MIT OCW, Discrete Stochastic Processes 02日目

Robert Gallager. 6.262 Discrete Stochastic Processes. Spring 2011. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture videoを要約していく.

• • Lecture 3. Laws of Large Numbers, Convergence
    • Markov, Chebychev, Chernoff bounds
      • Markov inequality
      • Chebyshev inequality
      • Chernoff bound
    • Convergence
      • Weak Law of Large Numbers
        • Definition
    • Central Limit Theorem

Lecture 3. Laws of Large Numbers, Convergence

Markov, Chebychev, Chernoff bounds

Markov inequality

$Y\geq 0, y > 0$なら
$$Pr(Y \geq y) \leq \frac{E[Y]}{y}$$

Chebyshev inequality

$\epsilon > 0$に
$$Pr(|Z-E[Z]|\geq \epsilon) \leq \frac{\sigma_Z^2}{\epsilon^2} = \frac{var[Z]}{\epsilon^2}$$

Chernoff bound

任意の$z>0, r>0$にmoment generationg function $g_Z(r) = E[e^{rZ}]$が定義されているなら,
$$Pr(Z\geq z) \leq g_Z(r)\exp(-rz)$$

proof.

$Y=e^{rZ}$とする. $E[Y]=g_Z(r)$で,$y>0$にMarkov inequalityを使って
$Pr(Y \geq y) \leq g_Z(r)/y$すなわち$Pr(e^{rZ}\geq y) \leq g_Z(r)/y$
$z=(\log y)/r \Leftrightarrow y = e^{rz}$と$z$を導入すると,$Pr(Z\geq z) \leq g_Z(r) \exp(-rz)$がたしかに成立.

Markov, Chebyshev, Chernoffを見比べると,Markovは$y^{-1}$, Chebyshevは$y^{-2}$に従って上限が小さくなるのに対し,Chernoffの上限は指数的に上限が小さくなる.これがChernoff boundの有用性の理由である.

Convergence

Weak Law of Large Numbers

$X_1, ..., X_n$はIIDで,$\bar{X}=E[X_1], \sigma^2 = \sigma_{X_1}^2$とする.
$S_n = X_1 + ...+X_n$とすると$\sigma_{S_n}^2 = n\sigma^2$である.
$S_n/n$の振る舞いを見る.
$var[S_n/n] = n\sigma^2/n^2=\sigma^2/n \rightarrow 0 ( n \rightarrow \infty)$だから
$\lim_{n\rightarrow \infty} E \left[ \left(\frac{S_n}{n}-X\right)^2 \right]=0$. これを$S_n/n$ converges in mean square to $\bar{X}$という. 前者はIIDでないときには成り立たないし,分散が存在しないときにも成り立たないが,このようなときでも実は後者は成立する.

Definition

$Y_1,...,Y_n$が$Y$にconverges in mean square to $Y$
$\Leftrightarrow \lim E[(Y_n-Y)^2]=0$

ここでChebishev’s inequalityを使って
$$Pr(|\frac{S_n}{n} - \bar{X}|\geq \epsilon) \leq \frac{\sigma^2}{n\epsilon^2} \rightarrow 0$$
以上より,weak law of large numbers(WLLN, 大数の弱法則)
$$\forall \epsilon >0. \ \lim_{n\rightarrow \infty} Pr(|\frac{S_n}{n}-\bar{X}|\geq \epsilon)) =0$$
が示せた. (IIDの仮定に注意,varianceは存在しなくても良い)これは$Pr(S_n/n \leq x)$のdistributionが$n$の極限で$x\leq \bar{X}$で0, $x \geq \bar{X}$で$1$をとるステップ関数になるということである

Central Limit Theorem

$$\lim_{n\rightarrow \infty} \left[Pr(\frac{S_n-n\bar{X}}{\sqrt{n}\sigma} \leq y ) \right] = \int^y_{-\infty} \frac{1}{\sqrt{2\pi}}\exp(-\frac{x^2}{2})dx$$