# The distribution of the sum of infinite fair coin tosses

This question came up in a course on measure theoretic probability theory. We have had lots of information on the existence of distribution, but no examples of how to find/construct them. Here's the problem:

Let $X_1,X_2,\dots$ be an $iid$ sequence of Bernoulli random variables, defined on $(\Omega,\mathcal{F},\mathbb{P})$ with $\mathbb{P}(X_1=1)=\frac{1}{2}$. Let

$$X = \sum_{k=1}^\infty2^{-k}X_k.$$

Find the distribution of $X$.

Clearly $F(x) = \mathbb{P}(X \leq x) = \int_{-\infty}^xX\,d\mathbb{P}$, but how to go from hear I have no idea. I also tried the path $P(\sum_{k=1}^\infty2^{-k}X_k \leq x) = \mathbb{P}(X = 1)\mathbb{P}(\sum_{k=2}^\infty2^{-k}X_k\leq x - \frac{1}{2}) + \mathbb{P}(X=0)\mathbb{P}(\sum_{k=2}^\infty2^{-k}X_k \leq x)$ but this seems to be a dead end.

Any tips tips how to tackle this?

-
Bernoullis are discrete random variables, so instead of $P(X \leq x)$, why don't you try $P(X = k)$? I also wonder if you are aware of what the answer is in advance and you just have to prove it; or you just don't and want to construct the solution. –  busman Oct 14 '12 at 11:33
In this case we haven't been given what the distribution is, and I also figured it's good practice to learn how to find distribution which you don't know in advance. On your first point, although the $X_i$'s are discrete, their "normalized" sum can approach any point in $[0,1]$ by the looks of it. –  BallzofFury Oct 14 '12 at 11:38
I understand your point, as the limit of that sum can be irrational. –  busman Oct 14 '12 at 11:41

Let $x\in[0,1]$. Then we can write $$x=\sum_{k\ge 1}\frac{b_k}{2^k}\;,$$ where each $b_k\in\{0,1\}$; this is simply the binary expansion of $x$. To avoid any ambiguity, we represent positive dyadic rationals (numbers of the form $\frac{m}{2^n}$ for integers $m,n>0$) by their non-terminating expansions in which $b_k=1$ for all sufficiently large $k$.

Then $X<x$ iff there is an $n\in\Bbb Z^+$ such that $X_k=b_k$ for $1\le k<n$ and $X_n<b_n$. For any $k\in\Bbb Z^+$, $\Bbb P(X_k=b_k)=\frac12$, and $$\Bbb P(X_k<b_k)=\begin{cases}\frac12,&\text{if }b_k=1\\\\0,&\text{if }b_k=0\;.\end{cases}$$

Thus,

\begin{align*} \Bbb P(X<x)&=\Bbb P(X_1<b_1)+\Bbb P(X_1=b_1\land X_2<b_2)+\ldots\\ &=\sum_{k\ge 1}\Bbb P\left(\forall i<k(X_i=b_i)\land X_k<b_k\right)\\ &=\sum_{k\ge 1}\left(\frac12\right)^{k-1}\Bbb P(X_k<b_k)\\ &=\sum_{b_k=1}\left(\frac12\right)^k\\ &=\sum_{k\ge 1}\frac{b_k}{2^k}\\ &=x\;. \end{align*}

Looks like a uniform distribution to me.

-
Neato! Starting to see dyadic rationals popping up everywhere in probability, but this I would have never figured out on my own. Thanks! –  BallzofFury Oct 14 '12 at 13:48
@BallzofFury: You’re welcome! –  Brian M. Scott Oct 14 '12 at 13:50