Press "Enter" to skip to content

Random bits

Dice

The lowest unit of randomness is probably a random uniform bit, in other words a symmetric Bernoulli random variable taking the values \( {0} \) and \( {1} \) with probability \( {1/2} \). If

\[ U=\sum_{n=1}^\infty b_n2^{-n} \]

is the binary expansion of a random variable \( {U} \) taking values in the interval \( {[0,1]} \), then \( {U} \) follows the uniform law on \( {[0,1]} \) iff the bits \( {{(b_n)}_{n\geq1}} \) are i.i.d. symmetric Bernoulli. As explained in a previous post, this observation allows for instance to extract from \( {U} \) a whole infinite sequence of i.i.d. uniform random variables on \( {[0,1]} \). But real real numbers are not accessible in current computers.

In a computer, everything is finite, and we use a finite sequence of bits to produce a uniform discrete random variable, up to a fixed precision, typically \( {32} \) or \( {64} \) bits, which corresponds to \( {2^{32}} \) and \( {2^{64}} \) different values respectively. More generally, the simulation of the discrete uniform law on \( {n} \) different values amounts to the coding in bits of the integer \( {n} \), namely \( {\log_2(n)} \) bits. In particular, the simulation of a random permutation \( {\sigma_n} \) on \( {\{1,\ldots,n\}} \) costs approximately \( {\log_2(n!)\sim n\log_2(n)} \) bits. If we use the Fisher-Yates-Knuth shuffle, we simulate \( {\sigma_n} \) using the representation in terms of product of transpositions \( {\sigma_n=(1,U_1)\cdots(1,U_n)} \) where \( {U_1,\ldots,U_n} \) are independent with \( {U_k} \) following the uniform discrete law on \( {\{1,\ldots,k\}} \) for every \( {1\leq k\leq n} \). Then the total cost is \( {\sim\sum_{k=1}^n\log_2(k)\sim n\log_2(n)} \), as expected.

If we start from a fixed deterministic matrix \( {{(x_{jk})}_{1\leq j,k\leq n}} \), and produce a random matrix

\[ {(x_{\sigma(j,k)})}_{1\leq j,k\leq n} \]

by shuffling the \( {n^2} \) entries with a random uniform permutation \( {\sigma} \) of \( {\{1,\ldots,n^2\}} \), then we use approximately \( {2n^2\log_2(n)} \) bits. On the other hand, the production of a \( {n\times n} \) random matrix with i.i.d. entries following the uniform distribution on \( {\{0,\ldots,N\}} \) needs \( {n^2\log_2(N)} \) bits (\( {N=2} \) for Bernoulli entries).

Be First to Comment

    Leave a Reply

    Your email address will not be published. Required fields are marked *