Markovの不等式

同義語：マルコフの不等式Markov's inequality

概要

前提知識: 期待値, 測度, Lebesgue積分, 確率空間

Markov の不等式（Markov's inequality）は、値が $0$ 以上の確率変数 $X$ と $a>0$ について
$$ P(X\ge a)\le\frac{E[X]}a $$
が成り立つという不等式である。得点が $0$ 点以上で平均点が $60$ 点の試験で $90$ 点以上をとった人の割合は、得点の分布を何も知らなくても $\frac{60}{90}=\frac23$ 以下だと分かる。期待値という 1 つの数だけから、値が大きくなる確率を上から押さえられる点に価値がある。
証明は「$X$ は $a\mathbf 1_{\{X\ge a\}}$ 以上である」という 1 行の観察で終わるが、$X$ の代わりに $X^2$ や $e^{sX}$ を使うことで、Chebyshevの不等式、高次の積率による評価、指数関数的に小さい裾の評価が次々に得られる。確率論と測度論で裾の確率を評価するほとんどの議論の出発点である。
この記事では、測度空間の上で不等式を述べて証明し（thm-mi-main、thm-mi-general）、等号の条件と、期待値だけを使う評価としての最良性を示す（thm-mi-sharp）。応用として、数え上げの第 1 積率法、独立な符号の和の指数型の評価、値が $0$ 以上で積分が $0$ の関数がほとんど至るところ $0$ であることを導く。逆向きの評価である Paley–Zygmund の不等式も扱う。

定理

設定

$(S,\mathcal S,m)$ を測度空間とする（測度）。$m$ は有限でなくてよい。値が $[0,\infty]$ の可測関数 $f$ の積分 $\int_Sf\,dm\in[0,\infty]$ は Lebesgue積分として定まる。確率空間 $(\Omega,\mathcal F,P)$ は $P(\Omega)=1$ の場合で、このとき確率変数 $X\ge0$ の積分が期待値 $E[X]$ である。$E[X]=\infty$ の場合も含めて述べる（右辺が $\infty$ なら不等式は自明に成り立つ）。

Markov の不等式

$f$ を $S$ 上の値が $[0,\infty]$ の可測関数とする。すべての $t>0$ について
$$ m\bigl(\{s\in S:f(s)\ge t\}\bigr)\le\frac1t\int_Sf\,dm $$
である。とくに確率空間の上の確率変数 $X\ge0$ と $a>0$ について $P(X\ge a)\le\dfrac{E[X]}a$ である。

指示関数で下から押さえる

$A:=\{f\ge t\}=f^{-1}([t,\infty])$ は可測集合である。各点 $s$ で
$$ t\,\mathbf 1_A(s)\le f(s) $$
が成り立つ。実際、$s\in A$ なら左辺は $t$ で $f(s)\ge t$ であり、$s\notin A$ なら左辺は $0$ で $f(s)\ge0$ である。値が $0$ 以上の可測関数の積分は単調で、正の定数倍と交換する（Lebesgue積分の定理「積分の線形性と単調性」）ので
$$ t\,m(A)=\int_St\,\mathbf 1_A\,dm\le\int_Sf\,dm $$
である。両辺を $t>0$ で割ればよい。$\blacksquare$

証明の要点は、値が $t$ 以上になる部分を高さ $t$ の箱で置き換えると、面積（積分）は小さくなるだけだ、ということである。$m(S)$ の有限性はどこにも使っていない。$\{f>t\}\subset\{f\ge t\}$ なので、$m(\{f>t\})$ にも同じ評価が成り立つ。

有限な場合と無限測度の場合

公平なさいころの目 $X$ は $E[X]=\frac72$ なので、$P(X\ge6)\le\frac{7/2}6=\frac7{12}=0.583\ldots$ である。実際の確率は $\frac16$ で、評価は粗い。$P(X\ge4)\le\frac78$ に対して実際は $\frac12$ である。
$\mathbb R$ 上の Lebesgue 測度 $m$（全体の測度は $\infty$）と $f(x)=\frac1{1+x^2}$ を考える。$\int_{\mathbb R}f\,dx=\pi$ であり、$0< t\le1$ なら $\{f\ge t\}$ は区間 $\lvert x\rvert\le\sqrt{1/t-1}$ なので、
$$ m(\{f\ge t\})=2\sqrt{\frac1t-1}\le\frac\pi t $$
が thm-mi-main から従う。$t=\frac12$ では左辺 $2$、右辺 $2\pi$ である。$t\to0$ で左辺は $t^{-1/2}$ の程度、右辺は $t^{-1}$ の程度で増える。

