4
$\begingroup$

Let $X_1,X_2,...$ be independent, identically distributed (iid) random variables with distribution Bernoulli$(1/2)$. Define the random variable: $$Y=\sum_{n=1}^\infty\frac{X_n}{2^n}.$$ Then $Y$ is unifromly distributed over the unit interval $[0,1]$. The proof of this result can be found in our mathstacexchange: Series of independent Bernoulli variables

But the inverse proposition:

If $Y$ is a uniform random variable on unit interval $[0,1]$, and $$Y=\sum_{n=1}^\infty\frac{X_n}{2^n}.$$ then $X_1,X_2,...$ are iid sequences of Bernoulli$(1/2)$.

How can we prove this result?

$\endgroup$
2
  • 2
    $\begingroup$ In your formulation, the claim is false: pick $X_1=Y$ and $X_n=0$ for $n>1$. $\endgroup$ Jun 28, 2019 at 1:16
  • $\begingroup$ Thanks Maurizio Moreschi giving me a remider. This false proposition is found in our Stackechange. I haven't thought of it for a long time. Thanks a lot. $\endgroup$
    – Scott
    Jun 28, 2019 at 1:46

2 Answers 2

2
$\begingroup$

Okay, let's first see why the first binary digit of $U$ is Bernoulli$(1/2)$. The first binary digit is $1$ if and only if $U \geq 1/2$, which has probability $1/2$, so we are done. For convenience, let $B_n$ denote the $n^{th}$ binary digit of $U$. Now, inductively assume that $B_1,\ldots,B_{n-1}$ are i.i.d. Bernoulli$(1/2)$. Then, look at the conditional probability $q_n:=\mathbb{P}(B_n=1\big|(B_1,\ldots,B_{n-1})=(b_1,\ldots,b_{n-1}))$, for a sequence $(b_1,\ldots,b_{n-1}) \in \{0,1\}^{n-1}$. Divide the interval $[0,1]$ into the diadic intervals of length $1/2^{n-1}$, and let these intervals be enumerated from left to right as $I_1,I_2,...I_{2^{n-1}}$. Now, what does the event $(B_1,\ldots,B_{n-1})=(b_1,\ldots,b_{n-1})$ say? It says that (is equal to the following event) $U$ must lie in exactly one of these diadic intervals, say $I_i$, where $i$ is a (complicated, but don't need to know) deterministic function of the deterministic binary sequence $(b_1,\ldots,b_{n-1})$. The way to find this interval is to follow a binary search algorithm, similar to the proof of the Heini-Borel theorem in real analysis.

Anyway, let $m_i$ be the midpoint of $I_i$. So, $$q_n = \mathbb{P}(U > m_i|U\in I_i)~.$$ The above probability is obviously $1/2$. This shows that $B_n$ has a Bernoulli$(1/2)$ distribution, independent of $(B_1,\ldots,B_{n-1})$, and the induction is complete.

$\endgroup$
2
  • $\begingroup$ The binary search algorithm I mentioned in my proof, is as follows: At stage 1, divide $[0,1]$ equally into two intervals $[0,1/2]$ and $[1/2,1]$. If $b_1=1$, call $I_2=[1/2,1]$, else call $I_2 = [0,1/2]$. In step 2, divide $I_2$ into two consecultive equal length intervals. If $b_2 =1$, take $I_3$ to be the upper interval, otherwise take $I_3$ to be the lower interval. In general, if $b_{m-1} = 1$, take $I_m$ to be the upper interval from $I_{m-1}$, otherwise the lower interval. Then, the interval I mentioned above, is $I_{n}$. $\endgroup$
    – abcd
    Jun 28, 2019 at 2:58
  • $\begingroup$ Thank you for giving me a good answer. The independence of $\{B_n,n\ge1\}$ is missing in your proof. But this isn't difficult. We can easily complement it. Thank you again. $\endgroup$
    – Scott
    Jun 28, 2019 at 8:54
0
$\begingroup$

If you require $X_i\in \{0,1\}$ for all $i$, then what you wrote seems true. $X_i$ determines the $i$th digit in the binary expansion of $Y$, so if $Y$ is uniform, the $i$th digit in the binary expansion is equally likely to be $0$ and $1$, so we must have $X_i\sim \text{Bern}(.5)$. It is tedious, but not too conceptually difficult, to see that any set of indices for digits of the binary expansion of a uniform random variable is independent, so the set of $X_n$ must be independent. Therefore, $X_1,\ldots$ is iid $\text{Bern}(.5)$.

$\endgroup$
1
  • $\begingroup$ As you say, "it seems true", "the $i$th digit in the binary expansion is equally likely to be 0 and 1, so we must have $X_i$~Bern$(.5)$". Why we "$\it{must \quad have}$"? Could you give me a detailed proof? $\endgroup$
    – Scott
    Jun 28, 2019 at 2:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .