<commit_before>---
layout: article
title: "Law of large numbers"
categories: study
comments: true
image:
  feature: Stanford-University-1600x500.jpg
---

This is a blog discussing the Law of large numbers (LLN) and proof with characteristic function.

In probability theory, law of large numbers describes the asymptotic behavior of the empirical average of the independent and identically distributed (i.i.d.) random variables converging towards the expectation as number of sample grows.

Consider a sequence of i.i.d. random variables $\color{black}{X_i}$ with mean $\color{black}{\mu = E\left[{X}\right]}$, the law of large numbers comes in two forms, one weak law and one strong law as follows

### Weak law

The weak law of large numbers states that the sample average converges in probability towards the expected value. That is for $\color{black}{\forall \epsilon > 0}$,

$$\begin{equation}
\begin{split}
\color{black}
{\lim_{n \rightarrow \infty}Pr \left( \left| \hat{\mu}_n - \mu \right| \leq \epsilon \right) = 1 .}
\end{split}
\end{equation}$$

In another notation, it is expressed as when $\color{black}{n \rightarrow \infty}$,

$$\begin{equation}
\begin{split}
\color{black}
{\hat{\mu}_n \overset{P}{\rightarrow} \mu,}
\end{split}
\end{equation}$$

where $\color{black}{\overset{P}{\rightarrow}}$ is called convergence in probability. What weak law represents is that as size of sample grows to infinity, the probability that the empirical average $\color{black}{\hat{\mu}_n}$ is within the $\color{black}{\epsilon}$ neighborhood of the expectation $\color{black}{\mu}$ goes to $\color{black}{1}$. In other words, weak law does not guarantee that $\color{black}{\hat{\mu}_n}$ is always within the $\color{black}{\epsilon}$ neighborhood of the expectation $\color{black}{\mu}$. For instance,
it can be the case that for  most of time $\color{black}{\hat{\mu}_n}$ converges to $\color{black}{\mu}$, but with very small probability $\color{black}{\hat{\mu}_n}$ deviates from $\color{black}{\mu}$ and the deviation can keep on increasing.

### Strong law

The strong law of large numbers, instead, states that the sample average converges almost surely to the expected value. Namely

$$\begin{equation}
\begin{split}
\color{black}
{Pr \left( \lim_{n \rightarrow \infty} {\hat{\mu}_n = \mu}\right) = 1 .}
\end{split}
\end{equation}$$

It is sometimes also written as when $\color{black}{n \rightarrow \infty}$,

$$\begin{equation}
\begin{split}
\color{black}
{\hat{\mu}_n \overset{a.s.}{\rightarrow} \mu},
\end{split}
\end{equation}$$

where $\color{black}{\overset{a.s.}{\rightarrow}}$ is called almost sure convergence. What strong law represents is that the probability that the empirical average $\color{black}{\hat{\mu}_n}$ is equal to the expectation $\color{black}{\mu}$ will be equal to $\color{black}{1}$ as the number of sample goes to infinity. In other words, the strong law prevents the occurrence of deviation from happening when $\color{black}{n}$ is sufficiently large.

### Proof of weak law using characteristic function

