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.

Syntax · Style · Tracking & Privacy.