Series of independent Bernoulli variables

Question

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!

Answer 1

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}

Answer 2

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 :)

Answer 3

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]$.