Xを任意の確率変数とし、a>0とする。
Pr(|X|≥a)≤E[X]a
Markov's Inequalityより、Chernoff Boundsが得られる。
任意のt>0について、
Pr(X≥a)=Pr(etX≥eta)≤E[etX]eta
同様に、任意のt<0について、Pr(X≤a)=Pr(etX≥eta)≤E[etX]eta
X1,⋯,Xnを独立な確率変数とする。Pr(Xi=1)=Pr(Xi=−1)=1/2とする。
このとき、X=∑i=1nXiとする。
任意のa>0について、Pr(|X|≥a)≤2e−a2/2n
任意のt>0について、E[etXi]=12et+12e−t
etとe−tをマクローリン展開をして、
et=1+t+t2/2!+⋯+ti/i!+⋯
e−t=1−t+t2/2!+⋯+(−1)iti/i!+⋯
(2i)!=2i(2i−1)(2i−2)⋯≥2ii(i−1)(i−2)⋯=2i(i)!に注意して、
E[etXi]=12et+12e−t=∑i≥0t2i/(2i)!≤∑i≥0(t/2)i/i!=et2/2
E[etX]=E[et∑iXi]=∏i=1nE[etXi]≤ent2/2
それゆえ、Pr(X≥a)=Pr(etX≥eta)≤E[etX]/eta≤et2n/2−ta
t=a/nとおけば、Pr(X≥a)≤e−a2/2n
同様にして、Pr(X≤−a)≤e−a2/2n
よって、任意のa>0について、Pr(|X|≥a)≤2e−a2/2n
バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。