Let $X_n$, $n \geq 0$ be an independent sequence of random variables , with the following distributions : $$ P(X_n = x) = \begin{cases} 1 - \frac{1}{2^{n+1}} & x = 0 \\ \frac 1{2^{n+1}}& x= 2^n \\ 0 & o.w \\ \end{cases} $$ Show that $\sum_{n=1}^{k} X_n$ has an almost sure limit $S$ as $k \to \infty$, and find the distribution of $S$.
For this question, one can use the Kolmogorov three series theorem , or merely observe that since $\sum_{n=0}^\infty \frac 1{2^{n+1}} < \infty$, by Borel Cantelli we see that a.s. the sum $\sum_{n=1}^\infty X_n$ is actually a finite sum. Thus, the almost sure limit exists, let us call it $S$. Note that $S$ takes whole number values a.s.
Now, let us for example compute $P(S= 0)$. By the nature of $X_n$, $S = 0$ if and only if every $X_n = 0$, which happens with probability $\prod_{n=0}^\infty P(X_n = 0) \approx 0.28$.
Now, for $P(S = k)$, we look at the binary expansion of $k$, so write $k = \sum 2^{n_i}$ with the $n_i$ distinct. Then note that $S_n =k$ if and only if $X_{n_i} = 2^{n_i}$ for each $i$ and $X_m = 0$ for $m \neq n_i$. This comes to the expression : $$ P(S_n = k) = \prod_{i} \frac 1{2^{n_i+1}} \prod_{m \neq n_i} (1-\frac 1{2^{m+1}}) \approx \prod_i \frac{0.28}{(1-\frac 1{2^{n_i+1}})2^{n_i+1}} \\ \approx \frac{(0.28)^i}{\prod_i (2^{n_i+1} - 1)} $$ I would like confirmation that the above is correct.
Yes you are right so far. The PDF of $S_n$ is $$P(S_n = k) = \prod_{i} \frac 1{2^{n_i+1}} \prod_{m \neq n_i} \left(1-\frac 1{2^{m+1}}\right)$$If we define $N_i\triangleq \max n_i$ we can rewrite$$P(S_n = k) = \prod_{i} \frac 1{2^{n_i+1}} \prod_{m \neq n_i\\1\le m\le N_i} \left(1-\frac 1{2^{m+1}}\right)\prod_{m = N_i+1}^n \left(1-\frac 1{2^{m+1}}\right)$$the last term $\prod_{m = N_i+1}^n \left(1-\frac 1{2^{m+1}}\right)$ tends to $\prod_{m = N_i+1}^\infty \left(1-\frac 1{2^{m+1}}\right)$ when $n\to \infty$. Also$$\prod_{m = N_i+1}^\infty \left(1-\frac 1{2^{m+1}}\right)={\prod_{m = 1}^\infty \left(1-\frac 1{2^{m+1}}\right)\over \prod_{m = 1}^{N_i} \left(1-\frac 1{2^{m+1}}\right)}$$The expression $\prod_{m = 1}^\infty \left(1-\frac 1{2^{m+1}}\right)$ is a constant namely $l\approx0.5776$. Therefore$$\prod_{m = N_i+1}^\infty \left(1-\frac 1{2^{m+1}}\right)={l\over \prod_{m = 1}^{N_i} \left(1-\frac 1{2^{m+1}}\right)}$$and by substitution we obtain $$\Pr\{S=k\}{=\prod_{i} \frac 1{2^{n_i+1}} \prod_{m \neq n_i\\1\le m\le N_i} \left(1-\frac 1{2^{m+1}}\right){l\over \prod_{m = 1}^{N_i} \left(1-\frac 1{2^{m+1}}\right)}\\=l\cdot {\prod_{i} \frac 1{2^{n_i+1}}\over \prod_{i} 1-\frac 1{2^{n_i+1}}}\\=l\cdot \prod_{i} \frac 1{2^{n_i+1}-1}\\={l\over \prod_i (2^{n_i+1}-1)}\\\approx{0.5776\over \prod_i (2^{n_i+1}-1)}}$$