Law of Large Numbers for Discrete Variables

Definition Let $X_1, X_2, \dots$ have common mean $\mu$, and let $\bar{X}_n$ be the mean of the first $n$ of them. An error tolerance is a fixed number $\varepsilon > 0$, in the units of the observations, that marks the distance from $\mu$ at which a miss begins. The sample mean misses by at least the tolerance on the event $\{\lvert \bar{X}_n - \mu \rvert \ge \varepsilon\}$ and is within tolerance on its complement $\{\lvert \bar{X}_n - \mu \rvert < \varepsilon\}$. In the law of large numbers $\varepsilon$ is chosen first and stays fixed while $n$ grows.

Definition A sequence of random variables $Y_1, Y_2, \dots$ converges in probability to a constant $c$ if for every $\varepsilon > 0$

Each probability in the sequence is computed at a single $n$, so the definition is a statement about a sequence of numbers. It makes no claim about the values along one observed run.

Definition Let $X_1, X_2, \dots$ be IID discrete random variables with finite mean $\mu$ and finite variance $\sigma^2$. Then for every $\varepsilon > 0$ and every $n \ge 1$

and therefore $\bar{X}_n$ converges in probability to $\mu$. The proof uses $E[\bar{X}_n] = \mu$ and $\operatorname{Var}(\bar{X}_n) = \sigma^2/n$, then Chebyshev’s inequality with distance $\varepsilon$. With $\sigma^2$ and $\varepsilon$ fixed, the right side tends to $0$ as $n \to \infty$, and a probability between $0$ and that bound tends to $0$ as well. Independence enters only through the variance formula, which needs the covariances to vanish. The conclusion also holds for IID variables with a finite mean and infinite variance, but that case needs a different proof.

Definition Let an experiment be repeated independently, let $A$ be an event with $P(A) = p$, and let $X_i$ be the indicator of $A$ on trial $i$. The $X_i$ are IID $\operatorname{Bernoulli}(p)$ with mean $p$ and variance $p(1 - p)$. If $K$ counts the trials among the first $n$ on which $A$ occurs, the relative frequency of $A$ is $\bar{X}_n = K/n$. The weak law gives, for every $\varepsilon > 0$,

where the last step uses $p(1 - p) \le \tfrac14$. So $K/n$ converges in probability to $p$. A relative frequency in finitely many trials is a random variable, while $p$ is a fixed model probability.

Definition Let $X_1, X_2, \dots$ be IID with mean $\mu$ and finite variance $\sigma^2 > 0$, and fix a tolerance $\varepsilon > 0$ and a target probability $\delta$ with $0 < \delta < 1$. Chebyshev’s bound $\sigma^2/(n\varepsilon^2)$ is at most $\delta$ exactly when

and every such $n$ guarantees $P(\lvert \bar{X}_n - \mu \rvert \ge \varepsilon) \le \delta$. The smallest whole number that satisfies the condition is the right side rounded up. Such an $n$ is sufficient, but it need not be the smallest sample size with miss probability at most $\delta$, because the exact probability can drop below $\delta$ at a much smaller $n$. Halving $\varepsilon$ with $\delta$ fixed multiplies the right side by $4$.

Definition For IID observations with mean $\mu$ and finite variance $\sigma^2$, the sample mean at a fixed sample size $n$ is still a random variable, with variance $\sigma^2/n$. When $\sigma^2 > 0$ this variance is positive, so $\bar{X}_n \ne \mu$ with positive probability. The weak law bounds the probability of a miss of a given size without ruling the miss out. It is a statement about the probabilities at each $n$, so it does not say that the observed averages along one run move closer to $\mu$ at every step, and it does not make later outcomes compensate for earlier ones.