概统-不等式与极限定理

概率不等式

Markov 不等式

Markov 不等式

$Y\ge 0$，则 $\forall a>0$，

$$P(Y\ge a)\le \frac{E(Y)}{a}$$

Proof

令

$$I=\{\begin{array}{r}1,Y\ge a\\ 0,Y<a\end{array}$$

则 $I\le \frac{Y}{a}$ 因此

$$P(Y\ge a)=E(I)\le \frac{E(Y)}{a}$$

Chebyshev 不等式

Chebyshev 不等式

$Var(Y)$ 存在，则 $\forall a>0$

$$P(|Y-E(Y)|\ge a)\le \frac{Var(Y)}{a^2}$$

Proof

$$P(|Y-E(Y)|\ge a)=P((Y-E(Y){)}^2\ge a^2)\le \frac{E((Y-E(Y){)}^2)}{a^2}=\frac{Var(Y)}{a^2}$$

• $Var(Y)=0\Rightarrow Y=E(Y)a.s.$
• $P(|Y-\mu |\ge k\sigma )\le \frac{1}{k^2}$

Chernoff 不等式

Chernoff 不等式

$\forall a>0,\forall t>0$，

$$P(Y\le a)\le \frac{E(e^{tY})}{e^{ta}}$$

Proof

$$P(Y\ge a)=P(e^{tY}\ge e^{ta})\le \frac{E(e^{tY})}{e^{ta}}$$

大数定律

$X_1,\dots ,X_n$ 独立同分布 $E(X_i)=\mu ,Var(X_i)=\sigma$ $\overline{X}=\frac{1}{n}{\sum }_{i=1}^n{X}_i$ $E(\overline{X})=\mu ,Var(\overline{X})=\frac{{\sigma }^2}{n}$

Khinchin 弱大数定律

$\forall ϵ>0$，

$$\underset{n\to \infty }{\lim }P(|\overline{X}-\mu |\ge ϵ)=0$$

Proof

$$P(|\overline{X}-\mu |\ge ϵ)\le \frac{Var(\overline{X})}{{ϵ}^2}=\frac{{\sigma }^2}{n{ϵ}^2}$$

• $\mu$ 未知，可以用 $\overline{X}$ 估计

依概率收敛

$\forall ϵ>0$，

$$P(|Y_n-Y|\ge ϵ)=0$$

则称 $Y_n$ 依概率收敛到 $Y$，记为 $Y_n\stackrel{P}{\to }Y$

Kolmogorov 强大数定律

$$P(\underset{n\to \infty }{\lim }\overline{X}=\mu )=1$$

几乎必然收敛

$$P(\underset{n\to \infty }{\lim }{Y}_n=Y)=1$$

则称 $Y_n$ 几乎必然收敛到 $Y$，记为 $Y_n\stackrel{a.s.}{\to }Y$

中心极限定理

中心极限定理

$X_1,X_2,\dots ,X_n$ 独立同分布，

$$\underset{n\to \infty }{\lim }P\left(\frac{\overline{X}-\mu }{\sigma /\sqrt{n}}\le x\right)=\Phi (x),\forall x\in \mathbb{R}$$

Proof

设 $\mu =0,\sigma =1$，$M(t)=M_X(t)$

$$E\left(\exp \left(t\frac{{\sum }_{i=1}^n{X}_i}{\sqrt{n}}\right)\right)=M^n\left(\frac{t}{\sqrt{n}}\right)$$ $$M\left(\frac{t}{\sqrt{n}}\right)=1+\frac{1}{2}\frac{t^2}{n}+o\left(\frac{t^2}{n}\right)$$ $$M^n\left(\frac{t}{\sqrt{n}}\right)\to e^{-t^2/2}$$

• ${\sum }_{i=1}^n{X}_i\stackrel{近似}{\sim }N(n\mu ,n{\sigma }^2)$
• $\overline{X}\stackrel{近似}{\sim }N(\mu ,{\sigma }^2/n)$

依分布收敛

$$\underset{n\to \infty }{\lim }{F}_{Y_n}(x)=F_Y(x)$$

称 $Y_n$ 依分布收敛于 $Y$，记为 $Y_n\stackrel{d}{\to }Y$

真实支持度 $p$ 未知，随机调查 $n$ 人，总人数为 $N$，$n\ll N$, 有放回抽样 $X_i\sim B(p)$ $P_n=\overline{X}=\frac{1}{n}{\sum }_{i=1}^n{X}_i$ 要求精度 $ϵ=0.03$，置信度 $1-\alpha =95\%$

$$P(|P_n-p|\ge ϵ)\le \alpha$$ $$P(|P_n-p|\ge ϵ)\approx 2\left(1-\Phi \left(\frac{ϵ}{\sqrt{\frac{p(1-p)}{n}}}\right)\right)\le \alpha$$

应用步骤

• 确定原分布的期望值和标准差
• 对于离散随机变量，需要加入修正项（$\pm 0.5$）
• 标准化后查表