Processing math: 0%

2021年11月20日土曜日

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

確率集中不等式はしばし実数値確率変数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}を得る (証明終).



0 件のコメント:

コメントを投稿

講義資料をNotionで書いてみた

 プログラミング応用という名前の講義を受け持っており, そこで組合せ最適化のベーシックな話題とそのPythonでの実装を教えているのですが, 資料をNotionで書いてみました. 講義資料をNotionで公開しているのでアルゴリズムの基礎とかNP困難性とかを勉強したい人はどう...