勉強材料

Canteli（カンテリ）の不等式

片側評価ならチェビシェフより優秀：

$X$ は実数値, $\lambda > 0$

Pr( X - E[X] \ge \lambda) \le \frac{\sigma^2}{\lambda^2 + \sigma^2}

片側評価だとチェビシェフより優れているが、両側評価だとチェビシェフのがマシらしい

なんやそれは

たとえ片側でも、 $\lambda=k\sigma$ とすると、チェビシェフと比較して $\frac{k^2}{k^2+1}$ 倍とかなので、近傍だとそこそこ改善するが遠方になるとチェビシェフとほぼ変わらんね。

読み方がわからん。単峰性を仮定することでチェビシェフより大幅に改善（約半減）：

$\lambda > \sqrt{\frac{8}{3}} = 1.63299.....$ のとき、

Pr(|X-E[X]| \ge \lambda \sigma) \le \frac{4}{9\lambda^2}

定番。期待値・分散が有限なら使えるが、使うほどでもないぐらいには粗い

Pr(|X-E[X]| \ge \lambda \sigma) \le \frac{1}{\lambda^2}

$X>0, a>0$ で、

Pr(X \ge a) \le \frac{E[X]}{a}

Markovの不等式の改善（？）版。 $X$ は負値まで拡張できているのがミソ。

$t > 0$ で

Pr(X \ge a) \le \frac{E[e^{tX}]}{e^{ta}}

一番大事そうなので、まずこれだけでも。

$X_1, ..., X_n$ を独立な確率変数とし、 $E[X_i]=0$ とする。各 $X_i$ に対して、ほとんど確実に $|X_i| \le M$ を満たすとき、すべての $t>0$ で以下が成り立つ：

Pr(|S_n| \ge t) \le \exp \left( - \frac{t^2}{2 (V_n + \frac{Mt}{3})} \right)

ただし、

\begin{split} S_n &:= \sum_{i=1}^n X_i \\ V_n &:= \sum_{i=1}^n E[X^2_i] = \sum_{i=1}^n Var[X_i] \end{split}

期待値が非ゼロな $X_i$ については、 $Z_i = X_i - E[X_i]$ と中心化して上記の式を適用すればよく：

$X_1, ..., X_n$ を独立な確率変数とし、ほとんど確実に $|X_i - E[X_i]| \le M$ を満たすとき、すべての $t>0$ で以下が成り立つ：

Pr(|S_n - E_n| \ge t) \le 2\exp \left( - \frac{t^2}{2 (V_n + \frac{Mt}{3})} \right)

ただし、

\begin{split} S_n &:= \sum_{i=1}^n X_i \\ E_n &:= \sum_{i=1}^n E[X_i] \\ V_n &:= \sum_{i=1}^n E[(X_i - E[X_i])^2] = \sum_{i=1}^n Var[X_i] \end{split}

特に $X_i$ たちが独立同分布だった場合、 $E[X_i]=\mu,~Var[X_i]=\sigma^2$ として、

Pr(|S_n - n \mu| \ge t) \le 2\exp \left( - \frac{t^2}{2 (n \sigma^2 + \frac{Mt}{3})} \right)

よって、

Pr(|\bar{X} - \mu| \ge t) \le 2\exp \left( - \frac{n t^2}{2 (\sigma^2 + \frac{Mt}{3})} \right)