Press "Enter" to skip to content

Month: January 2014

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).

Leave a Comment

Rêve anarchiste

computer-comic

Contrairement à une idée reçue, les mathématiciens ne sont pas forcément très à l’aise avec l’informatique, et ont parfois grand peine à répondre à la question récurrente « Vaut-il mieux utiliser les systèmes Apple, Microsoft, ou Linux ? ».  Il n’y a sans doute pas de réponse universelle. Il s’agit d’une affaire de sensibilité personnelle, voire même, pour certains, de convictions religieuses ! Sur le plan symbolique, Microsoft et/ou Apple font parfois figure de grands méchants, tandis que Linux est souvent perçu comme un jouet mal fini pour bidouilleurs. Pourtant, les trois univers n’ont jamais été aussi proches. Pour ma part, voilà des années que j’utilise avec délice le système Debian(*) à la stabilité légendaire. Il constitue à mes yeux la réalisation concrète et improbable d’un rêve anarchiste moderne. Mais pour vivre dangereusement avec mon temps, j’utilise également un ordiphone Samsung équipé du système Android, un dérivé de Linux développé par Google (autre grand méchant du moment).

(*) Plus précisément le système Debian GNU/Linux sur matériel PC ou Apple. Mais Debian est également disponible avec d’autres noyaux (comme FreeBSD) et diverses architectures. Pour Debian, le noyau Linux est plus un moyen qu’une fin en soi.

Leave a Comment