Sequence of independent random variables with converging parameter 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?
 A: 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:


*

*Generate $U_{i} \sim \text{Uniform}(0,1)$.

*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$.
