1. 前置き
調べ物をしているときにChernoffの不等式というのが登場して、調べてみるとまとまった日本語の資料がネットになさそうだったので書くことにした。どうもいろいろな不等式がChernoffの不等式と呼ばれているようで、どれが本当なのかよくわからないので、とりあえず自分が必要だったChernoff 不等式の導出をまとめる。
2. Markov bound
Chernoffの不等式の導出には、有名なMarkovの不等式を使う。
Markov の不等式
: 0以上の実数値をとる確率変数\(X\)の期待値を\(E(X)\)と書く。\(X\)がある実数\(a\)以上である確率は、以下の不等式で抑えられる。
\[P(X\geq a) \leq \frac{E(X)}{a} \tag{0}\]
証明は検索すればでてくると思うが、短いのでここでも書いておこう。以下証明。確率変数は離散値を取るとする。
\begin{align}
P(X\geq a) &= \sum_{x\geq a} P(X=x) \\
&\leq \sum_{x\geq a} \frac{x}{a} P(X=x)\\
&= \frac{1}{a} \sum_{x\geq a} x P(X=x)\\
&\leq \frac{1}{a} \sum_{x} x P(X=x)\\
&= \frac{E(X)}{a}
\end{align}
以上。一行目から二行目は\(x/a \geq 1\)であることを使った。
3. Chernoff bound (1)
Chernoff の不等式といったとき、次の形が最も一般的な形と思われる。
Chernoffの不等式 (1)
: 実数値をとる確率変数\(X\)がある実数\(a\)以上である確率は、任意の実数\(t\gt 0\)について以下の不等式で抑えられる。
\[\left\{\begin{align}
P(X\geq a) &\leq \frac{E(e^{tX})}{e^{ta}} \\
P(X\leq a) &\leq \frac{E(e^{-tX})}{e^{-ta}}
\end{align}\right.\tag{1}\]
これはMarkovの不等式を使えば簡単に示せる。なぜなら、
\[P(X\geq a) = P(e^{tX}\geq e^{ta})\]
なので、この右辺にMarkovの不等式(0)を適用して、
\[P(X\geq a) \leq \frac{E(e^{tX})}{e^{ta}}\]
を得る。逆の不等式も同様に
\[P(X\leq a) = P(e^{-tX}\geq e^{-ta})\]
を使えばよい。
4. Chernoff bound (2)
上の不等式を互いに独立な確率変数\(\{X_k\}\)の和\(X=\sum_k X_k\)に適用してみよう。
\begin{align}
P(X\geq a) &\leq \frac{E(e^{tX})}{e^{ta}} \\
&= e^{-ta}E\left(\exp\left(t\sum_k X_k\right)\right) \\
&= e^{-ta}E\left(\prod_k e^{tX_k}\right) \\
&= e^{-ta}\prod_k E\left(e^{tX_k}\right)
\end{align}
これは任意の実数\(t\)について成り立つべき不等式なので、不等式が最も強くなるのは、\(e^{-ta}\prod_k E\left(e^{tX_k}\right)\)が最小となる\(t\)を使ったときである。\(P(X\leq a)\)についても同じような不等式が示せるなことはすぐに分かるだろう。そこで以下が成り立つ。
Chernoffの不等式 (2)
: \(\{X_k\}\)を実数値をとる互いに独立な確率変数とし、その和を\(X=\sum_k X_k\)とする。このとき
\[\left\{\begin{align}
P(X\geq a) &\leq \min_{t\gt 0}e^{-ta}\prod_k E\left(e^{tX_k}\right) \\
P(X\leq a) &\leq \min_{t\gt 0}e^{ta}\prod_k E\left(e^{-tX_k}\right)
\end{align}\right.\tag{2}\]
5. Chernoff bound (3)
上の不等式(2)の具体的な応用先として、それぞれの\(X_k\)が\(\{0,1\}\)のどちらかをとる確率変数である場合を考え、その和\(X\)が平均からすれる確率
\[P(X\geq (1+\delta)E(X)),~P(X\leq (1-\delta)E(X))\]
を評価してみよう。(\(\delta\)は正の実数)同分布である場合を取り上げても良いのだが、ここではそれよりも、それぞれの分布が異なる場合を考えることにして、\(P(X_k = 1) = p_k\), \(P(X_k=0) = 1-p_k\)とする。
この場合、
\begin{align}
e^{tX_k} &= p_k e^t + (1-p_k) \\
&= 1 + p_k (e^t-1)
\end{align}
なので、
\begin{align}
P(X\geq a) &\leq \min_{t\gt 0}e^{-ta}\prod_k \left(1 + p_k (e^t-1)\right)
\end{align}
を得る。ここで最小を与える\(t\)を見つけるのも良いが、もう少し簡単な形に変形してからにしよう。\(\prod_k\)というのが曲者なので、右辺を
\[1 + p_k (e^t-1) \leq \exp\left(p_k (e^t-1)\right)\]
と指数関数で抑えてやると、
\begin{align}
P(X\geq a) &\leq \min_{t\gt 0}e^{-ta}\prod_k \exp\left(p_k (e^t-1)\right) \\
&= \min_{t\gt 0}e^{-ta}\exp\left(\sum_k p_k (e^t-1)\right)
\end{align}
ここで\(\sum_k p_k\)は\(X\)の期待値\(E(X)\)そのものなので、
\begin{align}
P(X\geq a) &\leq \min_{t\gt 0}e^{-ta}\exp\left(E(X) (e^t-1)\right) \\
&= \min_{t\gt 0}\exp\left(E(X)(e^t-1) - ta\right)
\end{align}
ここまで変形すると、右辺がとても簡単な関数になった。最小値を与える\(t\)を見つけるには、右辺の微分を考えてやればよくて
\[\frac{d}{dt}\left(E(X)(e^t-1) - ta\right) = E(X)e^t - a\]
したがって \(t = \log a/E(X)\) が最小値を与える\(t\)である。つまり
\[P(X\geq a) \leq \exp\left( a - E(X) - a \log \frac{a}{E(X)}\right)\]
を得る。もともと評価したかったのは \(P(X\geq (1+\delta)E(X))\) だったので、\(a=(1+\delta)E(X)\)を代入すれば、
\begin{align}
P(X\geq (1+\delta)E(X)) &\leq \exp\left( \delta E(X) - (1+\delta) E(X) \log (1+\delta) \right) \\
\end{align}
逆側も同じような式変形によって、同様の不等式が得られるので、以下が成り立つ
Chernoffの不等式 (3)
: \(\{X_k\}\)を\(\{0,1\}\)をとる互いに独立な確率変数、\(P(X_k = 1) = p_k\), \(P(X_k=0) = 1-p_k\)、その和を\(X=\sum_k X_k\)とする。このとき
\[\left\{\begin{align}
P(X\geq (1+\delta)E(X)) &\leq \left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{E(X)} ~~~ (\delta \geq 0)\\
P(X\leq (1-\delta)E(X)) &\leq \left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{E(X)} ~~~ (0 \leq \delta \lt 1)
\end{align}\right.\tag{3}\]
右辺の
\[\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\]
という関数は、分子は期待値からのズレ\(\delta\)に関する指数関数、分母は\(\delta^\delta\)の形でただの指数関数よりも十分早く大きくなりそうだ。実は右辺は簡単な指数関数で抑えることができる。それを次にやろう。
6. Chernoff bound (4)
(3)の不等式を使いやすい形にするために、右辺を指数関数で抑える。そこで利用するのは次の不等式である。
\begin{align}
\log (1+x) &\geq \frac{x}{1+\frac{x}{2}} ~~ (x\geq 0)\\
\log (1+x) &\geq \frac{x}{\sqrt{x+1}} ~~ (-1\lt x\leq 0)
\end{align}
この不等式は微分などで簡単に示せる。
\(x\geq 0\)の不等式を\(P(X\geq (1+\delta)E(X))\)の評価に使ってみよう。(3)の不等式から、
\begin{align}
P(X\geq (1+\delta)E(X)) &\leq \left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{E(X)} \\
&= \exp\left( \delta E(X) - (1+\delta) E(X) \log (1+\delta) \right) \\
&\leq \exp\left( \delta E(X) - (1+\delta) E(X) \frac{\delta}{1+\frac{\delta}{2}} \right) \\
&= \exp\left( \frac{(2+\delta)\delta - 2(1+\delta)\delta}{2+\delta} E(X) \right) \\
&= \exp\left(-\frac{\delta^2}{2+\delta} E(X) \right)
\end{align}
を得る。またもう一つのほうは、\(P(X\geq (1-\delta)E(X))\)の評価につかえて、
\begin{align}
P(X\leq (1-\delta)E(X)) &\leq \left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{E(X)} \\
&= \exp\left( -\delta E(X) - (1-\delta) E(X) \log (1-\delta) \right) \\
&\leq \exp\left( -\delta E(X) + (1-\delta) E(X) \frac{\delta}{\sqrt{1-\delta}} \right) \\
&= \exp\left( \left(-\delta + \delta\sqrt{1-\delta}\right) E(X) \right)
\end{align}
さらに\(\sqrt{1-\delta} \leq 1-\frac{\delta}{2}\)を使うと
\begin{align}
P(X\leq (1-\delta)E(X)) &\leq \exp\left( -\frac{\delta^2}{2} E(X) \right)
\end{align}
を得る。まとめると
Chernoffの不等式 (4)
: \(\{X_k\}\)を\(\{0,1\}\)をとる互いに独立な確率変数、\(P(X_k = 1) = p_k\), \(P(X_k=0) = 1-p_k\)、その和を\(X=\sum_k X_k\)とする。このとき
\[\left\{\begin{align}
P(X\geq (1+\delta)E(X)) &\leq \exp\left(-\frac{\delta^2}{2+\delta} E(X) \right) ~~~ (\delta \geq 0)\\
P(X\leq (1-\delta)E(X)) &\leq \exp\left(-\frac{\delta^2}{2} E(X)\right) ~~~ (0 \leq \delta \lt 1)
\end{align}\right.\tag{3}\]
7. 使いどころ
例えば、簡単に、\(\{X_k\}\)を\(n\)個の同分布な\(\{0,1\}\)をとる互いに独立な確率変数、\(P(X_k = 1) = p\), \(P(X_k=0) = 1-p\)であるとしよう。このとき
\[E(X) = np\]
なので
\[P(X\leq (1-\delta)np) \leq \exp\left(-\frac{\delta^2}{2} np\right)\]
である。\(\delta\)は\(0 \leq \delta \lt 1\)でありさえすればよかったので、\(\delta = n^{-\gamma}\) \(\gamma\gt 0\)のように\(n\)の関数として\(\delta\)をとっても良い。これを使うと、
\[P(X\leq (n-n^{1-\gamma})p) \leq \exp\left(-\frac{p}{2} n^{1-2\gamma}\right)\]
となって、\(\gamma \lt 1/2\)であれば、少しずつ期待値からのズレを増やしていっても、指数関数的に確率が0に近づいて行くことがわかったりする。
もっとも、このような二項分布の場合は、\(n\)が十分大きいとき正規分布で近似できるからそっちのほうが便利かもしれないが。