For any ${u\in[0,1]}$, let us consider a binary expansion

$u=0.b_1b_2\ldots=\sum_{n=1}^\infty b_n2^{-n}$

where ${b_1,b_2,\ldots}$ belong to ${\{0,1\}}$ (bits). This expansion is not unique when ${u}$ is rational, e.g.

$0.011111\cdots=0.10000\cdots.$

If ${U}$ is a uniform random variable on ${[0,1]}$ then almost surely, ${U}$ is irrational and its binary expansion is unique with ${b_1,b_2,\ldots}$ independent uniform random variables on ${\{0,1\}}$:

$\mathbb{P}(b_1=\varepsilon_1,\ldots,b_n=\varepsilon_n)=2^{-n}$

for any ${n\geq1}$ and every ${\varepsilon_1,\ldots,\varepsilon_n}$ in ${\{0,1\}}$. Conversely, if ${b_1,b_2,\ldots}$ are independent uniform random variables on ${\{0,1\}}$ then the random variable

$U:=\sum_{n=1}^\infty b_n2^{-n}$

follows the uniform law on ${[0,1]}$. Actually the odd/even separation map

$U=\sum_{n=1}^\infty b_n2^{-n}\mapsto (V_1,V_2):=\left(\sum_{n=1}^\infty b_{2n}2^{-n},\sum_{n=1}^\infty b_{2n-1}2^{-n}\right).$

allows to extract from ${U}$ a couple ${(V_1,V_2)}$ of independent uniform random variables on ${[0,1]}$. More generally, one can extract from ${U}$ a countable family ${{(W_n)}_{n\in\mathbb{Z}}}$ of independent uniform random variables on ${[0,1]}$ by considering the diagonals (or the columns, or the rows) in

$\begin{array}{ccccc} b_1 & b_2 & b_5 & b_{10} & \cdots \\ b_4 & b_3 & b_6 & b_{11} & \cdots \\ b_9 & b_8 & b_7 & b_{12} & \cdots \\ b_{16} & b_{15} & b_{14} & b_{13} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$

This reduces the simulation of any law to the simulation of the Bernoulli law.

Be First to Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.