5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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$." $\endgroup$ – Michael Dec 16 '19 at 22:38
  • $\begingroup$ @Michael I apologize for that. I think I messed up my terminology. $X_i$ are independent events. $\endgroup$ – johnny09 Dec 16 '19 at 22:42
  • 3
    $\begingroup$ Then, you should use the Chebyshev inequalty. Note that probabilties are just numbers, you can treat them as given constants. $\endgroup$ – Michael Dec 16 '19 at 22:43
  • 1
    $\begingroup$ Hint: $f(n)=\mathbb{E}[S_n/n]$ $\endgroup$ – Thorgott Dec 16 '19 at 22:44
  • 1
    $\begingroup$ I'm writing an answer to the question. Hold on a second. $\endgroup$ – ε--δ Dec 17 '19 at 17:16
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – johnny09 Dec 17 '19 at 18:08
  • 1
    $\begingroup$ 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. $\endgroup$ – ε--δ Dec 17 '19 at 18:10
  • 1
    $\begingroup$ @johny Michael Hardy showed how you can use my estimate to conclude what you want. $\endgroup$ – ε--δ Dec 17 '19 at 19:22
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 this was what I was missing in my answer. $\endgroup$ – ε--δ Dec 17 '19 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.