20.5 Chernoff 限界

確率変数に関して分かっているのが期待値と分散だけなら、その値が期待値から逸脱する量と確率の関係について Chebyshev の定理 (定理 20.2.3) より優れた結果は得られない。しかしときには、確率変数について分かっている追加の情報 ── 例えば「二項分布に従う」など ── を使うと強い結果を示せるケースがある。本節では、\(1/c^{2}\) のように多項式的に小さくなる上界よりも格段に優れた、\(1/e^{c}\) のように指数的に小さくなる上界が保証される性質を見る。その性質とは「\(0\) 以上 \(1\) 以下の値を取る相互独立な確率変数 \(T_{1}\), \(T_{2}\), \(\ldots\), \(T_{n}\) の和として表せる」であり、例えば二項分布に従う確率変数は必ずこの性質を持つ。他にも、この性質を持った確率変数は様々な場面で登場する。

20.5.1 例: サーバーの負荷分散

Fussbookファスブックは不愉快な人をターゲットとする新しい SNS サイトである。全ての大規模ウェブサービスと同様に、Fussbook は負荷分散の問題を抱えている: 掲示板に対する書き込みが大量に送信されるので、それを複数のサーバーで分担して処理しなければならない。もし特定の時間内に完了できない量のタスク (書き込みの処理) が特定のサーバーに送信されると、そのサーバーは過負荷状態になってシステム全体のパフォーマンスが悪化する。Fussbook のユーザーは寛容の対極にある存在なので、これは望ましくない。そのため複数のサーバーに対して負荷を適切に割り当てることが重要となる。

Fussbook が最初に採用していたのは「各サーバーにアルファベットの区間を割り当て、掲示板のスレッド名を使ってタスクを割り当てる」という方法だった。プログラマーは「多分動くよ！」と自信を見せたものの、「privacy (プライバシー)」スレッドと「preferred text editor (好きなテキストエディタ)」スレッドを担当するサーバーで過負荷が発生した。こういったアドホックなアプローチの欠点は明らかである: 計画を台無しにする致命的な障害を見落とす可能性が常にある。

もし全てのタスクにかかる時間が事前に分かるなら、この問題はビンパッキング問題 (bin packing problem) の一種となる。正確に解くのは難しいものの、優れた解を求める近似アルゴリズムが知られている。しかし残念ながら、今考えている問題では各タスクの長さが分からない。これは現実世界の負荷分散問題でも典型的な設定である。

この状況で負荷を上手く分散させるなど不可能に思える。そもそも、行う処理を決定するための情報が何もない。そこで Fussbook のプログラマーは諦めて、それぞれのタスクをランダムなサーバーに割り振るようにした。システムが長い間クラッシュせず動き続けたときの彼らの驚きようを想像してみてほしい！

実は、このランダムなタスクの割り当ては負荷を上手く分散させるだけではなく、パフォーマンスに関する数学的に証明可能な保証を持つ。一般に、決定的な解の計算が困難あるいは不可能なときランダム性を利用するアプローチには一考の価値がある。

具体的な数値を使ってさらに考えてみよう。Fussbook は \(10\) 分ごとに \(24{,}000\) 件の書き込みを受け取る。それぞれの書き込みはいずれかのサーバーに受け渡され、サーバーは書き込みを受け取った順に一つずつ処理する。一つの書き込みを処理するのにかかる時間は平均で \(1/4\) 秒であり、どんなに長い書き込みであっても ── 気が遠くなるほど長い大演説であっても ── 必ず \(1\) 秒以内に処理できると仮定する。もちろん、些末な文法ミスの指摘や趣味の悪いジョークのように処理がすぐに終わる書き込みもある。

