20.1 Markov の定理

Markovマルコフの定理は確率変数が期待値より格段に大きい値を取る確率の一般的な粗い推定を与える。自明な結果とさえ言えるものの、この定理から直ちに得られる強い結果もある。

Markov の定理を説明するために、その疑わしい正確性にもかかわらず広く利用される IQ (intelligence quotient, 知能指数) という指標を考えよう。IQ は測定値の平均が \(100\) になるように調整される。ここから、IQ が \(300\) 以上の人口は最大でも全体の \(1/3\) だと分かる。なぜなら、もし \(1/3\) より多くの割合が \(300\) 以上の IQ を持っていると、IQ の平均値が \((1/3)\cdot 300 = 100\) を超えてしまうからである。よって、ランダムに選択された人物が \(300\) 以上の IQ を持つ確率は \(1/3\) 以下である。同様に、IQ が \(150\) 以上の人口の割合は最大でも \(2/3\) だと分かる。

もちろん、これらはそれほど強い結論ではない。\(300\) 以上の IQ を持つ人物は記録されていない。\(150\) 以上の IQ を持つ人物は多く知られているものの、その割合は \(2/3\) よりずっと小さい。しかし、上記の結論は IQ の平均値が \(100\) という事実、そして IQ が負にならないという暗黙の仮定だけを使って導かれた。これら以外に利用可能な情報がないとき、さらに強い結論は得られない。なぜなら、上記の議論が示すように上界が達成される非負確率変数が存在するからである。例えば、確率 \(1/3\) で \(300\) となり、確率 \(2/3\) で \(0\) となる確率変数の期待値は \(100\) であり、\(300\) 以上の値を取る確率が \(1/3\) である。

定理 20.1.1[Markovマルコフの定理 (Markov's theorem)]

\(R\) が非負確率変数なら、全ての \(x > 0\) で次の不等式が成り立つ:

\[ \operatorname{Pr} [R \geq x] \leq \frac{\operatorname{Ex} [R]}{x} \tag{20.1}\]

証明 \(I_{x}\) を事象 [\(R \geq x\)] に対応する指示確率変数とする。このとき \(R \geq 0\) より、任意の結果で

\[ x I_{x} \leq R \]

が成り立つ。両辺の期待値を取れば

\[ x \operatorname{Pr} [R \geq x] \leq \operatorname{Ex} [R] \]

を得る。両辺を \(x > 0\) で割れば不等式 \(\text{(20.1)}\) となる。 ■

本章で注目するのは期待値からの偏差なので、Markov の定理を次のように言い換えておく:

系 20.1.2

\(R\) が非負確率変数なら、全ての \(c \geq 1\) で次の不等式が成り立つ:

\[ \operatorname{Pr} [R \geq c \operatorname{Ex}[R]] \leq \frac{1}{c} \tag{20.2}\]

この系は定理 20.1.1 で \(x = c \operatorname{Ex}[R]\) とすれば得られる。

20.1.1 Markov の定理の適用例

第 19.5.2 項で触れた「帽子をランダムに受け取る問題」をもう一度考えよう。Markov の定理 (定理 20.1.1) を使うと、正しい帽子を受け取る男性の人数が \(x\) 以上になる確率、つまり \(\operatorname{Pr}[G \geq x]\) の上界を求められる。

以前に示したように \(\operatorname{Ex} [G] = 1\) なので、Markov の定理から次の不等式が分かる:

\[ \operatorname{Pr} [G \geq x] \leq \frac{\operatorname{Ex} [G]}{x} = \frac{1}{x} \]

例えば、\(5\) 人以上が正しい帽子を受け取る確率は最大でも \(20\%\) と分かる。この上界は夕食会の出席者が何人いても変わらない。

似た問題に中国料理の前菜問題 (Chinese appetizer problem) がある。\(n\) 人が円卓に座って中国料理を食べている。円卓の中央には回転する円盤があり、そこに \(n\) 個の異なる前菜が等間隔に置かれている。\(n\) 人はそれぞれ自分の前に置いてある前菜を取って食べていたところ、誰かが円盤をランダムな量だけ回転させた。このとき、回転の後に \(n\) 人全員の前にある前菜が以前と変わらない確率はいくつだろうか？

円盤の回転量は \(n\) 通りあり、以前と同じ前菜は \(1\) 個しかない。よって正しい確率は \(1/n\) である。

Markov の定理からは何が分かるだろうか？回転の前後で前菜が変わらない人の数を表す確率変数を \(R\) とする。このとき \(\operatorname{Ex}[R] = n \cdot (1/n) = 1\) なので、Markov の定理より次の不等式の成立が分かる:

\[ \operatorname{Pr} [R \geq n] \leq \frac{\operatorname{Ex} [R]}{n} = \frac{1}{n} \]

つまり、この中国料理の前菜問題では Markov の定理が最良の上界を与える！

しかし残念ながら、Markov の定理はそれほど正確でない。例えば、最初に触れた「帽子をランダムに受け取る問題」で全員が正しい帽子を受け取る確率を評価すると \(1/n\) という上界が得られるものの、実際の確率は \(1/n!\) である。つまり、この問題に対して Markov の定理が与える確率の上界は明らかに大きすぎる。

20.1.2 有界確率変数に対する Markov の定理の適用

MIT の学生の IQ が平均で \(150\) だと仮定する (ちなみに、これは正しくない)。このとき、IQ が \(200\) 以上の MIT の学生の割合について何が言えるだろうか？ Markov の定理を使えば、その割合は 3/4 以下だと直ちに分かる。つまり、ランダムな MIT の学生の IQ を表す確率変数 \(R\) に対して次の不等式が成り立つ:

\[ \operatorname{Pr} [R > 200] \leq \frac{\operatorname{Ex} [R]}{200} = \frac{150}{200} = \frac{3}{4} \]

ここで、次の (またしても正しくない) 事実が成り立つと仮定しよう: IQ が \(100\) 未満の MIT の学生はいないとする。このとき、\(T ::= R - 100\) とすれば \(T\) は \(\operatorname{Ex} [T] = 50\) を満たす非負確率変数となる。Markov の定理を \(T\) に適用すれば次の不等式を得る:

\[ \operatorname{Pr} [R > 200] = \operatorname{Pr} [T > 100] \leq \frac{\operatorname{Ex} [T]}{100} = \frac{50}{100} = \frac{1}{2} \]

よって新しい仮定があるとき、IQ が \(200\) を超える MIT の学生の割合は \(3/4\) 以下ではなく \(1/2\) 以下だと分かる。多少は安心できることだろう！

実は、確率変数 \(R\) の任意の下界 \(b\) が分かっているなら、Markov の定理を \(R\) ではなく \(R - b\) に適用することで上界を改善できる (問題 20.3)。また、確率変数 \(S\) の任意の上界 \(u\) が分かっているなら、\(u - S\) は非負確率変数であり、Markov の定理を \(u - S\) に適用すると \(S\) が期待値よりずっと小さくなる確率の上界を計算できる。