Markov's inequality and 0-1 random variables

Probability !

Xを非負の確率変数としたとき、任意のa > 0に対して

が成り立ちます。

この不等式はマルコフの不等式として知られており、確率変数の値がある正の定数以上になる確率の上限を与えます。Markov's inequalityではこの不等式の興味深い応用例を紹介しています。

An example of an application of Markov's inequality is the fact that (assuming incomes are non-negative) no more than 1/5 of the population can have more than 5 times the average income.

Markov's inequality - Wikipedia

つまり、マルコフの不等式から、人口の1/5以上が平均の5倍以上の収入を得ることは起こりえないことがいえるのです。

さて、マルコフの不等式はあまり複雑に見えません。実際、この不等式が与える上界はかなりおおざっぱです。確率と計算ではマルコフの不等式が与える上界は大まかで有用な結果を出すには十分ではないことがままあると注意を促しつつも、より強力な評価を得るための基本的な道具であると紹介しています。

今回のエントリでは確率と計算で論じられているマルコフの不等式の証明の紹介とその解説を行い、さらに積分を用いた証明を行います。


さて、確率と計算ではマルコフの不等式を次のように証明しています(ここでの証明は原書と訳本を元に意訳をしています)。

a > 0に対して、次のような確率変数Iを定義します。

Iが0-1確率変数であることに注意すると、

また、X ≧ 0から

であることに注意して期待値を取ると、マルコフの不等式が得られます。


さて、より理解を深めるためにトピックを精選して考えてみましょう。

定義より、確率変数Iは0と1のいずれかの値しか取らない確率変数となります。このような確率変数を0-1確率変数(0-1 random variable)と呼びます。0-1確率変数は期待値や分散を簡単に計算することができる確率変数です。

実際に0-1確率変数の期待値を求めてみると確率変数Xの値が1となる確率、Pr(X = 1)と等しくなることが分かります。

また、驚くことに、0-1確率変数のi次積率EiもPr(X = 1)と等しくなります。

期待値と2次積率を用いて分散を計算してみましょう。分散Var[X]はE[X2] - (E[X])2として計算することができるので

つまり、0-1確率変数の分散は確率変数Xの値が1、0となるそれぞれの確率の積、Pr(X = 1)Pr(X = 0)と等しくなることが分かります。

また、確率変数Iが1となるのはX ≧ aが成立するときですので、結果として次の等式を得ることができます。


次に、Xが非負の確率変数であり、aが正の定数であること考えると、定義よりI ≦ X / aが成立します。これは少々直感に欠けるように思いますが、図を見ると明らかです。

確率変数Iの値は確かにX / a以下に収まることが分かります。確率変数Iは確率変数Xに従属した確率変数であることに注意してください。


最後に、確率と計算ではI ≦ X / aから次の不等式を導いています。

こちらも丁寧に計算しておきましょう。I ≦ X / aの両辺からIを引くと

Y = X / a - Iとします。定義より確率変数Yも非負の確率変数となりますので、その期待値ももちろん非負となります。

期待値の線形性を用いて

したがって

ここから


では積分を使ってマルコフの不等式を証明してみましょう。作図を考慮し、ここからは連続確率を用いた議論を行います。

定義より非負の確率変数Xの期待値は次のように与えられます。

ここで積分範囲を狭めてみましょう。具体的にはx ≧ aの範囲とします。xとf(x)が双方とも非負の値を取ることに注意すると、積分の結果は小さくなります(等しい場合もあります)。

この関係は図で見ると明らかとなります。期待値は次の図で表す面積を計算することに他なりません。

積分範囲を減らしたものはその積分値も小さくなります。

次に積分の中のxをaに置き換えてみましょう。xとf(x)が双方とも非負の値を取り、a > 0であることに注意すると、積分値はさらに小さくなります(さきほどと同様に等しくなる場合もあります)。

この関係も図で見てみましょう。

aは定数ですので、積分の外に吐き出せそうです。

積分値は確率変数Xがaと等しいか大きくなる確率、Pr(X >= a)を表していますので

まとめると

ここから

が成立します。

まとめ

今回のエントリではマルコフの不等式の証明を紹介しました。

確率と計算で論じられているマルコフの不等式の証明は自分の感覚と合わなかったのか理解するまで時間がかかりましたが、0-1確率変数と不等式の期待値について掘り下げて考えることができたのはよい機会でした。

積分での証明には慶應大学の講義で論じられているチェビシェフの不等式の証明を大いに参考にしました(チェビシェフの不等式の説明は37:20ほどから、証明は55:00ほどから始まります)。素晴らしい講義を公開してくださっている皆様に心から感謝いたします。


このエントリを記載するにあたり、以下のページを参考にしました。

以下のPDFには確率変数にまつわる不等式が分かりやすくまとまっています。

また、以下の書籍を参考にしました。

確率と計算 ―乱択アルゴリズムと確率的解析―

確率と計算 ―乱択アルゴリズムと確率的解析―

Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Probability and Computing: Randomized Algorithms and Probabilistic Analysis

アルゴリズムイントロダクション 第1巻 数学的基礎とデータ構造

アルゴリズムイントロダクション 第1巻 数学的基礎とデータ構造

  • 作者: T.コルメン,R.リベスト,C.ライザーソン,Thomas H. Cormen,Ronald L. Rivest,Charles E. Leiserso,浅野哲夫,梅尾博司,和田幸一,岩野和生,山下雅史
  • 出版社/メーカー: 近代科学社
  • 発売日: 1995/12
  • メディア: 単行本
  • 購入: 3人 クリック: 144回
  • この商品を含むブログ (34件) を見る

確率に関しては次のような記事を記載しています。