一台のサーバーが一秒に処理できる負荷を \(1\) 単位と定めれば、サーバーは \(600\) 秒間に \(600\) 単位より多い量の仕事を受け取ると過負荷状態になる。Fussbook が受け取る負荷の量は \(10\) 分ごとに \(24{,}000 \cdot 1/4 = 6000\) 単位である。よって \(6000 / (10 \cdot 60) = 10\) 台のサーバーを \(100\%\) 稼働させれば、全ての書き込みを遅滞なく処理できる。ただ、負荷は常に一定なわけではなく、負荷分散も完璧ではないので、実際に必要なサーバーは \(10\) 台より多い。では \(11\) 台で十分だろうか？それとも \(15\), \(20\), \(100\) 台を用意しなければならないだろうか？新しい数学的ツールを使うと、この質問に答えられる。

20.5.2 Chernoff 限界

Chernoffチェルノフ限界 (Chernoff bound) は非常に多種多様な問題を叩けるハンマーである¹。大まかに言えば、Chernoff 限界は特定の性質を持つ確率変数が期待値から大きく離れた値を取る可能性が極端に低いことを示す。上記の例で言えば、サーバー全体が理論上処理可能なタスクの量が実際のタスクの総量より少しでも大きければ (そして Chernoff 限界の条件が満たされるなら)、システムが過負荷状態になる可能性は低いと言える。

さらに正確に言えば、Chernoff 限界は「小さな値を取る独立な確率変数の和が、それぞれの確率変数の期待値の和から大きく離れる可能性は低い」と主張する。Markov の定理 (定理 20.1.1) と Chebyshev の定理 (定理 20.2.3) を使っても同様の結果は得られるものの、典型的にはずっと弱い上界しか得られない。二つの定理から得られる上界は多項式的であるのに対して、Chernoff 限界は指数的である。

Chernoff 限界を定理として述べると次のようになる。証明は第 20.5.6 項で示す。

定理 20.5.1[Chernoffチェルノフ限界 (Chernoff bound)]

\(T_{1}\), \(T_{2}\), \(\ldots\) \(T_{n}\) が相互独立な確率変数で、全ての \(i\) で \(0 \leq T_{i} \leq 1\) が成り立つとする。\(T = T_{1} + T_{2} + \cdots + T_{n}\) と定めると、全ての \(c \geq 1\) に対して次の不等式が成り立つ:

\[ \operatorname{Pr} [T \geq c \operatorname{Ex} [T]] \leq e^{-\beta (c) \operatorname{Ex} [T]} \tag{20.23}\]

ただし \(\beta (c) ::= c \ln c - c + 1\) である。

Chernoff 限界を適用できるのは、実数区間 \([0,1]\) に属する値だけを取る相互独立な確率変数の和として表せる確率変数に対してだけである。この基準を満たす有名な例として、任意の二項分布に従う確率変数がある。しかし、他にも様々な場面で現れる確率変数が基準を満たす。値域が \([0,1]\) でありさえすれば、足される確率変数は異なっていても、さらに言えば未知でも構わない。また、不等式 \(\text{(20.23)}\) は足される確率変数の個数やそれらの個別の期待値に直接依存しない。つまり、Chernoff 限界を使えば多くの場面で追加の情報をほとんど使わずにとても強い結果が得られる ── 広く用いられることに不思議はない！

20.5.3 Chernoff 限界を使った二項分布の裾の評価

Chernoff 限界を表す不等式 \(\text{(20.23)}\) は一見すると物騒な見た目をしているものの、それを使うために必要となるステップに難しいところはない。簡単な例を通して利用法を確認してみよう: 公平なコインを独立に \(1000\) 回投げたとき、表の出る回数が期待値より \(20\%\) 以上大きくなる (表が \(600\) 回以上出る) 確率の上界をこれから求める。事象 [\(i\) 回目に投げたコインが表を向く] に対応する指示確率変数を \(T_{i}\) とすれば、\(100\) 回のコイン投げ全体で表が出た回数を表す確率変数 \(T\) は次の等式を満たす:

\[ T = T_{1} + T_{2} + \cdots + T_{1000} \]

