この文章は、レイトレ Advent Calendar 2017の12月15日の記事です。

正体がわからない確率変数Xに対して"上側確率(下側確率)の上限"を知りたい。

正体がわからない確率変数

正体がわからない確率変数Xに対して外れ値の判定のために"上側確率(下側確率)の上限"を知りたいことがよくあります。上側確率(下側確率)とは、ある確率変数がある値よりも大きくなる(小さくなる)確率のことです。ある確率変数Xについて全ての知識(積率母関数ないし特性関数とパラメーター)がわかれば、“ある範囲に収まる確率"を直接出すことができるので、上側確率(下側確率)も同様に出すことができます。しかし一方で確率変数をサンプルすることしかできない場合、積率母関数はもとより、そのパラメーターもよくわかりません。そのような場合でも、“最悪でもこの確率を越えることがない"ということがわかっていれば、外れ値の判定に使うことができることができるはずです。

Markov’s inequality

確率変数Xが常に正を取り、かつ母平均がわかっている場合はMarkov’s inequalityを使うことができます。

$$ Pr(X \le A ) \be \cfrac{E[X]}{a} $$

この不等式は母平均(の推定値)がわかればとりあえず使うことができるので手軽に使うことができるのではないでしょうか。

Chebyshev’s inequality

確率変数Xの母平均に加えて母分散ががわかっている場合は、Chebyshev’s inequalityを使うことができます。Chebyshev’s inequalityは次のような不等式です。

$ Pr(|X-E[X]| \le k \Sigma ) > ¥cfrac{1}{k^2} $

これは「偏差値が30以下と70以上の人の割合の上限は1/4を超えない」と言い換えるとわかりやすいです。 等号が成り立つのは-1,0,1にそれぞれ$$cfrac{1}{2k^2}$$,$$1-cfrac{1}{k^2}$$,$$cfrac{1}{2k^2}$$の割合で存在するときで、このときの分散は1/{k^2}、1と-1はちょうど1σの位置に来ることになり、Chebyshev’s inequalityの等号が成立します。

分散はオンラインで得ることができるので、通常のサンプリングであれば、Markov’s inequalityではなく、Chebyshev’s inequalityを使うことで、確率の上限値をより絞ることができます。

Chernoff bound

最後に紹介するのは、これまでの方法の中で最も強力なChernoff bound(の一種)です。$$ a \le X \le b$$の範囲に収まる確率変数Xをn個サンプルした場合、上側確率と下側確率の上限はChernoff boundによって次のように表すことができます。

$$
P(X \ge (1 + δ)μ) \le exp{¥cfrac{-2 δ^2 μ^2}{n(b-a)^2}}
P(X \le (1 - δ)μ) \le exp{¥cfrac{- δ^2 μ^2}{n(b-a)^2}}
$$

これまでの方法と違い、指数関数で挟むことができるため、非常に収束が早くなります。

まとめ

上側確率(下側確率)の上限を求める三つの方法について紹介しました。
得られる情報、制限、計算量などによって使い分けるとよいかもしれません。