# Proof verification: Using Chebyshev inequality and weak law of large numbers.

Exercise. Let $$(\Omega, \mathcal{A}, \mathbb{P})$$ be a probability space, $$A \in \mathcal{A}$$ and $$X_N : \Omega^N \to \mathbb{R}$$ a random variable such that $$X_N(\omega_1, \dots, \omega_N) := \frac{1}{N} \sum_{n=1}^{N} \chi_{A}(\omega_n)$$ Show that $$\lim_{N \to \infty} \mathbb{P}[|X_N - \mathbb{P}(A)| > \sigma] = 0$$ for any $$\sigma > 0$$.

Attempt. Fix $$N$$. Then we can write $$X_N =\frac{1}{N} (X^1 + \dots + X^N)$$ with $$X^i : \Omega^N \to \mathbb{R}$$ such that $$X^{i}$$ is equal to $$1$$ if $$\omega_i \in A$$ and is zero otherwise. So we have $$\mathbb{P}(X^i = 1) = \sum_{\omega \in \Omega^N \\ \omega_i \in A } p_{\Omega^N}(\omega) = \sum_{\omega \in A} p_{\Omega}(\omega) = \mathbb{P}(A)$$ Then we get that $$\mathbb{E}(X_N) = \frac{1}{N} \big(\mathbb{E}(X^1) + \dots + \mathbb{E}(X^N)\big) = \frac{1}{N} \cdot N \cdot \sum_{\omega \in A} p_{\Omega}(\omega) = \mathbb{P}(A)$$ and $$\mathbb{V}(X_N) = \mathbb{P}(A) - \mathbb{P}(A)^2$$.

Applying Chebyshev inequality, we get the bound $$\mathbb{P}[|X_N - \mathbb{E}(A)| > \sigma] = \mathbb{P}[|X_N - \mathbb{P}(A)| > \sigma] \leq \frac{1}{\sigma^{2}}\mathbb{V}(X_N) = \frac{1}{\sigma^2}\mathbb{P}(A) - \mathbb{P}(A)^{2}$$

Now fix $$\sigma > 0$$. Since $$X^1 + \dots + X^N = \#\text{ Count of \omega's in A } \text{gotten in N tosses}$$, $$X_N$$ is the average and we can apply the weak law of large numbers to get $$\lim_{N \to \infty} \mathbb{P}[|X_N - \mathbb{P}\{X^{i} = 1 \}| > \sigma] = \lim_{N \to \infty} \mathbb{P}[|X_N - \mathbb{P}(A)| > \sigma] = 0.$$

Please let me know if this solution is total garbage! thanks.

• Shouldn't you have an $N$ remaining somewhere in the variance? Otherwise, why is the limit $0$? Commented Apr 29, 2021 at 0:44
• The variance of that average should be $\frac{Np(1-p)}{N^2}$ where $p=\mathbb{P}(A)$. So I think that is your mistake, you thought the division by $N$ would multiply the variance by $1/N$ but it actually multiplies it by $1/N^2$.
– Ian
Commented Apr 29, 2021 at 0:45

For, $$[|X_{N}-P(A)|>\sigma]$$ is a abbreviation of $$\{(\omega_{1},\ldots,\omega_{N})\in\Omega^{N}\mid|X_{N}(\omega_{1},\ldots,\omega_{N})-P(A)|>\sigma\},$$ which is a subset of $$\Omega^{N}$$. If $$B\subseteq\Omega^{N}$$, it is meaningless to talk about $$P(B)$$. Are you talking about $$(P\times\cdots\times P)(B)$$ instead?
• It is not just the issue of notation. It is about concept. What is the domain of $X_N$ ? If it is $\Omega^N$, then $[ |X_N - P(A)| >\sigma]$ must be a subset of $\Omega^N$. If $B$ is a subset of $\Omega^N$, how can we define $P(B)$ ? Commented Apr 29, 2021 at 0:56
• Just replace $\mathbb{P}$ by $\mathbb{P}^{\otimes N}$, for instance. Commented Apr 29, 2021 at 0:57