関数をはさんだ形

Markov の不等式の一般形

$f$ を $S$ 上の実数値可測関数、$\psi\colon[0,\infty)\to[0,\infty)$ を単調非減少な関数とする。$t>0$ で $\psi(t)>0$ なら
$$ m\bigl(\{\lvert f\rvert\ge t\}\bigr)\le\frac1{\psi(t)}\int_S\psi(\lvert f\rvert)\,dm $$
である。同様に、$g\colon\mathbb R\to[0,\infty)$ が単調非減少で $g(t)>0$ なら、$m(\{f\ge t\})\le\frac1{g(t)}\int_Sg(f)\,dm$ である。

単調な関数で集合を包む

$\psi$ は単調なので、各 $c$ について $\{x\ge0:\psi(x)\ge c\}$ は区間であり、$\psi$ は Borel 可測である。よって $\psi(\lvert f\rvert)$ は値が $0$ 以上の可測関数である。$\lvert f(s)\rvert\ge t$ なら単調性から $\psi(\lvert f(s)\rvert)\ge\psi(t)$ なので、
$$ \{\lvert f\rvert\ge t\}\subset\{\psi(\lvert f\rvert)\ge\psi(t)\} $$
である。右辺の集合に thm-mi-main を関数 $\psi(\lvert f\rvert)$ と正の数 $\psi(t)$ について使えばよい。後半は $\{f\ge t\}\subset\{g(f)\ge g(t)\}$ から同じく従う。$\blacksquare$

よく使う特別な場合を並べる。どれも thm-mi-general に関数を代入しただけである。

選ぶ関数	得られる評価	名前・使い道
$\psi(x)=x^p$（$p>0$）	$m(\lvert f\rvert\ge t)\le t^{-p}\int\lvert f\rvert^p\,dm$	積率による評価、弱 $L^p$ への埋め込み
$\psi(x)=x^2$、$f=X-E[X]$	$P(\lvert X-E[X]\rvert\ge a)\le V[X]/a^2$	Chebyshevの不等式
$g(x)=e^{sx}$（$s>0$）	$P(X\ge a)\le e^{-sa}E[e^{sX}]$	指数型の評価（Chernoff の方法）
$\psi=\mathbf 1_{[t,\infty)}$	等号 $m(\lvert f\rvert\ge t)=\int\mathbf 1_{\{\lvert f\rvert\ge t\}}dm$	評価は自明になる

最後の行のように $\psi$ を階段関数にすれば評価は等式になるが、それでは右辺を求めることが元の確率を求めることと同じになる。右辺の積分が計算でき、しかも評価が鋭くなるような $\psi$ を選ぶことが要点である。$\psi(x)=x^2$ の場合の評価の最良性や片側の改良は Chebyshevの不等式で扱う。

等号と最良性

等号の条件と最良性

確率変数 $X\ge0$ と $a>0$ について、$P(X\ge a)=\dfrac{E[X]}a$ となるのは、$P\bigl(X\in\{0,a\}\bigr)=1$ のとき、かつそのときに限る。
$\mu>0$ と $a\ge\mu$ を任意にとると、$X\ge0$、$E[X]=\mu$、$P(X\ge a)=\frac\mu a$ を満たす確率変数 $X$ がある。したがって、期待値だけから $P(X\ge a)$ を上から押さえる評価として、$\frac{E[X]}a$ はこれ以上小さくできない。
$0< a< \mu$ なら、$X\ge0$、$E[X]=\mu$、$P(X\ge a)=1$ を満たす $X$ がある（右辺 $\frac\mu a>1$ の評価は何も言っていない）。

期待値を事象で分ける

