Sequence of independent random variables with converging parameter

Question

Let $X_j, j\in\mathbb N$ be independent random variables s.t $X_j \sim B(1,p_j)$, where $p_j\to p\in (0,1)$. Let $$S_n = \frac{1}{n}\sum_{j=1}^n X_j $$ Show that $S_n$ converges a.s for which it's sufficient to show $S_n,n\in\mathbb N$ is a Cauchy sequence so we would have to show $$P\left (\sup_{m\geq 0} \left\lvert S_{n+m}-S_n\right\rvert > \varepsilon\right ) \xrightarrow[n\to\infty]{}0 $$ My hope at first was Markov's inequality: $$P(X\geq c)\leq \frac{EX}{c} $$ But since it's not i.i.d, I have no idea what $S_n$ is. Furthermore, how to make use of the converging parameter?

Answer 1

There is a trick that might help you. Let $X_{i} \sim \text{Bernoulli}(p_i)$. Note that you can simulate from $X_{i}$ in the following way:

1. Generate $U_{i} \sim \text{Uniform}(0,1)$.
2. Let $X_{i} = \mathbb{I}(U_{i} \leq p_i)$.

Now, let $Y_i = \mathbb{I}(U_i \leq p)$. If $p > p_i$, then \begin{align*} \mathbb{I}(U_i \leq p) &= \mathbb{I}(U_i \leq p_i) + \mathbb{I}(p_i \leq U_i \leq p) \\ \mathbb{I}(U_i \leq p_i) &= \mathbb{I}(U_i \leq p) - \mathbb{I}(p_i \leq U_i \leq p) \\ X_i &= Y_i - \mathbb{I}(p_i \leq U_i \leq p) \end{align*} Similarly, if $p_i > p$, then $X_i = Y_i + \mathbb{I}(p \leq U_i \leq p_i)$.

By putting these facts together, conclude that there exists a random variable, $Z_{i} \sim \text{Bernoulli}(|p-p_i|)$, such that \begin{align*} X_i &= Y_i + (-1)^{\mathbb{I}(p > p_i)}Z_i \end{align*} Using the previous equation, you can obtain that \begin{align*} S_n := \bar{X}_n &= \bar{Y}_n +n^{-1}\sum_{i=1}^{n}(-1)^{\mathbb{I}(p > p_i)}Z_i \end{align*} Note that $Y_{1},\ldots,Y_n$ are i.i.d. Bernoulli$(p)$. Hence, it follows from the LGN that $\bar{Y}_n$ converges a.s. to $p$. Now, it remains to prove that $n^{-1}\sum_{i=1}^{n}(-1)^{\mathbb{I}(p > p_i)}Z_i$ converges a.s. to $0$. In order to do this, it is sufficient to show that, for every $\epsilon >0$, \begin{align*} \sum_{n=1}^{\infty}{\mathbb{P}\left(\bigg|n^{-1}\sum_{i=1}^{n}(-1)^{\mathbb{I}(p > p_i)}Z_i\bigg| > \epsilon \right)} < \infty \end{align*} Now note that \begin{align*} \mathbb{P}\left(\bigg|n^{-1}\sum_{i=1}^{n}(-1)^{\mathbb{I}(p > p_i)}Z_i\bigg| > \epsilon \right) &\leq \mathbb{P}\left(\sum_{i=1}^{n}Z_i > n\epsilon\right) \\ &= \mathbb{P}\left(\exp\left(\sum_{i=1}^{n}Z_i\right) > \exp(n\epsilon) \right) \\ &\leq \frac{\mathbb{E}\left[\exp\left(\sum_{i=1}^{n}Z_i\right) \right]} {\exp(n\epsilon)} & \text{Markov's inequality} \\ &= \frac{\prod_{i=1}^{n}{(e|p-p_i|+(1-|p-p_i|))}} {\exp(n\epsilon)} \end{align*} Since $\lim_{i}p_i = p$, there exists $m$ such that, for every $i > m$, $e|p-p_i|+1 \leq \exp(0.5\epsilon)$. Therefore, \begin{align*} \frac{\prod_{i=1}^{n}{(e|p-p_i|+(1-|p-p_i|))}} {\exp(n\epsilon)} &\leq \prod_{i=1}^{m}{(e|p-p_i|+1)} \cdot \frac{\prod_{i=m+1}^{n}{\exp(0.5\epsilon)}}{\exp(n\epsilon)} \\ &\leq k \exp(-0.5n\epsilon) & k := \prod_{i=1}^{m}{(e|p-p_i|+1)} {\exp(n\epsilon)} \end{align*} Using this inequality, you can show that $\sum_{n=1}^{\infty}{\mathbb{P}\left(\bigg|n^{-1}\sum_{i=1}^{n}(-1)^{\mathbb{I}(p > p_i)}Z_i\bigg| > \epsilon \right)} < \infty$ and, therefore, $\bar{X}$ converges a.s. to $p$.