0
応用数学解説
文献あり

Chernoff Boundsで遊んでみよう!

179
0

Markov's Inequality

Xを任意の確率変数とし、a>0とする。

Pr(|X|a)E[X]a

Chernoff Bounds

Markov's Inequalityより、Chernoff Boundsが得られる。

任意のt>0について、

Pr(Xa)=Pr(etXeta)E[etX]eta

同様に、任意のt<0について、
Pr(Xa)=Pr(etXeta)E[etX]eta

Chernoff Boundsの応用

X1,,Xnを独立な確率変数とする。
Pr(Xi=1)=Pr(Xi=1)=1/2とする。

このとき、X=i=1nXiとする。

任意のa>0について、
Pr(|X|a)2ea2/2n

任意のt>0について、
E[etXi]=12et+12et

etetをマクローリン展開をして、

et=1+t+t2/2!++ti/i!+

et=1t+t2/2!++(1)iti/i!+

(2i)!=2i(2i1)(2i2)2ii(i1)(i2)=2i(i)!に注意して、

E[etXi]=12et+12et=i0t2i/(2i)!i0(t/2)i/i!=et2/2

E[etX]=E[etiXi]=i=1nE[etXi]ent2/2

それゆえ、
Pr(Xa)=Pr(etXeta)E[etX]/etaet2n/2ta

t=a/nとおけば、
Pr(Xa)ea2/2n

同様にして、
Pr(Xa)ea2/2n

よって、任意のa>0について、
Pr(|X|a)2ea2/2n

参考文献

[1]
Michael Mitzenmacher and Eli Upfal, Probability and Computing
投稿日:2024327
更新日:2024327
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

hdk105
hdk105
14
15060
計測・制御・情報に興味があります. 備忘録として残していきます.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. Markov's Inequality
  2. Chernoff Bounds
  3. Chernoff Boundsの応用
  4. 参考文献