大数の法則
独立・同分布な$ n個の確率変数の平均は$ n \rightarrow \inftyでその分布の平均に収束するという法則。
$ x_1, x_2, \ldots, x_nを、確率変数$ xの$ n個の独立なサンプルとする。
このとき、任意の非負の実数 $ \varepsilonに対して次式が成り立つ。
$ \lim_{n \rightarrow \infty} \mathrm{Pr}\left( \left| \frac{x_1 + x_2 + \cdots + x_n}{n} - E[x] \right| \ge \varepsilon \right) = 0
解釈: $ \left| \frac{x_1 + x_2 + \cdots + x_n}{n} - E[x] \right| の部分は、サンプルの平均と確率分布の平均の誤差を表している。$ \varepsilon がどんなに小さい場合でも、サンプル数$ nを十分大きくすれば、誤差がほぼ確実に$ \varepsilon以内に収まるということを、この定理は主張している。
$ \mathrm{Pr}\left( \left| \frac{x_1 + x_2 + \cdots + x_n}{n} - E[x] \right| \ge \varepsilon \right)
$ \frac{\le \mathrm{Var}\left[(x_1 + x_2 + \cdots + x_n) / n\right]}{\varepsilon^2}
$ = \frac{\mathrm{Var}[x_1 + x_2 + \cdots + x_n]}{n^2 \varepsilon^2}
$ = \frac{\mathrm{Var}[x_1] + \mathrm{Var}[x_2] + \cdots + \mathrm{Var}[x_n]}{n^2 \varepsilon^2}
$ = \frac{\mathrm{Var}[x]}{n \varepsilon^2}
※$ x_1, x_2, \ldots x_n は互いに独立なので、$ \mathrm{Var}[x_1 + x_2 + \cdots + x_n] = \mathrm{Var}[x_1] + \mathrm{Var}[x_2] + \cdots + \mathrm{Var}[x_n] が成り立つことを使った。
よって、$ n \rightarrow \infty とすると
$ \mathrm{Pr}\left( \left| \frac{x_1 + x_2 + \cdots + x_n}{n} - E[x] \right| \ge \varepsilon \right) \le \frac{\mathrm{Var}[x]}{n \varepsilon^2} \rightarrow 0
が得られる。