4
$\begingroup$

Let $L_k$ uniform (discrete) i.i.d. variables in $\{0,1\}$. How to prove $$X:=\sum_{k=1}^\infty \frac{L_k}{2^k}$$ is uniformly distributed in $[0,1]$?

Of course I have to show that the cdf is the same, which means I have to prove for all $n \in \mathbb{N}$, $$P\left(X \leq \frac{j}{2^n}\right) = \frac{j}{2^n}.$$

I have no idea how to continue after

$$P\left(X \leq \frac{j}{2^n} \right) = P\left(\sum_{k=1}^\infty \frac{L_k}{2^k}\leq \frac{j}{2^n} \right)$$

Can sb. give me a hint?

  • 0
    I think once you got $\Pr(X\le x)=x$ for all binary rationals $x\in[0,1]$, then $\Pr(X\le x)=x$ for all real $x\in[0,1]$ follows fairly easily. When you say you have no idea how to continue after a certain identity, do you mean you have no idea how to prove that identity, or that you have no idea what to do after you've proved it?2012-10-27
  • 2
    Hint: If you know what $L_1, \dots, L_n$ are, what do you know about $X$? What interval must it lie in?2012-10-27
  • 0
    I know from the sum that $X\in[0,1]$ by simple estimate. If there wouldn't be the weights $\frac{1}{2^k}$ in the sum, I would have a binomial distributed variable, or am I wrong? I have no idea how to prove this identity in this specific example.2012-10-27

1 Answers 1

1

Hints:

  • Let $n\geqslant0$ and $1\leqslant j\leqslant2^n$. Write $\left[\frac{j-1}{2^n}\leqslant X\lt\frac{j}{2^n}\right]$ as an event involving only the random variables $(L_1,\ldots,L_n)$.
    For example, show that $\left[\frac58\leqslant X\lt\frac34\right]=[L_1=1,L_2=0,L_3=1]$.
  • Deduce that $\mathbb P\left[\frac{j-1}{2^n}\leqslant X\lt\frac{j}{2^n}\right]=\frac{1}{2^n}$ for every $n\geqslant0$ and $1\leqslant j\leqslant2^n$.
  • Deduce that $\mathbb P\left[X\lt x\right]=x$ for every $x$ in $[0,1]$, and finally that $\mathbb P\left[X\leqslant x\right]=x$ for every $x$ in $[0,1]$.
  • 0
    Which is @NateEldredge's comment, the other way round.2012-10-28
  • 0
    I think my problem is, that I am not able to find the relation between the X and $L_k$ in a useful way. I know that for a given $n\in \mathbb{N}$ and $i$ the relation $\frac{i-1}{2^n}\le \sum_{k=1}^\infty \frac{L_k}{2^k}\leq \frac{i}{2^n}$ implies (yeah this a stupid step) $i-1\le \sum_{k=1}^\infty L_k\cdot 2^{n-k}\leq i$. So if I know the binary notation of "i" then I know the how the $L_k$ looks like. So $L_k=1$ iff the number "i" contains "1" on the k-th place in its binary notation.2012-10-28
  • 0
    What you said in your last comment seems like a useful *relation between the $X$ and $L_k$* to me.2012-10-28
  • 0
    Ok. I have:Let $X:=\sum X_k/2^k$, $X':=X-i$ and $I:=\left(\frac{i-1}{2^n},\frac{i}{2^n} \right]$ for some i. For $c_1,\ldots,c_n\in\{0,1\}$ we define $x:=\sum_{k=1}^nc_k\frac{1}{2^k}$ (only dyadic rational number). The property of X to be in the intervall I must be equivalent that $P(X\in I)=P(X'-i\in (x,x+\frac{1}{2^n}])=P(X_1'=c_1,\ldots, X_n'=c_n)-P(X'=x)\overset{?}{=}\frac{1}{2^n}$. I hope that this is the right direction. Can be X'=x? I only have dyadic rational insteal of real numbers. So is $\lambda(y)=0$ for a dyadic rational number y?2012-10-28