1：$A:=\{X\ge a\}$ とおく。$E[X]<\infty$ としてよい（$E[X]=\infty$ なら等号は成り立たず、$P(X\in\{0,a\})=1$ でもない）。
$$ E[X]-a\,P(A)=E\bigl[(X-a)\mathbf 1_A\bigr]+E\bigl[X\mathbf 1_{A^c}\bigr] $$
であり、右辺の 2 つの被積分関数はどちらも $0$ 以上である。値が $0$ 以上の可測関数の積分が $0$ になるのは、その関数が確率 $1$ で $0$ のときに限る（Lebesgue積分の補題「零集合と積分」）。よって等号は、確率 $1$ で「$A$ の上では $X=a$、$A^c$ の上では $X=0$」となること、すなわち $P(X\in\{0,a\})=1$ と同値である。
2：$X$ が $a$ を確率 $\frac\mu a\in(0,1]$、$0$ を確率 $1-\frac\mu a$ でとるようにすれば、$E[X]=\mu$、$P(X\ge a)=\frac\mu a$ である。
3：$X$ を定数 $\mu$ とすればよい。$\blacksquare$

2 で作った分布は、$0$ か $a$ しかとらない極端なものである。一方、可積分な $X\ge0$ を 1 つ固定すると、評価は $a\to\infty$ でいくらでも粗くなる。

固定した分布での改良

$X\ge0$ が $E[X]<\infty$ を満たすなら、$a\to\infty$ のとき $a\,P(X\ge a)\to0$ である。

優収束定理

$\{X\ge a\}$ の上では $a\le X$ なので、$a\,P(X\ge a)\le E\bigl[X\mathbf 1_{\{X\ge a\}}\bigr]$ である。$a\to\infty$ のとき、$X(\omega)<\infty$ となる各 $\omega$ で $X(\omega)\mathbf 1_{\{X\ge a\}}(\omega)\to0$ であり（$E[X]<\infty$ なので $X<\infty$ は確率 $1$ で成り立つ）、これらは可積分な $X$ で押さえられる。Lebesgue積分の定理「優収束定理」（$a$ を任意の数列 $a_n\to\infty$ に替えて使う）により右辺は $0$ に近づく。$\blacksquare$

応用

第 1 積率法

$0$ 以上の整数値をとる確率変数 $N$ では、$a=1$ として $P(N\ge1)\le E[N]$ である。$N$ を「起こってほしくないものの個数」にとり、期待値の線形性で $E[N]$ を計算して $1$ 未満にできれば、それが起こらない場合が正の確率で存在する。この使い方を 第 1 積率法 という（確率論的方法）。

表の連が現れる確率

公平な硬貨を $n$ 回投げ、$k$ 回以上表が続く箇所がある確率を評価する（$1\le k\le n$）。$i=1,\dots,n-k+1$ について、事象 $A_i$ を「$i$ 回目から $i+k-1$ 回目までがすべて表」とすると $P(A_i)=2^{-k}$ である。$N:=\sum_i\mathbf 1_{A_i}$ とおけば、$k$ 回以上の連があることは $N\ge1$ と同値なので
$$ P(\text{$k$ 回以上表が続く})=P(N\ge1)\le E[N]=(n-k+1)\,2^{-k} $$
である。$n=100$、$k=10$ では $\frac{91}{1024}=0.0888\ldots$ 以下である。事象 $A_i$ どうしは重なり合って独立でないが、期待値の線形性は独立性を要しないので、計算は 1 行で済む。

指数型の評価

thm-mi-general で $g(x)=e^{sx}$ とすると、和の裾の確率が指数関数的に小さいことを示せる。

独立な符号の和の裾

$\Omega:=\{1,-1\}^n$ に一様な確率を与え、$\varepsilon_i(\omega):=\omega_i$、$S_n:=\varepsilon_1+\cdots+\varepsilon_n$ とおく。すべての $a>0$ について
$$ P(S_n\ge a)\le\exp\Bigl(-\frac{a^2}{2n}\Bigr) $$
である。

積率母関数を評価して s を選ぶ

