# Series of independent Bernoulli variables

Let $$X_1, X_2, \ldots$$ be independent, identically distributed random variables with distribution $$\text{Ber}(\frac{1}{2})$$. Define the random varible:

$$Y:=\sum_{n=1}^\infty \frac{X_n}{2^n}$$

Prove that $$Y$$ is uniformly distributed over the unit interval $$[0,1]$$.

The only way I currently know how to attack this problem is by using Levy's theorem:

For $$Y_n:=\sum_{k=1}^n \frac{X_k}{2^k}$$, it's enough to prove that the characteristic function of $$Y_n$$ converges to the characteristic function of a uniform random variable, i.e.:

$$\lim_{n\to\infty}\mathbb{E}[e^{itY_n}]=\frac{e^{it}-1}{it}$$

Since $$X_1, X_2, \ldots$$ are independent, we have:

$$\mathbb{E}[e^{itY_n}]=\prod_{k=1}^n \mathbb{E} \left[e^{it\frac{X_k}{2^k}} \right] = \prod_{k=1}^n \frac{1+e^{it/2^k}}{2}.$$

I'm basically stuck because I don't know what to do with the product as $$n\to\infty$$.

Is there a trick to it? Is there maybe a simpler solution? Thanks in advance!

• Low tech way, show that $\Pr(Y\le a)=a$ using the binary expansion of $a$. – André Nicolas Jun 18 '16 at 2:28
• Looking at the first $n$ terms of the series, $Y$ is just as likely to be in any of the $2^n$ subintervals $[(j-1)2^{-n},j2^{-n}), j=1,\ldots,2^n$. You could use something like the $\pi-\lambda$ theorem to show that a measure that agrees with lebesgue measure on these cylinder sets must agree with lebesgue measure on the interval. – snarfblaat Jun 18 '16 at 3:00
• @AguirreK: I would have to write out the details. Apart from a little non-uniqueness, $x\lt a$ if the binary expansions agree up to the $k-1$-th place (where $k$ could be $0$) and then $x$ has a $0$ where $a$ has a $1$. sum the relevant probabilities over all $k$. Am favouriting the question and may write out a solution if no one else does. By the way, I think I have seen this question not too long ago. – André Nicolas Jun 18 '16 at 4:04
• @AguirreK: Yes, I had seen it. It is here. , I have not read the solution to check details are right, but it uses the same idea. Probably it has been asked on MSE a few other times, it is a natural question. – André Nicolas Jun 18 '16 at 4:10
• A rigorous proof is easy if you remember that the numbers $0.X_1X_2\ldots$ with $X_1=0$ are those in $[0,1/2]$ etc., so each intervals gets the correct measure, which then implies that your distribution is Lebesgue measure. – user138530 Jun 18 '16 at 5:44

## 3 Answers

Picking up where you left off:

\begin{align} \mathbb{E}[e^{itY_n}]=\prod_{k=1}^n \mathbb{E} \left[e^{it\frac{X_k}{2^k}} \right] &= \prod_{k=1}^n \frac{1+e^{it/2^k}}{2} \\ &= \frac{1}{2^n} \prod_{k=1}^n (e^{it/2^k}+1) \\ &= \frac{1}{2^n} (e^{it/2^{n}}+1) \prod_{k=1}^{n-1} (e^{it/2^k}+1) \\ &= \frac{1}{2^n} (e^{it/2^{n}}+1) \frac{(e^{it/2^{n}}-1)}{(e^{it/2^{n}}-1)} \prod_{k=1}^{n-1} (e^{it/2^k}+1) \\ &= \frac{1}{2^n (e^{it/2^n}-1)} (e^{it/2^{n-1}}-1) \prod_{k=1}^{n-1} (e^{it/2^k}+1)\\ &= \frac{1}{2^n (e^{it/2^n}-1)} (e^{it/2^{n-1}}-1) (e^{it/2^{n-1}}+1) \prod_{k=1}^{n-2} (e^{it/2^k}+1)\\ &= \frac{1}{2^n (e^{it/2^n}-1)} (e^{it/2^{n-2}}-1) \prod_{k=1}^{n-2} (e^{it/2^k}+1)\\ & \, \vdots \\ &= \frac{1}{2^n (e^{it/2^n}-1)} (e^{it/2^{n-n}}-1)\\ \\ &= \frac{(e^{it}-1)}{2^n (e^{it/2^n}-1)} . \end{align}

And, the Taylor expansion of $e^{it/2^n}$ is $1+\frac{1}{2^n}it+O(t^2)$, where $O(t^2)$ is such that $2n \cdot O(t^2) \to 0$, as $n \to \infty$. Therefore, $\mathbb{E}[e^{itY_n}]$ becomes:

\begin{align} \mathbb{E}[e^{itY_n}] &= \frac{(e^{it}-1)}{2^n (1+2^{-n}it+O(t^2)-1)} \\ &= \frac{(e^{it}-1)}{(it+2^n O(t^2))} \\ & \to \frac{(e^{it}-1)}{it}, \quad \mbox{as } n \to \infty. \quad \blacksquare \end{align}

Note that while it's certainly much easier to go via the cumulative distribution, your approach works, and uses a fairly typical technique for trigonometric products that you might like knowing. At least I always found it kinda cute...

First note that $1 + \exp (ix) = 1 + \cos x + i \sin x = 2 \cos x/2 \exp (ix/2)$ by using the half angle formulae. Thus,

