2018-Q3 – Bernoulli Binary Expansion, Almost Sure Convergence, and Characteristic Functions
2018 Probability Prelim Exam (PDF)
Problem 3 (verbatim)
Let $X, X_1, X_2,\ldots$ be an i.i.d. sequence of random variables where
\(X_k \sim \text{Bernoulli}\left(\tfrac12\right).\)
Let
\(S_n = \sum_{k=1}^n \frac{X_k}{2^k},\qquad n\ge 1.\)
(a) Prove the following.
(i) $S_n$ converges a.s. as $n\to\infty$. Denote the limit random variable by $S_\infty$.
(ii) $E(S_n)\to E(S_\infty)$ and $V(S_n)\to V(S_\infty)$. Calculate $E(S_\infty)$ and $V(S_\infty)$.
(b) Prove that
\(\prod_{k=1}^n \frac{1 + e^{i(t/2^k)}}{2}\)
converges as $n\to\infty$ for each $t\in \mathbb{R}$.
(c) It is known that
\(\prod_{k=1}^\infty \frac{1 + e^{i(t/2^k)}}{2}
= \frac{e^{it} - 1}{it},\qquad t\in\mathbb{R}.\)
Use this identity to find the distribution of $S_\infty$.
Solution
(a)(i) Convergence of $S_n$
Claim
\(S_n \to S_\infty \quad \text{a.s.}\)
Proof
Monotonicity
For each $k$,
\(0 \le X_k \le 1 \quad\Rightarrow\quad 0 \le \frac{X_k}{2^k} \le \frac{1}{2^k}.\)
Thus each increment is nonnegative, and consequently
\(S_{n+1} = S_n + \frac{X_{n+1}}{2^{n+1}} \ge S_n.\)
Hence $(S_n)$ is monotonically nondecreasing.
Boundedness
\(S_n \le \sum_{k=1}^\infty \frac{1}{2^k} = 1.\)
Thus $(S_n)$ is bounded above by 1.
Uniform Convergence Argument
A monotone increasing sequence of real numbers bounded above converges. Therefore the limit
\(S_\infty = \lim_{n\to\infty} S_n\)
exists pointwise, and hence almost surely.
Conclusion
\(S_n \xrightarrow{\text{a.s.}} S_\infty = \sum_{k=1}^\infty \frac{X_k}{2^k}.\)
(a)(ii) Convergence of $E(S_n)$ and $V(S_n)$
Claim
\(E(S_n)\to E(S_\infty), \qquad V(S_n)\to V(S_\infty).\)
Compute
\(E(S_\infty),\qquad V(S_\infty).\)
Proof
Expectation
\(E(S_n)=\sum_{k=1}^n \frac{E(X_k)}{2^k}
= \sum_{k=1}^n \frac{1/2}{2^k}.\)
This is a geometric series:
\(E(S_n) = \frac12 \sum_{k=1}^n 2^{-k}.\)
From part (i), $S_n\uparrow S_\infty$, so by the Monotone Convergence Theorem,
\(E(S_\infty)=\frac12\sum_{k=1}^\infty 2^{-k} = \frac12.\)
Variance
We already know from part (a)(i) that \(S_n \xrightarrow{\text{a.s.}} S_\infty, \qquad\text{and}\qquad 0 \le S_n \le \sum_{k=1}^\infty \frac{1}{2^k}=1.\) Therefore also \(0 \le S_n^2 \le 1 \qquad\text{and}\qquad S_n^2 \xrightarrow{\text{a.s.}} S_\infty^2.\) Hence, by the Bounded Convergence Theorem, \(E[S_n]\to E[S_\infty] \quad\text{and}\quad E[S_n^2]\to E[S_\infty^2].\) Now use the identity $\operatorname{Var}(Y)=E[Y^2]-(E[Y])^2$: \(\operatorname{Var}(S_n) =E[S_n^2]-(E[S_n])^2 \;\longrightarrow\; E[S_\infty^2]-(E[S_\infty])^2 =\operatorname{Var}(S_\infty).\)
So it remains only to compute $\operatorname{Var}(S_\infty)$.
By independence, \(\operatorname{Var}(S_n)=\sum_{k=1}^n \operatorname{Var}\!\left(\frac{X_k}{2^k}\right) =\sum_{k=1}^n \frac{\operatorname{Var}(X_k)}{4^k}.\) Since $X_k\sim\text{Bernoulli}(1/2)$, $\operatorname{Var}(X_k)=\tfrac14$, so \(\operatorname{Var}(S_n) =\sum_{k=1}^n \frac{1/4}{4^k} =\frac14\sum_{k=1}^n 4^{-k}.\) Taking $n\to\infty$ (now just a numerical geometric-series limit), \(\operatorname{Var}(S_\infty) =\lim_{n\to\infty}\operatorname{Var}(S_n) =\frac14\sum_{k=1}^\infty 4^{-k} =\frac14\cdot\frac{1/4}{1-1/4} =\frac14\cdot\frac13 =\frac{1}{12}.\)
Conclusion
\(E(S_\infty)=\frac12,\qquad V(S_\infty)=\frac{1}{12}.\)
Key Takeaway (for part a)
- Monotone Convergence Theorem justifies exchanging limit and expectation because $S_n$ is monotone and nonnegative.
- Always distinguish between
- purely numerical limits, and
- limits requiring justification under the expectation (MCT, DCT, or BCT).
(b) Convergence of the Infinite Product
Claim
For each fixed $t\in\mathbb{R}$,
\(\prod_{k=1}^n \frac{1 + e^{i(t/2^k)}}{2}\)
converges as $n\to\infty$.
Proof
Step 1: Identify the product as a characteristic function
For Bernoulli$(1/2)$,
\(\phi_{X_k/2^k}(t)=E\left[e^{it X_k/2^k}\right]
= \frac{1+e^{i(t/2^k)}}{2}.\)
Thus by independence,
\(\phi_{S_n}(t)
=E(e^{it S_n})
=\prod_{k=1}^n \frac{1+e^{i(t/2^k)}}{2}.\)
Step 2: Convergence by Lévy’s Continuity Theorem
From part (a)(i),
\(S_n \xrightarrow{a.s.} S_\infty.\)
Hence
\(S_n \Rightarrow S_\infty.\)
By Lévy’s Continuity Theorem (part 1),
\(\phi_{S_n}(t)\to \phi_{S_\infty}(t)\)
for each fixed $t$. Therefore the product converges.
Conclusion
\(\prod_{k=1}^n \frac{1+e^{i(t/2^k)}}{2} \to \phi_{S_\infty}(t).\)
Takeaways (part b)
- Lévy’s Continuity Theorem (part 1):
If $S_n\Rightarrow S$, then $\phi_{S_n}(t)\to\phi_S(t)$ pointwise. - Always check whether a mysterious analytical expression is actually a characteristic function.
(c) Distribution of $S_\infty$
We are given the identity:
\(\prod_{k=1}^\infty \frac{1 + e^{i(t/2^k)}}{2}
= \frac{e^{it}-1}{it}.\)
Claim
\(S_\infty \sim \text{Uniform}(0,1).\)
Proof
The characteristic function of a Uniform$(0,1)$ random variable is
\(\phi_U(t)=\int_0^1 e^{itx}\,dx = \frac{e^{it}-1}{it}.\)
From part (b),
\(\phi_{S_\infty}(t)
=\prod_{k=1}^\infty \frac{1 + e^{i(t/2^k)}}{2}
= \frac{e^{it}-1}{it}.\)
Justify weak convergence
By Lévy’s Continuity Theorem (part 2):
If
- $\phi_{S_n}(t)\to \phi(t)$,
- $\phi(t)$ is continuous at $0$,
then
\(S_n \Rightarrow S,\)
where $S$ has characteristic function $\phi$.
Here:
- Convergence was established in (b).
- $\phi(t)=(e^{it}-1)/(it)$ is a valid characteristic function with $\phi(0)=1$.
Thus
\(S_\infty \overset{d}= U(0,1).\)
Conclusion
\(S_\infty \sim \text{Uniform}(0,1).\)
Key Takeaways (part c)
-
Uniqueness of characteristic functions:
If two distributions have the same characteristic function, they are equal in distribution. -
The infinite Bernoulli binary expansion
\(S_\infty = \sum_{k=1}^\infty \frac{X_k}{2^k}\)
is exactly the classical binary construction of a Uniform(0,1) random variable.
Summary of Main Tools
- Monotone Convergence Theorem (MCT)
- Lévy’s Continuity Theorem (parts 1 and 2)
- Geometric series identities
- Uniqueness of characteristic functions
- Interpreting infinite products as characteristic functions of partial sums
Comments