$s>0$ とする。積を展開すると
$$ E[e^{sS_n}]=2^{-n}\sum_{\omega\in\Omega}\prod_{i=1}^ne^{s\omega_i}=\prod_{i=1}^n\frac{e^s+e^{-s}}2=(\cosh s)^n $$
である（$\prod_i(e^s+e^{-s})$ を展開すると、各 $\omega$ に対応する項がちょうど 1 つずつ現れる）。$(2k)!=k!\,(k+1)(k+2)\cdots(2k)\ge k!\,2^k$ なので
$$ \cosh s=\sum_{k=0}^\infty\frac{s^{2k}}{(2k)!}\le\sum_{k=0}^\infty\frac{(s^2/2)^k}{k!}=e^{s^2/2} $$
である。thm-mi-general の後半（$g(x)=e^{sx}$）により
$$ P(S_n\ge a)\le e^{-sa}E[e^{sS_n}]\le\exp\Bigl(-sa+\frac{ns^2}2\Bigr) $$
であり、右辺の指数は $s=\frac an$ で最小値 $-\frac{a^2}{2n}$ をとる。$\blacksquare$

$n=100$、$a=30$ で評価を比べると次のようになる（実際の確率は $S_{100}\ge30$、すなわち表が $65$ 回以上の二項分布の確率）。

評価	使う情報	$P(S_{100}\ge30)$ の上界
Chebyshev の不等式（両側）	分散 $V[S_{100}]=100$	$\frac{100}{900}=0.111$
片側の Chebyshev の不等式	分散	$\frac{100}{100+900}=0.1$
prop-mi-rademacher	積率母関数	$e^{-4.5}=0.0111$
実際の確率	分布そのもの	$0.00176$

同じ方法を独立な確率変数の和に一般に使うのが Cramérの定理(大偏差) の上からの評価である。

測度論での使い道

値が $[0,\infty]$ の可測関数 $f$ について $\int_Sf\,dm=0$ なら、$\{f>0\}=\bigcup_{k\ge1}\{f\ge\frac1k\}$ の各集合の測度は thm-mi-main により $k\int f\,dm=0$ 以下なので、可算劣加法性から $m(\{f>0\})=0$ である。同様に $\int f\,dm<\infty$ なら、$m(\{f=\infty\})\le m(\{f\ge k\})\le\frac1k\int f\,dm\to0$ である。この 2 つは Lebesgue積分の補題「零集合と積分」の 2 にあたり、thm-mi-sharp の 1 や prop-mi-little-o の証明で使った事実である。$L^p$ 収束から測度収束が従うこと（Chebyshevの不等式の系「$L^p$ 収束から測度収束へ」）も、$\psi(x)=x^p$ の場合からすぐに出る。

逆向きの評価

Markov の不等式は上からの評価だけで、期待値が大きくても $X$ が大きくなる確率は小さいことがある（下の表の 3 行目）。2 次の積率も使えば、下からの評価が得られる。

Paley–Zygmund の不等式

確率変数 $X\ge0$ が $0< E[X^2]<\infty$ を満たすとし、$0\le\theta< 1$ とする。このとき
$$ P\bigl(X>\theta\,E[X]\bigr)\ge(1-\theta)^2\frac{E[X]^2}{E[X^2]} $$
である。とくに $P(X>0)\ge\dfrac{E[X]^2}{E[X^2]}$ である。

小さい部分と大きい部分に分ける

$B:=\{X>\theta E[X]\}$ とおく。$B^c$ の上では $X\le\theta E[X]$ なので
$$ E[X]=E[X\mathbf 1_{B^c}]+E[X\mathbf 1_B]\le\theta E[X]+\sqrt{E[X^2]\,P(B)} $$
である。最後の項は $E[X\mathbf 1_B]$ に Cauchy–Schwarzの不等式の命題「期待値の形と相関係数」の 1 の不等式 $E[UV]^2\le E[U^2]E[V^2]$ を $U=X$、$V=\mathbf 1_B$ に使った（$E[\mathbf 1_B^2]=P(B)$）。よって $(1-\theta)E[X]\le\sqrt{E[X^2]P(B)}$ で、左辺は $0$ 以上なので 2 乗して $E[X^2]>0$ で割ればよい。$\blacksquare$

