How to show that $\lim_{n\to\infty}\mathbb{P}\left(\bigg|\frac{1}{n}S_n-f(n)\bigg|>\varepsilon\right)=0$

Question

Consider a collection of independent events $(X_i)$ with $\mathbb{I}_{X_i}$ being the indicator random variable for $X_i$.

Let $$f(n)=\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}(X_i)\quad\text{and}\quad S_n=\sum_{i=1}^{n}\mathbb{I}_{X_i}.$$

I'm interested in showing that $$\lim_{n\to\infty}\mathbb{P}\left(\bigg|\frac{1}{n}S_n-f(n)\bigg|>\varepsilon\right)=0,\quad\forall\varepsilon>0$$ (in other words show convergence in probability).

My second attempt: (using the hints given in the comments below)

Let $\varepsilon>0$. $$\lim_{n\to\infty}\mathbb{P}\left(\bigg|\frac{1}{n}S_n-f(n)\bigg|>\varepsilon\right)=\lim_{n\to\infty}\mathbb{P}\left(\frac{1}{n}\bigg|\sum_{i=1}^{n}\big[\mathbb{I}_{X_i}-\mathbb{P}(X_i)\big]\bigg|>\varepsilon\right)$$

Let us use the Chebyshev's inequality, i.e., $\mathbb{P}(|Y|\geq a)\leq\frac{\mathbb{E}(Y^2)}{a^2}$ which leads to

\begin{align} \lim_{n\to\infty}\mathbb{P}\left(\frac{1}{n}\bigg|\sum_{i=1}^{n}\big[\mathbb{I}_{X_i}-\mathbb{P}(X_i)\big]\bigg|>\varepsilon\right)& \leq\lim_{n\to\infty}\frac{\mathbb{E}\bigg(\frac{1}{n^2}\big(\sum_{i=1}^{n}\mathbb{I}_{X_i}-\mathbb{P}(X_i)\big)^2\bigg)}{n\varepsilon}\\ & =\lim_{n\to\infty}\sum_{i=1}^{n}\frac{\mathbb{E}\bigg(\big(\sum_{i=1}^{n}\mathbb{I}_{X_i}-\mathbb{P}(X_i)\big)^2\bigg)}{n^2\varepsilon}. \end{align}

Can we argue that as the term $\sum_{i=1}^{n}\mathbb{I}_{X_i}-\mathbb{P}(X_i)$ is just a summation of numbers, the expectation is constant and so taking the limit of $\frac{\text{constant}}{n^2}$ is equal to zero?

I'd appreciate any hints or help.

Answer 1

Recall Chebyshev's inequality. If $\mathbb{E}X^2 < \infty$, then for all $\epsilon >0$

$$\mathbb{P}(|X-\mathbb{E}X| > \epsilon) \leq Var(X)/\epsilon^2$$ Now, note that $\mathbb{E}S_n:= \sum_{k=1}^n \mathbb{E}I_{X_k} = \sum_{k=1}^n\mathbb{P}(X_k)$ and thus $\mathbb{E}(S_n/n) = f(n)$. Applying Chebyshev's inequality, we get

$$\mathbb{P}(|S_n/n-f(n)| > \epsilon) = \mathbb{P}(|S_n/n-\mathbb{E}(S_n/n)| > \epsilon) $$$$\leq Var(S_n/n)/\epsilon^2 = Var(S_n)/(n^2\epsilon^2) = \frac{1}{n^2\epsilon^2}\sum_{k=1}^n Var(I_{X_k})$$

You can now use the answer of Michael Hardy to conclude what you want.

Or, you can do the following if we assume that $\mathbb{P}(X_k)$ is constant for all $k$. Then the last sum reduces to

$$\frac{1}{n}Var(I_{X_1}) \stackrel{n \to \infty}{\to} 0$$

Under this last assumption, the strong law of large numbers also implies almost sure convergence, which is stronger than what you need.

Answer 2

For $0\le p \le1,$ you have $p(1-p)\le 1/4.$

$$ \operatorname{var} (\mathbb I_i) = \Pr(\mathbb I_i=1)\Pr(\mathbb I_i = 0) \le \frac 1 4. $$ $$ \operatorname{var}\left( \frac {S_n} n \right) = \frac 1 {n^2} \sum_{i=1}^n \operatorname{var} (\mathbb I_i) \le \frac 1 {4n}. $$ Now proceed as when using Chebyshev's inequality to prove the weak law of large numbers.