私以为大数定律是整个概率论中最重要也最核心的定律之一。它是整个概率论成立的基础。本章是对MIT的stochastic process第一章的整理。
在上stochastic process之前，以我对本科概率论的残存记忆来看，一直以为大数定律就是频率=概率。现在再看，比这个等式复杂了许多。
数学基础
在说大数定律之前，我们首先需要了解概率论的一些基本知识。当然了，概率，期望，方差那些基本的就不说了。
期望的第二种算法
对了，说到期望，期望还有一种计算方式(第一种就不说了吧)：
$$\begin{equation}
E[X] = \int_{-\infty}^0 -F_X(x)dx + \int_0^\infty (1-F_X(x))dx
\end{equation}$$
证明的话看下面这张图就行了：
Indicator rv
对于任何一个时间A，它的Indicator rv $$\mathbb{I}_A=\begin{cases} 0& w \in A\\ 1& w \notin A \end{cases}$$
Moment generating function(MGF)
一个随机变量的MGF定义为：
$g_X(r) = E[e^{rx}] = \int^\infty_{-\infty} e^{rx} dF_X(x)= \int^\infty_{0} e^{rx} dF_X(x) + \int^0_{-\infty} e^{rx} dF_X(x)$
显而易见， $g_X(r)$ 并不是对于所有的r都存在的。对于正数r来说，必存在一个最大值 $r_+$ 使得对于所有的 $r \le r_+$ ，第一个积分存在；同理，必存在一个最小值 $r_-$ 使得对于所有的 $r \ge r_-$ ，第二个积分存在。所以我们可以找到一个区间 $I(x)=[r_-,r_+]$ ，在此范围内 $g_X(r)$ 恒存在。
我们对 $g_X(r)$ 求n阶导，可以发现：
$\dfrac{\partial^k}{\partial r^k} g_X(r) = \int^\infty_{-\infty} x^ke^{rx}dF_X(x)$
令r = 0，可以发现：
$\dfrac{\partial^k}{\partial r^k} g_X(r){\bigg|}_{r=0} = E[X^k]$
这就是它被称为moment generate function的原因。
一些基础的不等式
Markov inequality
对于 非负的rv Y，有
$P\left\{Y \ge y\right\} \le \dfrac{E[Y]}{y}$
Proof
- 下图给出了直观的证明：
或者可以采用Indicator rv证明：
易知：
$Y \ge y\mathbb{I}_{Y\ge y}$对两边求期望（由于y是常数，所以右边是对indicator rv求期望），可得
$E[Y] \ge yP\left\{Y\ge y\right\}$除一下就可以得到markov inequality
我们还可以得到 $\lim_{y \to \infty} yP\left\{Y\ge y\right\} = 0$
Chebyshev inequality
由markov inequality，我们可以得到：
$P\left\{(Z-E[Z])^2 \ge y\right\} \le \dfrac{\delta_Z^2}{y}$其中 $\delta_Z^2$ 表示Z的方差。
$P\left\{|Z-E[Z]| \ge \epsilon \right\} \le \dfrac{\delta_Z^2}{\epsilon}$
由上式，我们可以得到 Chebyshev inequality：
与 Markov inequality的区别：
- markov inequality需要非负的rv，但是chebyshev inequality没有这个限制
Chebyshev inequality使得rv 以平方的速度趋向均值而 markov inequality 是线性速度。
Chebyshev inequality在处理多个rv相加是尤其有用。在证明WLLN时会用到Chebyshev inequality
Chernoff bounds
同样从markov inequality出发，我们可以得到：
$P\left\{exp(rZ) \ge y\right\} \le \dfrac{g_Z(r)}{y}$
其中 $g_Z(r) = E[e^{rZ}], y > 0$ 。如果令 $y = e^{rb}$ ，我们可以得到：
$$P\left\{Z \ge b\right\} \le g_Z(r)exp(-rb)\quad 0<r \in I(Z)\\
P\left\{Z \le b\right\} \le g_Z(r)exp(-rb) \quad 0>r \in I(Z)$$
之所以会出现两种情况是因为 $e^{rZ} \ge e^{rb}$ 根据r的符号不同会得到不同的结果。
令 rv $S_n = X_1 + X_2 + ... + X_n$ 。则有：
$$P \left\{S_N\ge na\right\} \le {g_X(r)}^n exp(-rna) \quad 0<r \in I(Z)\\
P \left\{S_N\le na\right\} \le {g_X(r)}^n exp(-rna) \quad 0>r \in I(Z)$$
令 $\gamma_X(r)=ln g_X(r)$ 。这货被称为semi-invariant MGF(取个ln名字就又高上大了好多╮(￣▽￣”)╭)。
对 $\gamma_X(r)$ 在r=0处求导，可以发现 $\gamma_X'(0)=E[X], \gamma_X''(0)=\delta_X^2$ 。这是个典型的二次函数。如果X的期望大于0，那么我们可以画出 $\gamma_X(r)$ 的图像：
当然我们就可以把上面的不等式进一步化简：
$$P \left\{S_N\ge na\right\} \le exp[n(\gamma_X(r)-ra)] \quad 0<r \in I(Z)\\
P \left\{S_N\le na\right\} \le exp[n(\gamma_X(r)-ra)] \quad 0>r \in I(Z)$$
如果我们想要找到tightest bound，就需要找到式子右边的最小值。对右边的式子求导，我们可以发现： $\dfrac{\partial}{\partial r}(\gamma_X(r)-ra) = E[X]-a$ 。所以我们可以发现，对于r>0,a>E[X] 或者 r<0,a
$$P \left\{S_N\ge na\right\} \le exp[n\mu_X(a)] \quad \mu_X(a)<0 , a > E[x]\\
P \left\{S_N\le na\right\} \le exp[n\mu_X(a)] \quad \mu_X(a)<0 , a < E[x]$$
laws of large number
WLLN with finite variance
令 X 表示方差存在的rv， $S_n = X_1+X_2+...X_n$ ，其中所有的X为IID。有下式成立：
$\lim_{n \to \infty} Pr\left\{|\dfrac{S_n}{n}-\bar{X}| > \epsilon\right\} = 0$
central limit theorem
$X_1, X_2,...,X_n$ 是n个IID的rv，均值为 $\bar{X}$ ，方差为 $\sigma^2$ 。故对于每个实数 z，均有下式成立：$\lim_{n \to \infty} Pr\left\{\dfrac{S_n-n\bar{X}}{\sigma\sqrt{n}} \le z\right\} = \Phi(z)$
其中 $\Phi(z)$ 为高斯分布
WLLN
$S_n = X_1+X_2+...+X_n$ ，其中 $X_1, X_2,...,X_n$ 为IID rv，满足 $E[|X|] < \infty$ ，则$\lim_{n\to\infty} Pr\left\{|\dfrac{S_n}{n} - E[X]| > \epsilon\right\} = 0$
证明
我们基于原有的rv $X_i$ 定义截断(truncation)变量 $\hat{X}_i$ ：
$$\hat{X}_i=
\begin{cases}
X_i&E[X]-b \le X_i \le E[x]+b\\
E[X]+b & X_i > E[X]+b\\
E[X]-b & X_i < E[X]+b
\end{cases}$$
根Chebyshev inequality，有：
$Pr\left\{|\dfrac{\hat{S}_n}{n} -E[\hat{X}]|> \dfrac{\epsilon}{2}\right\} \le \dfrac {4\sigma_{\hat{X}}}{n\epsilon^2}$
其中
$$\begin{aligned}
\sigma_{\hat{X}} &= E{[\hat{X}-E[\hat{X}]]}^2 \le E[|\hat{X}-\bar{X}|][|\hat{X}-\bar{X}|]\\
&\le E[|\hat{X}-\bar{X}|][|\hat{X}-X| + |X -\bar{X}||]\\
&=E[|\hat{X}-\bar{X}||\hat{X}-X|] + E[|\hat{X}-\bar{X}||X -\bar{X}|]\\
&\le bE[|\hat{X}-\bar{X}|]\\
&\le 2bE[|X|]
\end{aligned}$$
所以原不等式可化为：
$Pr\left\{|\dfrac{\hat{S}_n}{n} -E[\hat{X}]|> \dfrac{\epsilon}{2}\right\} \le \dfrac{8bE[|X|]}{n\epsilon^2}$
又由E[X]的计算公式，可知：
$E[|\hat{X}-X|] = 2\int_{b}^{\infty} 1 - F_X(x) dx$
由于 $E[|X|]$ 存在，故 $\int_{b}^{\infty} 1-F_X(x)$ 趋向于0。故对于任何 $\epsilon$ ，必有b使得下式成立：
$E[\hat{X}-X] \le \dfrac{\epsilon}{2}$
故原不等式可以继续化简(hexo-math没有公式编号只能这样了。。。。。)为：
$Pr\left\{|\dfrac{\hat{S}_n}{n} -E[X]|> \epsilon\right\} \le \dfrac{8bE[|X|]}{n\epsilon^2}$
所以有：
$Pr\left\{|\dfrac{S_n}{n} -E[X]|> \epsilon\right\} \le Pr\left\{|\dfrac{\hat{S}_n}{n} -E[X]|> \epsilon\right\} + Pr\left\{S_n\neq \hat{S}_n\right\}$
其中 $Pr\left\{S_n\neq \hat{S}_n\right\} \le nPr\left\{|X_i-\bar{X}|>b\right\}$
带入原式，你就可以得到WLLN了
convergence of rv
convergence in distribution
$\lim_{n \to \infty} F_{Z_n}(z) = F_Z(z)$CLT就是典型的例子
convergence in probability
$\lim_{n \to \infty} Pr\left\{|Z_n-Z| > \epsilon\right\} = 0$convergence in mean square
$\lim_{n \to \infty} E[(Z_n-Z)^2] = 0$convergence with probability 1
$Pr\left\{w\in\Omega:\lim_{n\to\infty} Z_n(w) = Z(w)\right\}$但是需要特别注意的是这里convergence的意思。这里的convergence是指下图的这种：
对于下图的这种分布：
这种分布是convergence in probability，而不是convergence with probability 1。这一点需要特别注意。
四者关系