$$\phi_n(t) = \prod_{k=1}^n \cos\left(t/2^{k+1} \right) \exp \left(it/2^{k+1} \right)$$

This breaks into two easier products:

First, use the sum of a geometric series to compute the following: $$P_{n,1} = \prod_{k = 1}^n \exp\left(it/2^{k+1} \right) = \exp \left(it \frac{1-2^{-n}}{2} \right)$$

Next, we'll repeatedly use the identity $2 \sin x \cos x = \sin 2x$ to exploit the fact that the cosines in our product have angles progressively reduced by a factor of $2$:

\begin{align} P_{n,2} &= \prod_1^n \cos \left(t/2^{k+1} \right) \\ &= \frac{\sin \left(t/2^{n+1} \right)}{\sin \left(t/2^{n+1} \right)} \prod_1^n \cos \left(t/2^{k+1} \right) \\ &\overset{a}{=} \frac{\sin \left(t/2^{n} \right)}{2\sin\left(t/2^{n+1} \right)} \prod_1^{n-1} \cos \left(t/2^{k+1} \right) \end{align}

where the equality $(a)$ is from using the above identity to take out the last term in the product. Continuing along the same lines,

$$P_{n,2} = \frac{\sin (t/2)}{2^n \sin (t/2^{n+1})}$$

As $n \to \infty$, $P_{n,1} \to \exp\left(it/2\right)$, and $P_{n,2} \to \frac{\sin t/2}{t/2}$. Since both limits exist, we have

$$\phi_n(t) \to \exp(it/2) \cdot \frac{\sin t/2}{t/2} = \exp(it/2) \cdot \frac{\exp(it/2) - \exp(-it/2)}{2i \cdot t/2} = \frac{\exp it - 1}{it}$$

Now appeal to the continuity of $\phi_\infty$, and mutter something about using a sledgehammer to hang a picture :)

• I think the solution via cumulative distribution is very intuitive but its formalization is delicate. This solution however is purely computational, which (in my opinion) is much easier to verify. Call me crazy, but I think it's a decent trade-off. Thanks! – rmdmc89 May 5 '20 at 20:06

Let $Y_n=\sum_{j=1}^n 2^{-j}X_j$, then $Y_n$ is uniformly distributed over the set $$\left\{\sum_{j\in S} 2^{-j} : S\subset\{1,2,\ldots,n\} \right\}.$$ This set has the same cardinality of the power set of $\{1,2,\ldots,n\}$, $2^n$, and so $\mathbb P(Y=y)=2^{-(n+1)}$ for each $y\in E_n$. This implies that $\mathbb P(Y_n=y)\stackrel{n\to\infty}\longrightarrow0$ for any $y\in[0,1]$. As $Y_n$ converges to $Y$ almost surely, it follows that $\mathbb P(Y=y)=0$ for any $y\in[0,1]$. Now, $Y$ takes values in the set $$A = \left\{\sum_{j\in S}2^{-j} : S\subset\mathbb N \right\}.$$ But $A=[0,1]$ as any $y\in[0,1]$ has a (possibly infinite) binary representation. If $S\subset A$ has zero Lebesgue measure, then $[0,1]\setminus S$ contains an open interval $(a,b)$. Choose $N$ such that $2^{-N}<b-a$. Then $\mathbb P(Y_N\in(a,b))>0$, and since $E_n\subset E_{n+1}$ it follows that $$\mathbb P(Y_n\in(a,b))\geqslant \mathbb P(Y_N\in(a,b))>0$$ for $n\geqslant N$. Since $Y_n$ converges to $Y$ almost surely, $Y_n$ converges to $Y$ in distribution, and hence $\mathbb P(Y\in(a,b))>0$. It follows that $Y$ is not concentrated on $S$ and therefore is a continuous random variable, that is, there exists a measurable function $f:\mathbb R\to\mathbb R$ such that $$\mathbb P(Y\leqslant y)=\int_{[0,y]}f\ \mathsf d\lambda,$$ where $\lambda$ is Lebesgue measure. If $y\in[0,1]$ has decimal expansion $0.y_1y_2\ldots$, then as $\mathbb P(X_n>y_n)=2^{-1}(1-y_n)$ and $\mathbb P(X_n=y_n)=2^{-1}$ for each $n$, it follows that \begin{align} \mathbb P(Y>y) &= \mathbb P\left(\bigcup_{n=1}^\infty\{X_n>y_n\}\cap \bigcap_{j=1}^{n-1} \{X_j=y_j\}\right)\\ &= \sum_{n=1}^\infty \mathbb P\left(\{X_n>y_n\}\cap \bigcap_{j=1}^{n-1} \{X_j=y_j\}\right)\\ &= \sum_{n=1}^\infty 2^{-n}(1-y_n)\\ &= \sum_{n=1}^\infty 2^{-n} - \sum_{n=1}^\infty 2^{-n}y_n\\ &= 1-y, \end{align} and hence $$y=\mathbb P(Y\leqslant y)=\int_{[0,y]}f\ \mathsf d\lambda.$$ This implies that $\mathbb P(Y\in(a,b))=b-a$ for all $(a,b)\subset[0,1]$, so $f=1$ a.e. and the distribution of $Y$ is Lebesgue measure on $[0,1]$, i.e. the uniform distribution on $[0,1]$.