MIT OCW, Fundamentals of Probability 19日目 大数の法則と中心極限定理

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 18. Laws Of Large Numbers

• Lecture 18. Laws Of Large Numbers
  • 1. Useful Inequations
    • • Markov Inequality
      • Chevbyshev Inequality
  • 2. The Weak Law of Large Numbers
    • • Proposition 19-1
      • Theorem 18-1 The Weak Law of Large Numbers (証明略)
      • Theorem 19-1 The Strong Law of Large Numbers
    • 18-3 The Central Limit Theorem (中心極限定理)
      • Theorem 18-2 Central Limit Theorem, CLT
  • 19-2. The Chernoff Bound
    • 19-2.1 Upper Bound
      • Theorem 19-2 (Chernooff Upper Bound) (証明略)
      • Example
    • 19-2.2 Lower Bound
      • Assumption 19-1.
      • Theorem 19-3 (Chernoff Lower Bound)

1. Useful Inequations

Markov Inequality

$X$が非負なrandom variableなら
$$P(X \geq a) \leq E[X]/a$$

proof.

$$I_{\{X\geq a\}} \leq X/a$$
が必ず成立する.両辺のexpectationを考えれば直ちに成立.

Chevbyshev Inequality

$$P(|X - E[X]| \geq \epsilon) \leq var[X]/\epsilon^2$$

proof.

Markov inequalityで,$X = |X-E[X]|$, $a = \epsilon^2$とすれば直ちに成立.

2. The Weak Law of Large Numbers

expectationは無限回の試行の結果の平均と考えることが出来る. “有限回の試行の結果の平均(sample mean)はexpectationに近づく”ということの定式化がlaw of large numbers (大数の法則)である.
大数の弱法則と大数の強法則があり,後者は前者を導く.大数の強法則を僅かに弱くして証明し,弱法則をも導く.まずalmost sure convergenceの証明に使う補題を示す.

Proposition 19-1

$\{X_n\}$をrandom variableの列とする.独立性は仮定しない.
(i) $\sum E[|X_n|^s] < \infty, s>0 \Rightarrow X_n \rightarrow^\text{a.s.} 0$
(ii) $\forall \epsilon>0, \sum P(|X_n|>\epsilon) < \infty \Rightarrow X_n \rightarrow^\text{a.s.} 0$

proof.

(i)
$\sum_{n=1}^\infty E[|X_n|^s] =E[\sum_{n=1}^\infty |X_n|^s <\infty$がmonotone conergence theoremから成立し,ゆえに$\sum_{n=1}^\infty |X_n|^s$というrandom variableは確率1で有限. したがって$|X_n|^s \rightarrow^\text{a.s.} 0$であり,$X_n \rightarrow^\text{a.s.} 0$.
(ii)
任意の$k \in \mathbb{N}$を取って$\epsilon = 1/k$とする. Borel-Cantelli lemmaから$P(\{|X_n| > 1/k \text{ i.o.}\})=0$すなわち$\{|X_n|>1/k\}$というeventは確率1で有限回のみ起こる. したがって$P(\limsup X_n > 1/k) = 0$が任意の$k$に成立する.$\{\limsup |X_n|>1/k\}$は単調で$P(\{\limsup X_n > 0\})=0$に収束する.よって$X_n \rightarrow^\text{a.s.}0$

Theorem 18-1 The Weak Law of Large Numbers (証明略)

$\{X_n\}$がi.i.d.で$E[|X_1|] < \infty$ならば,$S_n = \sum_{i=1}^n X_i$とすると
$$\frac{S_n}{n} \rightarrow^\text{i.p.} E[X_1]$$

Theorem 19-1 The Strong Law of Large Numbers

Theorem 18-1の仮定のもとで
$$\frac{S_n}{n} \rightarrow^\text{a.s.} E[X_1]$$

proof.

$E[X^4] < \infty$を前提に加える. このとき$E[|X|] <\infty$. $|X| \leq 1+x^4$から
$$E[|X|] \leq 1 + E[X^4] < \infty$$
$E[X] = 0$を仮定し,$E[\sum (X_1 + \cdots X_n)^4/n^4] < \infty$を示す.
まず
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] = \frac{1}{n^4} \sum_{i_1=1}^n \sum_{i_2=1}^n \sum_{i_3=1}^n \sum_{i_4=1}^n E[X_{i_1}X_{i_2}X_{i_3}X_{i_4}]$$
であって,i.i.d.だから,random variableたちの少なくとも１つが他のすべてのrandom variableと異なるとき$E[X_{i_1}X_{i_2}X_{i_3}X_{i_4}] = 0$. したがって,上の式で$0$出ない項は$E[X_i^4]$あるいは$E[X_i^2X_j^2] \ (i \neq j)$という形をしている. $E[X_i^4]$となる$i$は$n$通りで,$E[X_i^2X_j^2] \ (i \neq j)$となる$i, j$の組み合わせは$3n(n-1)$通りある.以上から
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] = \frac{nE[X_1^4] + 3n(n-1)E[X_1^2 X_2^2]}{n^4}$$
が成立する.$xy \leq (x^2 + y^2)/2$に$x=X_1^2, y=X_2^2$を代入して$X_1^2X_2^2 \leq X_1^4+X_2^4$,expectationをとって$E[X_2^4] = E[X_1^4]$を考えれば$E[X_1^2X_2^2] \leq E[X_1^4]$が成立する.ゆえに
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] \leq \frac{3n^2 E[X_1^4]}{n^4}=\frac{3E[X_1^4]}{n^2}$$
したがって
$$E\left[\sum_{n=1}^\infty\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] \leq 3E[X_1^4]\sum_{n=1}^\infty \frac{1}{n^2} < \infty$$
ゆえに$(X_1 + \cdots + X_n)^4/ n^4$は確率1で$0$に収束し,$(X_1 + \cdots +X_n)/n$もそうである.これがStrong law of large numbersの主張するところだった.
$E[X_i] \neq 0$である場合,$(X_1 + \cdots + X_n - nE[X_1])/n$が$0$にa.s.収束することは$(X_1 + \cdots + X_n) / n$が$E[X_1]$にa.s.収束することだから,成立.

