Let
$\displaystyle X_1,\cdots,X_n$ be
i.i.d. Bernoulli RVs with parameter
$\displaystyle p.$
Let
$\displaystyle S_n=\sum_{i=1}^n X_i,$
$\displaystyle \mu=E[S_n]=np.$
Then,
$\displaystyle \mathbb{P}(S_n\ge(1+\varepsilon)\mu)\le\left(\frac{e^{-\varepsilon}}{1+\varepsilon}\right)^{1+\varepsilon},\;\;\;\;\forall\varepsilon>0$
$\displaystyle \mathbb{P}$ 안의 내용
$\displaystyle S_n\ge(1+\varepsilon)\mu$ 을 다시 쓰면
$\displaystyle S_n-\mu\ge\varepsilon\mu$
즉, 평균에서
$\displaystyle \varepsilon\mu$ 만큼 벗어날 확률이 오른쪽 식만큼 bound가 된다.
또 다른 theorem:
$\displaystyle \mathbb{P}(S_n\le(1-\varepsilon)\mu)\le\left(\frac{e^{-\varepsilon}}{1-\varepsilon}\right)^{1-\varepsilon},\quad\quad 0<\varepsilon<1.$
증명에 앞서
(independent하면)
$\displaystyle E[XY]=E[X]E[Y]$
일반적으로
$\displaystyle E\left[\prod_i X_i\right]=\prod_i E[X_i]$
곱하기의 평균 = 평균의 곱하기
Proof)
$\displaystyle \mathbb{P}(S_n\ge(1+\epsilon)\mu)$
$\displaystyle =\mathbb{P}(tS_n\ge(1+\epsilon)\mu t)$
$\displaystyle =\mathbb{P}(e^{tS_n}\ge e^{(1+\epsilon)\mu t})$ Markov ineq.를 적용하면,
$\displaystyle \le\frac{E[e^{tS_n}]}{e^{(1+\epsilon)\mu t}}$
우변을 풀어서 써보면
$\displaystyle =e^{-(1+\epsilon)\mu t}E\left[\prod_{i=1}^n e^{tX_i}\right]$ 위의 independent 성질을 이용하면
$\displaystyle =e^{-(1+\epsilon)\mu t}\prod_{i=1}^n E[e^{tX_i}]$ (∵ independence of Xi's)
$\displaystyle =e^{-(1+\epsilon)\mu t}\prod_{i=1}^n\left( p\cdot e^t + (1-p) \right)$
$\displaystyle =e^{-(1+\epsilon)\mu t}\prod_{i=1}^n\left( 1+(e^t-1)p \right)$
부등식
$\displaystyle 1+x\le e^x$ 를 이용하면
$\displaystyle \le e^{-(1+\epsilon)\mu t}\prod_{i=1}^n e^{(e^t-1)p}$
$\displaystyle =e^{-(1+\epsilon)\mu t}e^{(e^t-1)\mu}$
$\displaystyle =e^{-(1+\epsilon)\mu t+e^t\mu-\mu$
이 값을 최소화하려면, upper bound가 작으면 작을수록 좋으니까, t에 대해 미분해서 값이 0이 될 때를 생각하면
minimized at
$\displaystyle t=\log(1+\epsilon)$
$\displaystyle =e^{(-(1+\epsilon)\log(1+\epsilon)+1+\epsilon-1)\mu}$
$\displaystyle =e^{(\log(1+\epsilon)^{-(1+\epsilon)}+\epsilon)\mu}$
$\displaystyle =e^{\mu\log((1+\epsilon)^{-(1+\epsilon)}e^{\epsilon})$
$\displaystyle =\left(\frac{e^{\epsilon}}{(1+\epsilon)^{1+\epsilon}}\right)^{\mu}$
$\displaystyle \mathbb{P}(S_n\ge(1+\epsilon)\mu)\le\left(\frac{e^{ \epsilon}}{(1+\epsilon)^{1+\epsilon}}\right)^{\mu}\le e^{-\frac{\epsilon^2\mu}{3}}$
$\displaystyle \mathbb{P}(S_n\ge(1-\epsilon)\mu)\le\left(\frac{e^{-\epsilon}}{(1-\epsilon)^{1-\epsilon}}\right)^{\mu}\le e^{-\frac{\epsilon^2\mu}{2}}$
$\displaystyle (1-\epsilon)^{1-\epsilon}>\exp(-\epsilon+\frac12\epsilon^2)$
$\displaystyle (1-\epsilon)\log(1-\epsilon)>-\epsilon+\frac12\epsilon^2$
(from 이향원 건대강의)
(from 이향원
건대강의(http://kocw.net/home/search/kemView.do?kemId=991018))