6
$\begingroup$

With $X \sim U[0,1]$, Lecturer says that $X = \sum_{k\ge 1} B_k(\frac{1}{2}) 2^{-k}$ where the $B_k(\frac{1}{2})$ are independent Bernoulli random variables with parameter $1/2$.

I have no idea how we can express uniformly distributed RV like that. Can anyone please explain?

Thanks,

$\endgroup$
  • 1
    $\begingroup$ You missed the subscript $k$ on the $B_k(\frac{1}{2})$, and presumably your lecturer would have said these are Bernoulli random variables that are independent. (Edited) $\endgroup$ – r.e.s. May 30 '16 at 13:19
  • 1
    $\begingroup$ If your $X$ is one r.v. and the above sum of Bernoulli r.v.s is another, then the two r.v.s have the same distribution even though they are not the same function. On the other hand, if $X$ is defined as the above sum of i.i.d. Bernoulli$(\frac{1}{2})$ r.v.s, then it has a Uniform[0,1] distribution. $\endgroup$ – r.e.s. May 30 '16 at 13:49
  • $\begingroup$ @r.e.s. Yes, he said $B_k(1/2)$ and independent. Sorry... $\endgroup$ – user1292919 May 31 '16 at 5:10
8
$\begingroup$

Theorem. $(X_i)_{i\in\mathbb{N}}\text{ iid Uniform }\{0,1\}\iff X=(0.X_1X_2X_3...)_2\sim\text{ Uniform }[0,1].$

Proof:

($\implies$)

If random variables (r.v.s) $X_1,X_2,\ldots$ are i.i.d. uniformly distributed on the set $\{0,1\}$, then $X=(0.X_1X_2\ldots)_2$ is a r.v. uniformly distributed on the real interval $[0,1]$. To see this, note that for any $x=(0.x_1x_2\ldots)_2\in[0,1)$ (always taking, WLOG, the unique binary representation of $x$ that has infinitely many $0$s), we have the following: $$\begin{align}\{X > x\} = & \{X_1>x_1\}\cup\\ &\{\{X_1=x_1\}\cap \{X_2>x_2\}\}\cup\\ &\{\{X_1=x_1\}\cap \{X_2=x_2\}\cap\{X_3>x_3\} \}\cup\\ &\ldots \end{align}$$ Now, $P(X_i >x_i) = \frac{1}{2}(1-x_i)$, so the probability of the above disjoint union is just $$\begin{align}P(X>x) &= \frac{1}{2}(1-x_1) + \frac{1}{2^2}(1-x_2) + \frac{1}{2^3}(1-x_3)+\ldots\\ &= \sum_{i=1}^\infty \frac{1}{2^i} - \sum_{i=1}^\infty \frac{x_i}{2^i}\\ &= 1 - x\\ \therefore P(X\le x) &= x \end{align} $$ therefore $X$ is a r.v. uniformly distributed on the interval $[0,1]$.

$(\impliedby)$

If $X$ is a r.v. uniformly distributed on the interval $[0,1]$ and $X_i$ denotes its $i$th binary digit (following the same convention as above for unique representation), then the $X_i$ are iid Uniform on the set $\{0,1\}$. To see this, note that $$P\left(X_{i_1}=x_{i_1},X_{i_2}=x_{i_2},...,X_{i_k}=x_{i_k}\right)=P\left(X\in 0.*{x_{i_1}}*{x_{i_2}}*...*{x_{i_k}}*\right)$$ where $\ \ 0.*{x_{i_1}}*{x_{i_2}}*...*{x_{i_k}}*\ \ $ denotes the set of real numbers in the interval $[0,1]$ having the specified binary digits. For example,
$$\begin{align}0.1*&=[0.1000...,\ 0.1000...+0.0111...)=[0.1, 1)\\ \\ 0.*x_3*&=0.00x_3*\ \cup\ 0.01x_3*\ \cup\ 0.10x_3*\ \cup\ 0.11x_3*\\ \\ &= [0.00x_3, 0.00x_3+0.001)\ \cup\ [0.01x_3, 0.01x_3+0.001)\\ \\ &\quad\ \cup\ [0.10x_3, 0.10x_3+0.001)\ \cup\ [0.11x_3, 0.11x_3+0.001),\\ \\ \end{align}$$ and in general $$\begin{align} \ 0.*{x_{i_1}}*{x_{i_2}}*...*{x_{i_k}}*&=\bigcup_{s_1s_2...s_k\in\{0,1\}^{i_k-k}}\left[0.s_1{x_{i_1}}s_2{x_{i_2}}...s_k{x_{i_k}},\ \ 0.s_1{x_{i_1}}s_2{x_{i_2}}...s_k{x_{i_k}}+2^{-{i_k}}\right). \end{align}$$
That is, the general term $\ 0.*{x_{i_1}}*{x_{i_2}}*...*{x_{i_k}}*\ $ is a union of $2^{i_k-k}$ disjoint intervals, each having width $2^{-i_k}.$ (The binary string $s_1{x_{i_1}}s_2{x_{i_2}}...s_k{x_{i_k}}$ is $i_k$ digits long and contains $k$ $x$s, so $s_1s_2...s_k$ is a binary string of length $i_k-k$, of which kind there are $2^{i_k-k}$ altogether.) Therefore, $$\begin{align}&P\left(X_{i_1}=x_{i_1},X_{i_2}=x_{i_2},...,X_{i_k}=x_{i_k}\right)\\ \\ &=P(X\in 0.*{x_{i_1}}*{x_{i_2}}*...*{x_{i_k}}*)\\ \\ &=P\left(X\in\bigcup_{s_1s_2...s_k\in\{0,1\}^{i_k-k}}\left[0.s_1{x_{i_1}}s_2{x_{i_2}}...s_k{x_{i_k}},\ \ 0.s_1{x_{i_1}}s_2{x_{i_2}}...s_k{x_{i_k}}+2^{-{i_k}}\right) \right)\\ \\ &=\sum_{s_1s_2...s_k\in\{0,1\}^{i_k-k}} P\left(X\in\left[0.s_1{x_{i_1}}s_2{x_{i_2}}...s_k{x_{i_k}},\ \ 0.s_1{x_{i_1}}s_2{x_{i_2}}...s_k{x_{i_k}}+2^{-{i_k}}\right) \right)\\ \\ &= 2^{i_k-k}\cdot 2^{-i_k}\\ &= 2^{-k}. \end{align}$$ As a special case, $P(X_i=x_i) = 2^{-1}$, so we have mutual independence of the $X_i$: $$P\left(X_{i_1}=x_{i_1},...,X_{i_k}=x_{i_k}\right) = 2^{-k}=\prod_{j=1..k}P\left(X_{i_j}=x_{i_j}\right); $$ consequently, the $X_i$ are iid Uniform on the set $\{0,1\}.$

QED

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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