Generating a Uniform(0,1) Distribution Using a Fair Coin

How can we approximate a Uniform(0,1) random variable using a fair coin?

Answer

We can use the binary representation of numbers in $(0,1)$.

Let $b_1, b_2, b_3, \dots$ be independent indicator random variables that take value $1$ for heads and $0$ for tails. Then define

\[ U = \sum_{k=1}^{\infty} \frac{b_k}{2^k}. \]

which gives a number of the form $0.b_1 b_2 b_3 b_4 \dots$ in binary.

Each coin toss determines one binary digit of $U$. Hence, by tossing the coin many times, we generate a number uniformly distributed on $(0,1)$.

Notes and comments

Comment 1: The more coin tosses we perform, the more granular (i.e. more continuous) our approximation of the Uniform$(0,1)$ distribution becomes.

Comment 2: Note that we start with the first power of $2$ (i.e. $2^{-1}$), not the zeroth power. This ensures $U$ lies strictly within the interval $(0,1)$ rather than including $1$.

Back to collection