Chernoff 限界は確率変数 \(T_{i}\) が相互独立であり、\([0,1]\) に属する値だけを取ることを要求する。この問題では、いずれの条件も満たされる。\(1000\) 回のコイン投げは問題の設定より相互独立であり、指示確率変数 \(T_{i}\) は \(0\) または \(1\) の値しか取らない。

求めたいのは「表が出る回数が期待値より \(20\%\) 以上大きくなる確率の上界」であり、これは \(c = 1.2\) としたときの \(\operatorname{Pr} [T \geq c \operatorname{Ex} [T]]\) の上界に等しい。これを求めるために、まず Chernoff 限界で利用される \(\beta (c)\) を計算する:

\[ \beta (c) = c \ln c - c + 1 = 0.0187\ldots \]

また、コインは公平なので \(\operatorname{Ex} [T] = 500\) が成り立つ。これらを不等式 \(\text{(20.23)}\) に代入すれば、次の関係が分かる:

\[ \begin{aligned} \operatorname{Pr} [T \geq 1.2 \operatorname{Ex} [T]] &\leq e^{-\beta (c) \operatorname{Ex} [T]} \\ &= e^{-(0.0187\ldots) \cdot 500} < 0.0000834 \end{aligned} \]

つまり、公平なコインを独立に \(1000\) 回を投げて表が出る回数が期待値より \(20\%\) 以上大きくなる (表が \(600\) 回以上出る) 確率は \(10{,}000\) 分の \(1\) より小さい。

指数の肩に表が出る回数の期待値が乗っているので、この上界はコインを投げる回数を増やすと格段に小さくなる。例えば、コインを \(100\) 万回投げるとき、表が出る回数が期待値より \(20\%\) 以上大きくなる確率の上界は

\[ e^{-(0.0187\ldots) \cdot 500{,}000} < e^{-9392} \]

と求められる。これは途方もなく小さな値である。

また、偏差を大きくした場合にも上界は小さくなる。例えば、公平なコインを独立に \(1000\) 回を投げるとき、表が出る回数が期待値より (\(20\%\) ではなく) \(30\%\) 以上大きくなる確率の上界に興味があるとする。このときは \(c = 1.2\) ではなく \(c = 1.3\) とすればよい。すると \(\beta (c)\) は \(0.0187\) から \(0.0410\) に上昇する。大した変化ではないと思うかもしれないが、\(\beta(c)\) は上界を表す式で指数の肩に乗っているので、最終的に求まる上界は約 \(1\) 万分の \(1\) から約 \(10\) 億分の \(1\) に減少する！

20.5.4 Chernoff 限界の応用: 番号選択式宝くじ

Pick-4ピックフォーと呼ばれる方式の宝くじがある: それぞれの参加者は \(1\) ドルを支払って \(0000\) から \(9999\) までの \(4\) 桁の数字を一つ選び、それがランダムに選ばれた当選番号と一致すると \(5{,}000\) ドルを獲得できる。この方式の宝くじの当選確率は \(1/10{,}000\) である。参加者がちょうど \(1000\) 万人で、宝くじの運営者は参加者が支払った総額の半分にあたる \(500\) 万ドルを運営費などのために確保したいと考えている。運営者にとっての悪夢は当選者の人数が数学的な期待値よりずっと大きくなることであり、特に \(2000\) 人以上が当選してしまうと参加者から集めた金額より多くの当選金を支払うことになる。この状況が発生する確率はどれくらいだろうか？

事象 [\(i\) 番目の参加者が当選する] に対応する指示確率変数を \(T_{i}\) とすれば、当選者の人数を表す確率変数 \(T\) は \(T = T_{1} + T_{2} + \cdots + T_{n}\) を満たす。参加者が選択する数字と当選番号が独立かつ一様ランダムだと仮定²すれば \(T_{i}\) は (相互) 独立であり、Chernoff 限界が必要とする前提条件が満たされる。

