3
$\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
  • 1
    $\begingroup$ In your formulation, the claim is false: pick $X_1=Y$ and $X_n=0$ for $n>1$. $\endgroup$ – Maurizio Moreschi Jun 28 '19 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 '19 at 1:46
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 '19 at 2:08
0
$\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 '19 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 '19 at 8:54

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.