# Uniform Random Variable on $[0,1]$ and Bernoulli$(1/2)$

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?

• In your formulation, the claim is false: pick $X_1=Y$ and $X_n=0$ for $n>1$. – Maurizio Moreschi Jun 28 '19 at 1:16
• Thanks Maurizio Moreschi giving me a remider. This false proposition is found in our Stackechange. I haven't thought of it for a long time. Thanks a lot. – Scott Jun 28 '19 at 1:46

If you require $$X_i\in \{0,1\}$$ for all $$i$$, then what you wrote seems true. $$X_i$$ determines the $$i$$th digit in the binary expansion of $$Y$$, so if $$Y$$ is uniform, the $$i$$th digit in the binary expansion is equally likely to be $$0$$ and $$1$$, so we must have $$X_i\sim \text{Bern}(.5)$$. It is tedious, but not too conceptually difficult, to see that any set of indices for digits of the binary expansion of a uniform random variable is independent, so the set of $$X_n$$ must be independent. Therefore, $$X_1,\ldots$$ is iid $$\text{Bern}(.5)$$.
• As you say, "it seems true", "the $i$th digit in the binary expansion is equally likely to be 0 and 1, so we must have $X_i$~Bern$(.5)$". Why we "$\it{must \quad have}$"? Could you give me a detailed proof? – Scott Jun 28 '19 at 2:08
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.
• The binary search algorithm I mentioned in my proof, is as follows: At stage 1, divide $[0,1]$ equally into two intervals $[0,1/2]$ and $[1/2,1]$. If $b_1=1$, call $I_2=[1/2,1]$, else call $I_2 = [0,1/2]$. In step 2, divide $I_2$ into two consecultive equal length intervals. If $b_2 =1$, take $I_3$ to be the upper interval, otherwise take $I_3$ to be the lower interval. In general, if $b_{m-1} = 1$, take $I_m$ to be the upper interval from $I_{m-1}$, otherwise the lower interval. Then, the interval I mentioned above, is $I_{n}$. – abcd Jun 28 '19 at 2:58
• Thank you for giving me a good answer. The independence of $\{B_n,n\ge1\}$ is missing in your proof. But this isn't difficult. We can easily complement it. Thank you again. – Scott Jun 28 '19 at 8:54