Here I provide the proof of weak law of large numbers using characteristic function discussed in [last post](https://alex8937.github.io/study/From-Fourier-transform-to-Characteristic-function/). For anyone who is interested in the proof of strong law, please check [here](https://www.math.ucdavis.edu/~tracy/courses/math135A/UsefullCourseMaterial/lawLargeNo.pdf).

In order to prove the weak law, let us introduce [Lévy's continuity theorem](https://en.wikipedia.org/wiki/L%C3%A9vy%27s_continuity_theorem). That is if for $\color{black}{\forall t}$

$$\begin{equation}
\begin{split}
\color{black}
{\lim_{n \rightarrow \infty}{\phi}_{X_{n}}(t) = {\phi}_{X}(t)  }
\end{split}
\end{equation}$$

then $\color{black}{\phi_{X_{n}}(t)}$ converges to $\color{black}{\phi_{X}(t)}$ in probability. Then, to prove the weak law of large numbers becomes equivalent to show

$$\begin{equation}
\begin{split}
\color{black}
{\lim_{n \rightarrow \infty}{\phi}_{\hat{\mu}_{n}}(t) = {\phi}_{\mu}(t)  .}
\end{split}
\end{equation}$$

where the random variable of empirical average $\color{black}{\hat{\mu}_{n}}$ is defined as

$$\begin{equation}
\begin{split}
\color{black}
{\hat{\mu}_{n} = \frac{1}{n}\sum_{i=1}^{n} X_i =\sum_{i=1}^{n} \frac{X_i}{n}}
\end{split}
\end{equation}$$

Due to the fact of each random variable $\color{black}{X_i}$ being i.i.d. drawn from the same probability distribution with $\color{black}{\mu = E\left[{X}\right]}$, the characteristic function of $\color{black}{\hat{\mu}_{n}}$ is then<commit_msg>-amend<commit_after>---
layout: article
title: "Law of large numbers"
categories: study
comments: true
image:
  feature: Stanford-University-1600x500.jpg
---

This is a blog discussing the Law of large numbers (LLN) and proof with characteristic function.

In probability theory, law of large numbers describes the asymptotic behavior of the empirical average of the independent and identically distributed (i.i.d.) random variables converging towards the expectation as number of sample grows.

Consider a sequence of i.i.d. random variables $\color{black}{X_i}$ with mean $\color{black}{\mu = E\left[{X}\right]}$, the law of large numbers comes in two forms, one weak law and one strong law as follows

### Weak law

The weak law of large numbers states that the sample average converges in probability towards the expected value. That is for $\color{black}{\forall \epsilon > 0}$,

$$\begin{equation}
\begin{split}
\color{black}
{\lim_{n \rightarrow \infty}Pr \left( \left| \hat{\mu}_n - \mu \right| \leq \epsilon \right) = 1 .}
\end{split}
\end{equation}$$

In another notation, it is expressed as when $\color{black}{n \rightarrow \infty}$,

$$\begin{equation}
\begin{split}
\color{black}
{\hat{\mu}_n \overset{P}{\rightarrow} \mu,}
\end{split}
\end{equation}$$

where $\color{black}{\overset{P}{\rightarrow}}$ is called convergence in probability. What weak law represents is that as size of sample grows to infinity, the probability that the empirical average $\color{black}{\hat{\mu}_n}$ is within the $\color{black}{\epsilon}$ neighborhood of the expectation $\color{black}{\mu}$ goes to $\color{black}{1}$. In other words, weak law does not guarantee that $\color{black}{\hat{\mu}_n}$ is always within the $\color{black}{\epsilon}$ neighborhood of the expectation $\color{black}{\mu}$. For instance,
it can be the case that for  most of time $\color{black}{\hat{\mu}_n}$ converges to $\color{black}{\mu}$, but with very small probability $\color{black}{\hat{\mu}_n}$ deviates from $\color{black}{\mu}$ and the deviation can keep on increasing.

### Strong law

The strong law of large numbers, instead, states that the sample average converges almost surely to the expected value. Namely

$$\begin{equation}
\begin{split}
\color{black}
{Pr \left( \lim_{n \rightarrow \infty} {\hat{\mu}_n = \mu}\right) = 1 .}
\end{split}
\end{equation}$$

It is sometimes also written as when $\color{black}{n \rightarrow \infty}$,

$$\begin{equation}
\begin{split}
\color{black}
{\hat{\mu}_n \overset{a.s.}{\rightarrow} \mu},
\end{split}
\end{equation}$$

where $\color{black}{\overset{a.s.}{\rightarrow}}$ is called almost sure convergence. What strong law represents is that the probability that the empirical average $\color{black}{\hat{\mu}_n}$ is equal to the expectation $\color{black}{\mu}$ will be equal to $\color{black}{1}$ as the number of sample goes to infinity. In other words, the strong law prevents the occurrence of deviation from happening when $\color{black}{n}$ is sufficiently large.

### Proof of weak law using characteristic function

Here I provide the proof of weak law of large numbers using characteristic function discussed in [last post](https://alex8937.github.io/study/From-Fourier-transform-to-Characteristic-function/). For anyone who is interested in the proof of strong law, please check [here](https://www.math.ucdavis.edu/~tracy/courses/math135A/UsefullCourseMaterial/lawLargeNo.pdf).

In order to prove the weak law, let us introduce [Lévy's continuity theorem](https://en.wikipedia.org/wiki/L%C3%A9vy%27s_continuity_theorem). That is if for $\color{black}{\forall t}$

$$\begin{equation}
\begin{split}
\color{black}
{\lim_{n \rightarrow \infty}{\phi}_{X_{n}}(t) = {\phi}_{X}(t)  }
\end{split}
\end{equation}$$

then $\color{black}{X_{n}(t)}$ converges to $\color{black}{X(t)}$ in probability. Then, to prove the weak law of large numbers becomes equivalent to show

$$\begin{equation}
\begin{split}
\color{black}
{\lim_{n \rightarrow \infty}{\phi}_{\hat{\mu}_{n}}(t) = {\phi}_{\mu}(t)  .}
\end{split}
\end{equation}$$

where the random variable of empirical average $\color{black}{\hat{\mu}_{n}}$ is defined as

$$\begin{equation}
\begin{split}
\color{black}
{\hat{\mu}_{n} = \frac{1}{n}\sum_{i=1}^{n} X_i =\sum_{i=1}^{n} \frac{X_i}{n}}
\end{split}
\end{equation}$$

Due to the fact of each random variable $\color{black}{X_i}$ being i.i.d. drawn from the same probability distribution with $\color{black}{\mu = E\left[{X}\right]}$, the characteristic function of $\color{black}{\hat{\mu}_{n}}$ is then
{'fraction_non_alphanumeric': 0.15623969213853767, 'fraction_numerical': 0.005717427157779, 'mean_word_length': 4.906493506493507, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 6, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3861884', 'n_tokens_mistral': 2759, 'n_tokens_neox': 2627, 'n_words': 1001}