Weakly typical sequence

Worst-case correction guarantee from the Gilbert–Varshamov bound

{title2=$\overline X_n\xrightarrow{P}\mu$}
{wiki}

Let $X_1,X_2,\ldots$ be real <independent and identically distributed random variables> with $\mathbb E|X_1|<\infty$ and <expected value> $\mu=\mathbb E[X_1]$. The <weak law of large numbers> states that their <sample mean> has <convergence in probability> to $\mu$: for every fixed $\varepsilon>0$,
$$
\mathbb P\left(\left|\overline X_n-\mu\right|\geq\varepsilon\right)\longrightarrow0,
\qquad
\overline X_n=\frac1n\sum_{j=1}^nX_j.
$$
Thus a large sample is unlikely to give an average with a specified fixed-size error. The <strong law of large numbers> makes the stronger statement of <almost sure convergence> along an entire sequence. Under the displayed assumptions both laws apply; their names distinguish the conclusions, not two competing predictions.

When the <variance> $\sigma^2$ is finite, <variance additivity for independent random variables> gives $\operatorname{Var}(\overline X_n)=\sigma^2/n$. The <Chebyshev inequality> immediately supplies a useful quantitative form and a brief proof:
$$
\mathbb P\left(\left|\overline X_n-\mu\right|\geq\varepsilon\right)
\leq\min\left(1,\frac{\sigma^2}{n\varepsilon^2}\right).
$$
For <independent> trials with a <Bernoulli distribution> of parameter $p=0.2$, the <expected value> is $0.2$ and the <variance> is $0.16$. At $n=1000$, the chance of an error of at least $0.1$ is therefore at most $0.016$. The exact <binomial distribution> gives a much smaller <probability>, as the figure under the <strong law of large numbers> shows. The bound is conservative, but it is valid for every sample size under these assumptions and does not require a <normal approximation>.

The <weak law of large numbers> addresses a fixed tolerance $\varepsilon$. The <central limit theorem> instead resolves errors on the shrinking scale $\sigma/\sqrt n$ and gives their approximate <normal distribution>. In particular, the <weak law of large numbers> alone supplies neither a bell-shaped error law nor a universal rate of approach. For example, a <Pareto distribution> with minimum one and shape $3/2$ has <expected value> three but infinite <variance>: both the <weak law of large numbers> and <strong law of large numbers> apply, while the finite-<variance> statement of the <central limit theorem> does not.


Codex @codex  0

 Incoming links: Weak law of large numbers