置換の不動点

$n\ge2$ 個のものの置換を一様に選び、不動点の個数を $X$ とする。$i$ が不動点である確率は $\frac1n$、$i\ne j$ がともに不動点である確率は $\frac1{n(n-1)}$ なので、指示関数の和に分けて $E[X]=1$、$E[X(X-1)]=n(n-1)\cdot\frac1{n(n-1)}=1$、$E[X^2]=2$ である。Markov の不等式は $P(X\ge1)\le1$ しか与えないが、prop-mi-paley-zygmund は $P(X\ge1)=P(X>0)\ge\frac12$ を与える。実際の確率は $n\to\infty$ で $1-e^{-1}=0.632\ldots$ に近づく。

条件を外したときの反例

外す条件・誤った推論	反例	成り立たなくなること
値が $0$ 以上	$X$ が $-3$ と $1$ を確率 $\frac12$ ずつとる	$E[X]=-1$ で、$P(X\ge1)=\frac12>\frac{E[X]}1$
逆：裾の評価から可積分性	$X$ が密度 $x^{-2}$（$x\ge1$）をもつ	すべての $a>0$ で $P(X\ge a)\le\frac1a$ だが $E[X]=\infty$
期待値が大きければ大きな値をとりやすい	$X_n$ が $n^2$ を確率 $\frac1n$、$0$ を確率 $1-\frac1n$ でとる	$E[X_n]=n\to\infty$ だが $P(X_n\ge1)=\frac1n\to0$

表の反例の確かめ

3 つの反例の確かめを開く

1 行目：$E[X]=\frac{-3+1}2=-1$ で、$P(X\ge1)=P(X=1)=\frac12$ である。満たさないのは「値が $0$ 以上」だけで、$\lvert X\rvert$ に使えば $P(\lvert X\rvert\ge1)=1\le E[\lvert X\rvert]=2$ と正しい。

2 行目：$a\ge1$ なら $P(X\ge a)=\int_a^\infty x^{-2}\,dx=\frac1a$、$0< a< 1$ なら $P(X\ge a)=1<\frac1a$ である。一方 $E[X]=\int_1^\infty x\cdot x^{-2}\,dx=\infty$ である。Markov の不等式は「可積分なら裾が $\frac{C}{a}$ 以下」を言うが、その逆は成り立たない。prop-mi-little-o により、可積分なら $aP(X\ge a)\to0$ なので、この $X$ が可積分でないことはそこからも分かる。

3 行目：$E[X_n]=n^2\cdot\frac1n=n$、$P(X_n\ge1)=\frac1n$ である。$E[X_n^2]=n^3$ なので $\frac{E[X_n]^2}{E[X_n^2]}=\frac1n$ で、prop-mi-paley-zygmund の下界 $P(X_n>0)\ge\frac1n$ は等号で成り立つ。下からの評価には 2 次の積率の情報が欠かせない。

補足

名前。 呼び分けは文献によって異なる。Dur19 は thm-mi-general にあたる一般形を Chebyshev の不等式と呼び（Theorem 1.6.4、p. 29）、この結果を Markov の不等式と呼んで $\psi(x)=x^2$ の場合だけを Chebyshev の不等式と呼ぶ著者もいると注意している（p. 30）。この記事は後者の呼び方に従い、Chebyshevの不等式の記事も $\psi(x)=x^2$ を偏差 $X-E[X]$ に使った形をその名で呼ぶ。また、次数 $n$ の実係数多項式 $p$ について $\max_{[-1,1]}\lvert p'\rvert\le n^2\max_{[-1,1]}\lvert p\rvert$ とする多項式の Markov の不等式は、名前が同じだけの別の定理である。
位置づけ。 Markov の不等式が使う情報は期待値だけなので、得られる評価は粗い。分散を使えば Chebyshevの不等式、独立な和の積率母関数を使えば指数型の評価と、情報を増やすほど評価は鋭くなり、その極限が中心極限定理と大偏差の理論である。どの段階でも、最後に使うのはこの記事の 1 行の証明である。