\(2000\) 人の当選者は期待値の倍なので、\(c = 2\) とする。このとき \(\beta(c) = 0.386\ldots\) であり、Chernoff 限界に値を代入すれば次の不等式を得る:

\[ \begin{aligned} \operatorname{Pr} [T \geq 2000] &= \operatorname{Pr} [T \geq 2 \operatorname{Ex} [T]] \\ &\leq e^{-\beta(c) \operatorname{Ex} [T]} = e^{-(0.386\ldots) \cdot 1000} \\ &< e^{-386} \end{aligned} \]

よって、参加者が支払った総額より多くの当選金が発生する事態は事実上発生しないと分かる。さらに言えば、当選者の人数が期待値より \(10\%\) 多くなる事態さえ頻繁には起こらない。実際 \(c = 1.1\) とすれば \(\beta (c) = 0.00484\) であり、同様に値を代入すれば次の不等式を得る:

\[ \begin{aligned} \operatorname{Pr} [T \geq 1.1 \operatorname{Ex} [T]] &\leq e^{-\beta(c) \operatorname{Ex} [T]} = e^{-(0.00484\ldots) \cdot 1000} \\ &< 0.01 \end{aligned} \]

Pick-4 方式の宝くじは参加者にとってはワクワクするものかもしれないが、運営者が利益に関して心配することはない！

20.5.5 ランダム性を利用する負荷分散

Fussbook における負荷分散の問題に話を戻そう。任意の \(600\) 秒間に処理できない量の書き込みが割り当てられるサーバーが発生しないようにしたいとき、用意すべきサーバーの台数 \(m\) を求めたいのだった。

最初に、\(1\) 台目のサーバー \(S_{1}\) が過負荷状態になる確率の上界を計算する。特定の \(10\) 分間に \(S_{1}\) に割り当てられる全ての書き込みを処理するのにかかる時間を表す確率変数を \(T\) とすれば、求めたいのは \(\operatorname{Pr} [T \geq 600]\) の上界である。\(S_{1}\) が \(i\) 番目の書き込みを処理する時間の長さを表す確率変数を \(T_{i}\) とする。つまり \(i\) 番目の書き込みが \(S_{1}\) に割り当てられるなら \(T_{i}\) は \(i\) 番目の書き込みの処理にかかる時間に等しく、そうでなければ \(T_{i} = 0\) となる。さらにシステム全体に送信される書き込みの個数を \(n = 24{,}000\) とすれば、\(T = \sum_{i=1}^{n} T_{i}\) が成り立つ。

Chernoff 限界は \(T_{i}\) が相互独立かつ \([0,1]\) に属する値を取るときにだけ適用できる。一つ目の条件は、サーバーに対する書き込みの割り当てがその処理にかかる時間 (などの任意の情報) に関係なく決定されると仮定すれば満たされる。二つ目の条件は処理に \(1\) 秒より長く書かる書き込みが存在しない設定から分かる。これは時間の長さを秒で表している理由でもある。

処理すべき書き込みは全部で \(24000\) 件あり、それぞれの処理には平均で \(1/4\) の時間がかかる。システムは \(m\) 台のサーバーを持つので、\(S_{1}\) に対する負荷の期待値は次のように求められる:

\[ \begin{align*} \operatorname{Ex} [T] &= \frac{24{,}000 \cdot 1/4}{m} \\[6pt] &= \frac{6000}{m}~\text{単位} \tag{20.24} \end{align*} \]

よって、例えばサーバーが \(10\) 台より少ないなら \(6000/m > 600\) なので、\(S_{1}\) に対する負荷の期待値は処理可能な量を超える。もしサーバーが \(10\) 台なら \(6000/m = 600\) であり、これは \(S_{1}\) が全く手を止めずに処理を続けたときに捌ける負荷の量に等しい。

