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

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.

• There is no such thing as $P[X_i]$ for random variables $X_i$ (the probability that $X_i$ is....what?) There is also no such thing as "an indicator variable for $X_i$." Dec 16 '19 at 22:38
• @Michael I apologize for that. I think I messed up my terminology. $X_i$ are independent events. Dec 16 '19 at 22:42
• Then, you should use the Chebyshev inequalty. Note that probabilties are just numbers, you can treat them as given constants. Dec 16 '19 at 22:43
• Hint: $f(n)=\mathbb{E}[S_n/n]$ Dec 16 '19 at 22:44
• I'm writing an answer to the question. Hold on a second. Dec 17 '19 at 17:16

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.

• First, thank you for your answer. I think there is a typo in your last sentence (do you mean "strong LAW of large numbers?") Also, why do you say that your answer is not complete? Certainly as the upper bound of $\mathbb{P}(|S_n-f(n)|>\epsilon)$ goes to zero, then this proves convergence in probability, right? Dec 17 '19 at 18:08
• Thanks for spotting the typo. I say this answer is not complete because I assumed that we have $\mathbb{P}(X_1) = \mathbb{P}(X_2) = \dots$ which you are not given. Dec 17 '19 at 18:10
• @johny Michael Hardy showed how you can use my estimate to conclude what you want. Dec 17 '19 at 19:22

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.

• +1 this was what I was missing in my answer. Dec 17 '19 at 19:19