あまり日本語で書いているネットの記事が多くなかったので確率不等式についてちょっとだけ書いてみます。この種のテーマはある程度手法自体は似通っているものの、どちらかというと技術的な話題のため、応用に応じて適切なものを選んでいくことが必要なので、散在的な話題になりがちで書きにくいというのはあるんですかね。とはいうものの1本目に書くこの内容については、確率不等式を使っていくならマストだろうという感じですがね。
Markovの不等式
確率不等式のすべての出発点はこのMarkovの不等式でしょう。なお、これをChebyshevの不等式という文献もあるみたいです。
定理1(Markov の不等式)
\(X\) を非負値確率変数, \(a>0\) とする. このとき,
\[\Pr[X\geq a]\leq\frac{\mathbb{E}[X]}{a}\]
が成立する.
証明
\[\mathbb{E}[X]\geq\mathbb{E}[X1_{\{X\geq a\}}]\geq a\Pr[X\geq a]\]
より従う.
証明を見れば分かるとおり、等号成立条件は \(X\) がほとんど確実に定数関数になっていることです。さらに \(a\) に比べてやたらデカい値を \(X\) がとる場合には評価としては使い物にならなさそうなことが分かると思います。
例
\(X\) が平均 \(1\) の指数分布, すなわち密度関数が \(f_X(x)=e^{-x}1_{[0,\infty)}\) で与えられるような分布を持つとしよう. このとき, Markovの不等式を適用して, \(X\geq n\) なる確率を評価すると,
\[\Pr[X\geq n]\leq\mathbb{E}[X]/n=\frac{1}{n}\]
となるが, 実際には \(\Pr[X\geq n]=e^{-n}\) より実際の値に比べて Markovの不等式が示唆する上限は指数的に悪い.
ですが、Markov の不等式はここからの議論の出発点にはなり得ます。重要な工夫は、非負値関数 \(\psi:\mathbb{R}\to\mathbb{R}\) が与えられたときに、実確率変数 \(X\) と実数 \(a\in\mathbb{R}\) に対して、\(\psi(a)>0\) である限り、Markov の不等式から
\[\Pr[X\geq a]\leq\Pr[\psi(X)\geq\psi(a)]\leq\psi(a)^{-1}\mathbb{E}[\psi(X)]\]
が成立するということです。例えば二乗可積分確率変数 \(X\) と \(\varepsilon>0\) に対して、\(\psi(x)=(x-\mathbb{E}[X])^2\) として上記の考察を適用すれば、有名な Chebyshevの不等式
\[\Pr[|X-\mathbb{E}[X]|\geq\varepsilon]\leq\frac{\mathrm{Var}[X]}{\varepsilon^2}\]
が得られます。
モーメント母関数
一般には Markov の不等式よりも Chebyshev の不等式の方が評価は良いことが多いです。これは結局のところある分布が高次のモーメントをもてばもつほど、その分布は裾野において急減少するため、高次のモーメントを利用した方が裾野を評価するにあたってより強い情報をもたらしてくれるということに他なりません。そこですべての次数のモーメントを利用する方法としてモーメント母関数を導入しましょう。
定義2 モーメント母関数
実確率変数 \(X\) に対するモーメント母関数(Moment Generating Function, MTG) \(M_X(\lambda)\) とは,
\[M_X(\lambda)=\mathbb{E}[e^{\lambda X}]\]
で定義される関数のことである.
まず簡単に性質を紹介しておきます。まずモーメント母関数は \(0\) を含む凸集合上で定義され、定義域上では常に正の値をとります。しかし、一方でモーメント母関数の定義域についてこれ以上のことを言うことはできません。
また、\(X_1,\ldots,X_n\) が独立であれば、Fubiniの定理から
\[M_{X_1+\cdots+X_n}(\lambda)=M_{X_1}(\lambda)M_{X_2}(\lambda)\cdots M_{X_n}(\lambda)\]
と和のモーメント母関数はもとのモーメント母関数の積の形になります。なお、左辺と右辺のすべての項が定義されることは同値であることに注意しておきます。
いくつか例を計算してみましょう。
例 (正規分布)
平均 \(\mu\), 分散 \(\sigma^2\) の正規分布に従う確率変数 \(X\) に対して, そのモーメント母関数は,
\[M_X(\lambda)=\exp\left(\mu\lambda+\frac{\sigma^2\lambda^2}{2}\right)\]
で与えられる. 定義域は実数全体である.
例 (カイ二乗分布)
自由度 \(n\) のカイ二乗分布とは, 独立に標準正規分布に従う確率変数 \(Z_1,\ldots,Z_n\) があったときに,
\[X=Z_1+Z_2+\cdots+Z_n\]
が従う分布である. その密度関数は
\[f_X(x)=\frac{1}{2^{n/2}\Gamma(n/2)}x^{n/2-1}e^{-x/2}1_{(0,\infty)}(x)\]
で与えられることに注意すれば, モーメント母関数は
\[M_X(\lambda)=\left(\frac{1}{1-2\lambda}\right)^{n/2}\]
となり、その定義域は \((-\infty,1/2)\) となる。
例
確率変数 \(X\) をその密度関数が
\[f_X(x)=\begin{cases} C\frac{e^{-|x|}}{x^2} & (|x|\geq 1)\\ 0 & (|x|<1)\end{cases}\]
で与えられるものとする. ここで \(C>0\) は正規化定数である. すると, モーメント母関数の定義域は \([-1,1]\) になる.
Cramer-Chernoff 不等式
以下、確率変数 \(X\) が \(D\subset\mathbb{R}\) 上でモーメント母関数 \(M_X(\lambda )\) をもつとします。このとき
\[\psi_X(t)=\sup_{\lambda\in [0,\infty)\cap D}(\lambda t – \log M_X(\lambda))\]
とおきます。
定理3 (Cramer-Chernoff 不等式)
任意の t > 0 に対して,
\[\Pr[X\geq t]\leq\exp(-\psi_X(t))\]
が成立する.
証明
Markov の不等式から, \(\lambda\in[0,\infty)\cap D\) に対して,
\[\Pr[X\geq t]=\Pr[e^{\lambda X}\geq e^{\lambda t}]\leq e^{-\lambda t}\mathbb{E}[e^{\lambda X}]\]
となるので, \(\lambda\) に渡って上限をとると所望の結論を得る.
Cramer-Chernoff 不等式を用いると, 非常にタイトな評価を得ることができます。
例 (正規分布)
\(X\) が正規分布に従うとき, Chernoff 不等式を適用すると,
\[\Pr[X-\mathbb{E}[X]\geq t]\leq \exp(-\sup_{\lambda>0}(\lambda t -\frac{\lambda^2\sigma^2}{2}))=e^{-\frac{\lambda^2}{2\sigma^2}}\]
となる.