では、Chernoff 限界を使って \(S_{1}\) が過負荷を起こさない確率の上界を求めよう。今回はサーバーの台数 \(m\) が変数なので、少しだけ使い勝手が異なる。等式 \(\text{(20.24)}\) から次の関係が分かる:

\[ c ::= m/10\ \text{ とすれば }\ 600 = c \operatorname{Ex} [T] \]

Chernoff 限界 (定理 20.5.1) より次の不等式を得る:

\[ \operatorname{Pr} [T \geq 600] = \operatorname{Pr} [T \geq c \operatorname{Ex} [T]] \leq e^{-(c \ln c - c + 1) \cdot 6000 / m} \]

和集合上界則 (規則 17.5.4) より、\(m\) 台あるサーバーのいずれかで過負荷が発生する確率は、\(S_{1}\) で過負荷が発生する確率の \(m\) 倍で抑えられる。よって次の関係を得る:

\[ \begin{aligned} & \operatorname{Pr} [\text{いずれかのサーバーで過負荷が発生する}] \\ & \qquad \leq \sum_{i=1}^{m} \operatorname{Pr} [\text{\(i\) 番目のサーバーで過負荷が発生する}] \\ & \qquad = m \operatorname{Pr} [\text{\(S_{i}\) で過負荷が発生する}] \\ & \qquad \leq m e^{-(c \ln c - c + 1) \cdot 6000 / m} \end{aligned} \]

ここで \(c = m/10\) である。\(m\) に具体的な数値を代入したときの上界の値を示す:

\[ \def\arraystretch{1.2}\begin{array}{cl} m = 11: & 0.784\ldots \\ m = 12: & 0.000999\ldots \\ m = 13: & 0.0000000760\ldots \end{array} \]

この結果を見ると、サーバーの台数が \(m = 11\) ならすぐに過負荷が発生し、\(m = 12\) なら数日中に過負荷が発生する可能性が高いと分かる。しかし \(m = 13\) とすればシステムはおそらく数世紀にわたって動作を続ける！

20.5.6 Chernoff 限界の証明

Chernoff 限界の証明は少し難しい。実は、証明を発見したのは Chernoff ではない³。Chernoff に証明の大枠を示してみせたのは彼の友人 Hermanハーマン Rubinルービンだった。しかし、この結果がそれほど重要でないと考えた Chernoff は論文で Rubin の名前を出さなかった。後に結果が有名になったとき、彼は深く後悔したという！

定理 20.5.1 の証明議論を追いやすくするため、証明は「トップダウン」に行う。つまり、未証明の事実を使って全体の流れを示してから、利用した事実を証明する。

鍵となるのは、不等式 \(T \geq c \operatorname{Ex} [T]\) の両辺の指数を取ってから Markov の定理 (定理 20.1.1) を適用するステップである:

