Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  Michael Hardy Oct 27 '12 at 18:20
2  
Hint: If you know what $L_1, \dots, L_n$ are, what do you know about $X$? What interval must it lie in? –  Nate Eldredge Oct 27 '12 at 18:21
    
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. –  user46233 Oct 27 '12 at 19:09

1 Answer 1

up vote 1 down vote accepted

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]$.
share|improve this answer
    
Which is @NateEldredge's comment, the other way round. –  Did Oct 28 '12 at 8:11
    
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. –  user46233 Oct 28 '12 at 13:01
    
What you said in your last comment seems like a useful relation between the $X$ and $L_k$ to me. –  Did Oct 28 '12 at 13:04
    
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? –  user46233 Oct 28 '12 at 13:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.