Law of Large Numbers

Comparing the bounds

• Markov only uses $\mathbb{E}[X]$. Loosest bound, often doesn't shrink with n for the sample mean.
• Chebyshev uses variance. Decays as $\frac{\sigma^2}{n\varepsilon^2}$, tighter but still polynomial.
• Hoeffding uses bounded range. Decays as $2e^{-2n\varepsilon^2 / R^2}$, exponentially fast. Only for bounded distributions.
• Chernoff uses the full moment generating function. Decays as $e^{-n I(\mu + \varepsilon)}$ where $I$ is the Cramér rate function. Tightest of the concentration bounds, and works for unbounded light-tailed distributions like the exponential.
• Berry-Esseen is a different kind of statement. It bounds how far the distribution of $M_n$ is from the normal approximation: $2(1-\Phi(\varepsilon\sqrt{n}/\sigma)) + \frac{2C\rho}{\sigma^3\sqrt{n}}$ with $\rho = \mathbb{E}|X-\mu|^3$ and $C \approx 0.4748$. The error term shrinks only as $1/\sqrt{n}$, so the band stays vacuous at high confidence until n is in the hundreds. It can beat Chebyshev for small ε but never catches the exponential bounds.
• $M_n \to \mu$ with probability 1 as $n \to \infty$. All bounds confirm this, at different speeds.