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.
Leave a Comment