$E[X^4]<\infty$の仮定を外した場合の証明は省略する.

18-3 The Central Limit Theorem (中心極限定理)

Theorem 18-2 Central Limit Theorem, CLT

$X_1, ...$がi.i.d.で,そのexpectationとvarianceをそれぞれ$\mu< \infty, \sigma^2<\infty$とする.$S_n = X_1 + \cdots +X_n$とすると,
$$\frac{S_n - n\mu}{\sigma\sqrt{n}}$$
が$N(0, 1)$にdistribution convergenceする.

proof.

簡単のため$\mu = 0, \sigma^2 = 1$とする. 1,2次のmomentが有限であることから,$\phi_{X_1}(t)$は$0$において２回微分可能である.
$$\phi_X(t) = 1 - t^2/2 + o(t^2)$$
と書ける.$S_n /\sqrt{n}$のcharacteristic functionは
$$(\phi_X(t/\sqrt{n}))^n = (1 - t^2/2n + o(t^2/n))^n$$
という形をしていて,$t$を固定して$n\rightarrow \infty$の極限は$e^{-t^2/2}$である.これは$N(0,1)$のcharacteristic function$\phi_Z$に等しい.$\phi_{S_n /\sqrt{n}}(t) \rightarrow \phi_Z(t) \forall t$から,たしかにdistribution convergenceが言えた.

CLTは$S_n/$のPDFはCDFについて何も言っていないが,以下の2つの命題が成り立つ.
(a)

$\int|\phi_{X_1}(t)|^r dt < \infty$が成立する$r$があるとき,$S_n$は$n\geq r$で連続で
$(S_n-\mu_n)/(\sigma\sqrt{n})$のPDF$f_n$は$N(0,1)$のPDFに一様収束($\Rightarrow$各点収束)する.すなわち
$$\lim_n \sup_z |f_n(z) - \frac{1}{\sqrt{2\pi}} e^{-z^2/2}|=0$$
である.

(b)

$a, h$を定数,$k$を整数として,$X_i$が$a+hk$という値を取り,$E[X]=0, var[X]=1$とする. $z=(na+kh)/\sqrt{n}$という形の$z$に,
$$\lim \frac{\sqrt{n}}{h} P(S_n=z) = \frac{1}{2\pi}e^{-z^2/2}$$
である.

19-2. The Chernoff Bound

$X, X_1, ...$はi.i.d.で,$S_n = X_1 +\cdots X_n$とする.$E[X]=0$とする. (weak) law of large numbers から, $P(S_n \geq na) \rightarrow 0$が任意の$a>0$で成立.この収束を上下から押さえる関数を与えたい.

19-2.1 Upper Bound

$M(s) = E[e^{sX}]$として,$M(s) <\infty$が$s \in [0, c], c>0$で成り立つとする.
$M_{S_n}(s) = E[e^{s(X_1 +\cdots +X_n)}]=(M(s))^n$. 任意の$s>0$にMarkov inequalityを使って,
$$P(S_n \geq na) = P(e^{sS_n}\geq e^{nsa})\leq e^{nsa}E[e^{sS_n}] = e^{-nsa}(M(s))^n$$
($c <s$では右辺が$\infty$になってしまうが不等号自体は成立する)
$P(S_n \geq a)$が$n$とともに指数的に減少することがわかったが,$s$を操作してより狭い境界を与える.

Theorem 19-2 (Chernooff Upper Bound) (証明略)

ある$s>0, a>0$で$E[e^{sX}] < \infty$ならば,
$$P(S_n\geq na) \leq \exp[n\underline{\sup_{s\geq 0} (sa-\log M(s))}_{\phi(a)}]$$

$s=0$では$sa-\log M(s) = 0 - \log 1 = 0$
また
$$\frac{d}{ds} (sa-\log M(s))|_{s=0} = a - \frac{1}{M(s)} \frac{d}{ds} M(s)|_{s=0}=a - 1E[X] = a> 0$$
$sa-\log M(s)$は$s=0$で$0$をとり,微分係数は正だから,十分小さい$s>$で正の値を取る. $\phi(a)>0$であって,$a>0$を固定すると$P(S_n \geq na)$は$n$によって指数的に減少する.

Example

$X \sim N(0, 1)$について,$M(s) = e^{s^2/2}$. したがって$sa - \log M(s)=sa-s^2/2$ これの最小値は$\phi(a) = a^2/2$.これは
$$P(X \geq a) \leq e^{-a^2/2}$$
を与える.

19-2.2 Lower Bound

Assumption 19-1.

(i) $\forall s \ M(s) = E[^sX] < \infty$
(ii) random variable $X$はcontinuous で, PDFは$f_X$
(iii) $X$は有限の上限,下限を持たない.すなわち$0 < F_X(x) < 1, \forall x\in \mathbb{R}$

Theorem 19-3 (Chernoff Lower Bound)

Assumption 1のもとで,任意の$a > 0$に
$$\lim_{n\rightarrow \infty} \frac{1}{n} \log P(S_n \geq na) = -\phi(a)$$