確率変数の中央値と期待値の差

確率集中不等式はしばし実数値確率変数$Z$に対して$\Pr[|Z-\mathbf{E}Z|\geq t]$の上界を与えますが, Talagrandの不等式に代表されるようなisoperimetric inequalityを考えると期待値$\mathbf{E}Z$の代わりに中央値$\mathbf{M}Z$を考えることがよくあります. ここで確率変数$Z$の中央値(median)とは, $\Pr[Z\geq \mathbf{M}Z]\geq 1/2$ かつ $\Pr[Z\leq\mathbf{M}Z]\leq 1/2$を満たす実数$\mathbf{M}Z$のことです. Isoperimetric inequalityを使うと$\Pr[|Z-\mathbf{M}Z|\geq t]$の上界を与えることができます.

平均値と中央値は一般に異なりますが, 例えば$Z$の分散が小さいとバラつきが小さいので $\mathbf{E}Z$と$\mathbf{M}Z$の間はそれほどギャップがないように思われます. この直感は実際正しく, 以下の事実が成り立ちます.

定理

$\mathbf{E}Z^2<\infty$を満たす確率変数$Z$に対し,

$$|\mathbf{M}Z-\mathbf{E}Z|\leq \sqrt{\mathrm{Var}Z}$$

本記事ではこの事実を証明していきます.

補題 (Cantelli's inequality)

任意の$t>0$に対し,

$$\Pr\left[\frac{Z-\mathbf{E}Z}{\sqrt{\mathrm{Var}Z}} \geq t\right] \leq \frac{1}{1+t^2}.$$

(補題の証明)

平行移動とスケーリングによって一般性を失わず$\mathbf{E}Z=0$, $\mathrm{Var}Z=1$と仮定してよい. すなわち, 平均0で分散1の確率変数$Z$に対して$\Pr[Z\geq t]\leq 1/(1+t^2)$を示せば良い.

マルコフの不等式より, 任意の$\lambda>0$に対して

$$\Pr[Z\geq t] \leq \Pr[(Z+\lambda)^2\geq (t+\lambda)^2] \leq \frac{\mathbf{E}Z^2+\lambda^2}{(t+\lambda)^2}=\frac{1+\lambda^2}{(t+\lambda)^2}.$$

関数$\lambda\mapsto \frac{1+\lambda^2}{(t+\lambda)^2}$は$\lambda=1/t$の時に最小化され, このとき$1/(1+t^2)$をとる (証明終).

(定理の証明)

補題において$t=1$を代入すると, $\Pr[Z\geq \mathbf{E}Z+\sqrt{\mathrm{Var}Z}] \leq 1/2$を得る. 中央値の定義より

$$\Pr[Z\geq \mathbf{E}Z+\sqrt{\mathrm{Var}Z}] \leq 1/2 \leq \Pr[Z\geq \mathrm{M}Z].$$

よって$\mathrm{M}Z\geq\mathbf{E}Z+\sqrt{\mathrm{Var}Z}$を得る.

一方, 新たな確率変数$-Z$に対して$t=1$として改めて補題を適用すると, $-1$倍しても分散は変わらないため, $\Pr[Z\leq \mathbf{E}Z-\sqrt{\mathrm{Var}Z}]\leq 1/2$となり, 同様にして$\mathrm{M}Z\leq\mathbf{E}Z-\sqrt{\mathrm{Var}Z}$を得る (証明終).

モーメント母関数のlogについて

実数値をとる確率変数 $X$ と適当な値$t\in\mathbb{R}$に対して, 確率$\Pr[X\geq t]$を抑えるときにモーメント母関数 (MGF: Moment Generating Function) を考えたくなります. 確率変数$X$のモーメント母関数は$M_X(c)=\mathrm{E}[e^{cX}]$で定義されます. これを使うと, 任意の$\lambda\geq 0$に対して

$\Pr[X\geq t] = \Pr[\lambda X \geq \lambda t] = \Pr[e^{\lambda X} \geq e^{\lambda t}] \leq e^{-\lambda t} M_X(\lambda)$

が成り立つ (最後の不等式ではMarkovの不等式を適用した) わけです. 一般に浸透された言い回しではありませんが, モーメント母関数のlogをとったものをここではlogMGFと呼ぶこととします. すなわち, 確率変数$X$のlogMGFは

$$\Psi_X(\lambda) = \log M_X(\lambda) = \log \mathrm{E}[e^{\lambda X}]$$

です. これを使うと任意の$\lambda\geq 0$に対して

$$\Pr[X\geq t] \leq \exp(-\lambda t + \Psi_X(\lambda))$$

となるので, 最適な$\lambda$をチューニングしたくなります. ここで$\Psi_X^*(t) = \sup_{\lambda\geq 0}\{\lambda t - \Psi_X(\lambda)\}$ を考えてやると,

$$\Pr[X\geq t] \leq \exp(-\Psi^*_X(t))$$

を得ますが, $\Psi_X^*(t)$をよくみると関数$\Psi_X(\lambda)$のルジャンドル変換っぽいことが分かります ($\sup$で動く$\lambda$の範囲が$\lambda\geq 0$でなく$\lambda\in\mathbb{R}$ならばルジャンドル変換と一致します. なお, $t\geq \mathrm{E}[X]$ならば, $\Psi_X^*(t)=\sum_{\lambda\in\mathbb{R}}\{\lambda t - \Psi_X(\lambda)\}$ となり, ルジャンドル変換と一致します).

$\Psi_X(\lambda)$の有名な性質として凸性が挙げられます. つまり, $S=\{\lambda>0\colon \Psi_X(\lambda)<\infty\}$とすると$\Psi_X(\lambda)$は$S$上で凸関数になっています. これは, $x,y\in S$を$0<x<y$を満たす実数として$p\in(0,1)$を任意に選んで$\Psi_X(px+(1-p)y)$をHölderの不等式を使って上から抑えることによって証明することができます.