\[ \begin{aligned} \operatorname{Pr} [T \geq c \operatorname{Ex} [T]] & = \operatorname{Pr} [c^{T} \geq c^{c \operatorname{Ex} [T]}] \\[5pt] & \leq \frac{\operatorname{Ex} [c^{T}]}{c^{c \operatorname{Ex} [T]}} \qquad \quad\ \, (\because\ \text{Markov の定理}) \\[10pt] & \leq \frac{e^{(c-1) \operatorname{Ex} [T]}}{c^{c \operatorname{Ex} [T]}} \qquad (\because\ \text{以下で示す\text{補題 }\href{#lemma-20-5-2}{20.5.2}}) \\[10pt] & = \frac{e^{(c - 1) \operatorname{Ex} [T]}}{e^{c \ln c \operatorname{Ex} [T]}} = e^{-(c \ln c - c + 1) \operatorname{Ex} [T]} \end{aligned} \]

■

この証明では代数的な変形でない部分で素晴らしいアイデアが使われている: 考えている不等式の両辺に指数関数を適用すると、Markov の定理が与える上界が格段に小さくなる。もちろんこれは一般に可能な操作ではない！不幸な副作用として、証明を完了するために指数が絡む厄介な期待値を上から抑える必要が生じる。これは次に示す二つの補題を通して行われる。変数の設定は定理 20.5.1 と同様とする。

補題 20.5.2

\[ \operatorname{Ex} [c^{T}] \leq e^{(c - 1)\operatorname{Ex} [T]} \]

証明

\[ \begin{aligned} \operatorname{Ex} [c^{T}] &= \operatorname{Ex} [c^{T_{1} + \cdots + T_{n}}] && (\because\ \text{\(T\) の定義}) \\ &= \operatorname{Ex} [c^{T_{1}} \cdots c^{T_{n}}] && \\ &= \operatorname{Ex} [c^{T_{1}}] \cdots \operatorname{Ex} [c^{T_{n}}] && (\because\ \text{\text{系 }\href{/mcs/probability/random_variables/linearity_of_expectation/#coro-19-5-7}{19.5.7}}) \\ & \leq e^{(c-1) \operatorname{Ex} [T_{1}] } \cdots e^{(c - 1) \operatorname{Ex} [T_{n}]} && (\because\ \text{以下で示す\text{補題 }\href{#lemma-20-5-3}{20.5.3}}) \\ &= e^{(c - 1)(\operatorname{Ex} [T_{1}] + \cdots + \operatorname{Ex} [T_{n}])} && \\ &= e^{(c - 1)(\operatorname{Ex} [T_{1} + \cdots T_{n}])} && (\because\ \text{期待値の線形性}) \\ &= e^{(c - 1)\operatorname{Ex} [T]} \end{aligned} \]

二行目から三行目への式変形では、独立な確率変数の関数も独立となる事実 (参照: 補題 19.2.2) も使っている。 ■

補題 20.5.3

\[ \operatorname{Ex} [c^{T_{i}}] \leq e^{(c - 1)\operatorname{Ex} [T_{i}]} \]

証明次の式変形において、全ての総和は確率変数 \(T_{i}\) の取る値 \(v\) に関する和を表す。問題の設定より、\(v\) は区間 \([0,1]\) に属する。

\[ \begin{aligned} \operatorname{Ex} [c^{T_{i}}] & = \sum c^{v} \operatorname{Pr} [T_{i} = v] && (\because\ \text{期待値の定義}) \\ & \leq \sum (1 + (c - 1)v) \operatorname{Pr} [T_{i} = v] && (\because\ \text{凸性 ── 以下を参照}) \\ &= \sum \operatorname{Pr} [T_{i} = v] + (c - 1) v \operatorname{Pr} [T_{i} = v] && \\ &= \sum \operatorname{Pr} [T_{i} = v] + (c - 1) \sum v \operatorname{Pr} [T_{i} = v] && \\ &= 1 + (c - 1) \operatorname{Ex} [T_{i}] && \\ & \leq e^{(c - 1) \operatorname{Ex} [T_{i}]} && (\because\ 1 + z \leq e^{z}) \end{aligned} \]

一行目と二行目を結ぶ不等号は、全ての \(v \in [0,1]\) と \(c \geq 1\) で成り立つ次の不等式によって正当化される:

\[ c^{v} \leq 1 + (c - 1) v \]

この不等式は「凸関数と線形関数が二か所で交わるなら、その間では凸関数の方が線形関数より小さな値を取る」という一般的な命題から分かる。凸関数を \(c^{v}\) として線形関数を \(1 + (c - 1)v\) とすれば、交点は \(v = 0\) と \(v = 1\) を満たす。Chernoff 限界 (定理 20.5.1) で確率変数 \(T_{i}\) の値域が実数区間 \([0,1]\) に制限されるのは、この不等式を成り立たせるためである。 ■

20.5.7 上界の比較

簡単な例を使って本章で見た概念や定理をまとめておく。相互独立な事象 \(A_{1}\), \(\ldots\), \(A_{n}\) があり、その中で起こる事象の個数を知りたいとする。

事象 \(A_{i}\) に対応する指示確率変数を \(T_{i}\) として、\(p_{i}\) を次のよう定める:

\[ p_{i} ::= \operatorname{Pr} [T_{i} = 1] = \operatorname{Pr} [A_{i}] \qquad (1 \leq i \leq n) \]

\(A_{1}\), \(\ldots\), \(A_{n}\) の中で起こる事象の個数を表す確率変数を \(T\) とすれば、\(T\) は次の等式を満たす:

\[ T = T_{1} + \cdots + T_{n} \]

期待値の線形性 (系 19.5.3) から次の等式を得る:

\[ \begin{aligned} \operatorname{Ex} [T] &= \operatorname{Ex} [T_{1}] + \cdots + \operatorname{Ex} [T_{n}] \\ &= \sum_{i=1}^{n} p_{i} \end{aligned} \]

この等式は事象が独立でない場合でも成り立つ。

分散の全組独立加法性 (定理 20.3.8) からは次の等式も分かる:

\[ \begin{aligned} \operatorname{Var} [T] &= \operatorname{Var} [T_{1}] + \operatorname{Var} [T_{2}] + \cdots + \operatorname{Var} [T_{n}] \\ &= \sum_{i=1}^{n} p_{i} (1 - p_{i}) \qquad (\because\ \text{\text{系 }\href{/mcs/probability/deviation_from_mean/properties_of_variance/#coro-20-3-2}{20.3.2}}) \end{aligned} \]

よって \(T\) の標準偏差 \(\sigma_{T}\) は次のように表せる:

\[ \sigma_{T} = \sqrt{\sum_{i=1}^{n} p_{i} (1 - p_{i})} \]

これは事象が全組独立でしかない場合でも成り立つ。

Markov の定理 (定理 20.1.1) は任意の \(c > 1\) で次の不等式が成り立つと主張する:

\[ \operatorname{Pr} [T \geq c \operatorname{Ex} [T]] \leq \frac{1}{c} \]

Chebyshev の定理 (定理 20.2.3) からは、より強い結果が得られる:

\[ \operatorname{Pr} [\left| T - \operatorname{Ex} [T] \right| \geq c \, \sigma_{T} ] \leq \frac{1}{c^{2}} \]

Chernoff 限界 (定理 20.5.1) はさらに強い結果を与える。つまり、任意の \(c > 0\) で次の不等式が成り立つ:

\[ \operatorname{Pr} [T \geq c \operatorname{Ex} [T]] \leq e^{-(c \ln c - c + 1) \operatorname{Ex} [T]} \]

言い換えれば、確率変数が Chernoff 限界の前提条件を満たすなら、それが期待値の \(c\) 倍以上になる確率は \(c\) に関して指数的に小さくなる。

確率変数 \(n - T\) に Chernoff 限界を適用すれば、\(T\) が期待値より小さくなる確率も指数的に小さくなることが示せる。

20.5.8 Murphy の法則

確率変数の期待値が \(1\) より小さく \(0\) に非常に近いとき、その確率変数の値が \(1\) 以上になる確率は低い。これは Markov の定理から分かる。一方で、本書が Murphyマーフィーの法則 (Murphy's law) と呼ぶ⁴結果からは、\(0\) または \(1\) の値を取る確率変数の和であり期待値が大きい確率変数が \(1\) 以上になる確率は非常に高いと分かる。

定理 20.5.4[Murphyマーフィーの法則 (Murphy's law)]

\(A_{1}\), \(A_{2}\), \(\ldots\), \(A_{n}\) を相互独立な事象、\(T_{i}\) を \(A_{i}\) に対応する指示確率変数とする。さらに、\(A_{1}\), \(A_{2}\), \(\ldots\), \(A_{n}\) の中で起こる事象の個数を表す確率変数を \(T\) と定める:

\[ T ::= T_{1} + T_{2} + \cdots + T_{n} \]

このとき次の不等式が成り立つ:

\[ \operatorname{Pr} [T = 0] \leq e^{- \operatorname{Ex} [T]} \]

証明

\[ \begin{align*} \operatorname{Pr} [T = 0] & = \operatorname{Pr} [\overline{\mathstrut A_{1}} \cap \overline{\mathstrut A_{2}} \cap \cdots \cap \overline{\mathstrut A_{n}}] \\ & \qquad (\because\ T = 0 \ \ \longleftrightarrow \ \ \text{\(A_{1}\), \(A_{2}\), \(\ldots\), \(A_{n}\) が一つも起こらない}) \\ & = \prod_{i=1}^{n} \operatorname{Pr} [\overline{\mathstrut A_{i}}] \\ & \qquad (\because\ \text{\(A_{1}\), \(A_{2}\), \(\ldots\), \(A_{n}\) は相互独立}) \\ & = \prod_{i=1}^{n} (1 - \operatorname{Pr} [A_{i}]) \\ & \leq \prod_{i=1}^{n} e^{- \operatorname{Pr} [A_{i}]} \\ & \qquad (\because\ \text{\(0 \leq x \leq 1\) のとき \(1 - x \leq e^{-x}\)}) \\ & = e^{-\sum_{i=1}^{n} \operatorname{Pr} [A_{i}]} \\ & = e^{-\sum_{i=1}^{n} \operatorname{Ex} [T_{i}]} \\ & \qquad (\because\ \text{\(T_{i}\) は \(A_{i}\) に対応する指示確率変数}) \\ & = e^{-\operatorname{Ex} [T]} \\ & \qquad (\because\ \text{期待値の線形性}) \end{align*} \]

■

例えば、相互独立な事象の集合があり、その中で発生する事象の個数の期待値が \(10\) だとする。このとき、少なくとも \(1\) 個の事象が発生する確率は \(1 - e^{-10}\) 以上であり、事象が全く発生しない確率は \(e^{-10} < 1/22{,}000\) 以下である。また、次の事実も分かる: 何らかの確率で失敗する処理をいくつも実行する状況で各操作の失敗確率の和が \(1\) よりずっと大きいなら、いずれかの操作が失敗する確率が非常に高い。

この結果は、確率が極端に低く思える「偶然」や「奇跡」が起きる理由を説明するのにも利用できる。そういった事象が起きる理由の一つは、発生する可能性のある確率が低い事象が非常に多いために確率の和が \(1\) を超えるからである。例えば、誰かは宝くじに当選する。実際、Pick-4 方式の宝くじ (第 20.5.4 項) が \(100{,}000\) 枚売れた場合、定理 20.5.4 からは当選者がいない確率が \(e^{-10} < 1/20{,}000\) に満たないと分かる。一般的に言えば、百万回に一回しか起きない事象は文字通り数百万個も存在するので、そのうち一つは間違いなく発生する。

Chernoff は宝くじで儲ける方法 (第 19.4.7 項) を発見した人物でもある ── 彼は確率論に多少は精通しているようだ。 ↩︎
第 19.4.7 項で説明したように、番号選択式宝くじで参加者が選択する数字は一様でない場合が多く、大きな偏りを持つケースもある。例えば、何らかの意味がある日付を使って数字を選ぶ参加者が多くいる。全ての参加者にランダムな \(4\) 桁の数字が割り当てられる方式でない限り、宝くじ関係者は以降の解析から大きな安心感を得るべきでない。 ↩︎
参照: A Conversation with Herman Chernoff. Statistical Science. 1996, Vol. 11, No. 4, pp 335-350. ↩︎
この命名は有名な警句「失敗する可能性があるなら、必ず失敗する」を踏まえたものである。 ↩︎