Let $X_1,X_2,…$ be independent, identically distributed (iid) random variables with distribution Bernoulli$(1/2)$. Define the random variable:
$$Y=\sum_{n=1}^\infty\frac{X_n}{2^n}.$$
Then $Y$ is unifromly distributed over the unit interval $[0,1]$. The proof of this result can be found in our mathstacexchange:
Series of independent Bernoulli variables
But the inverse proposition:
If $Y$ is a uniform random variable on unit interval $[0,1]$, and
$$Y=\sum_{n=1}^\infty\frac{X_n}{2^n}.$$
then $X_1,X_2,…$ are iid sequences of Bernoulli$(1/2)$.
How can we prove this result?
Best Answer
Okay, let's first see why the first binary digit of $U$ is Bernoulli$(1/2)$. The first binary digit is $1$ if and only if $U \geq 1/2$, which has probability $1/2$, so we are done. For convenience, let $B_n$ denote the $n^{th}$ binary digit of $U$. Now, inductively assume that $B_1,\ldots,B_{n-1}$ are i.i.d. Bernoulli$(1/2)$. Then, look at the conditional probability $q_n:=\mathbb{P}(B_n=1\big|(B_1,\ldots,B_{n-1})=(b_1,\ldots,b_{n-1}))$, for a sequence $(b_1,\ldots,b_{n-1}) \in \{0,1\}^{n-1}$. Divide the interval $[0,1]$ into the diadic intervals of length $1/2^{n-1}$, and let these intervals be enumerated from left to right as $I_1,I_2,...I_{2^{n-1}}$. Now, what does the event $(B_1,\ldots,B_{n-1})=(b_1,\ldots,b_{n-1})$ say? It says that (is equal to the following event) $U$ must lie in exactly one of these diadic intervals, say $I_i$, where $i$ is a (complicated, but don't need to know) deterministic function of the deterministic binary sequence $(b_1,\ldots,b_{n-1})$. The way to find this interval is to follow a binary search algorithm, similar to the proof of the Heini-Borel theorem in real analysis.
Anyway, let $m_i$ be the midpoint of $I_i$. So, $$q_n = \mathbb{P}(U > m_i|U\in I_i)~.$$ The above probability is obviously $1/2$. This shows that $B_n$ has a Bernoulli$(1/2)$ distribution, independent of $(B_1,\ldots,B_{n-1})$, and the induction is complete.