Markov & Chebyshev Inequality
示性函数
\[\mathbb{I}(A) = \begin{cases} 1, & A \text{ happen } \\ 0, & A \text{ not happen} \end{cases} \]对于事件\(A\)，如果对于样本点\(\omega\)有示性函数
\[I_A(\omega) = \begin{cases} 1, & \omega \in A \\ 0, & \omega \notin A \end{cases} \]那么可以证明
\[\mathbb{E}[I_A] = 1 \times P(A) = \sum_\omega I_A(\omega) \times P(\omega) = P(A) \]Markov Inequality
如果\(X\)是一个非负随机变量，那么对于任意的\(a > 0\)，有
\[P(X \geq a) \leq \frac{\mathbb{E}[X]}{a} \]这个不等式粗略刻画了随机变量取值大于等于\(a\)的概率上界。
proof
我们定义示性函数，固定正数\(a\)，那么有
\[\mathbb{I}(X \geq a) = \begin{cases} 1, & X \geq a \\ 0, & X < a \end{cases} \]那么我们可以得到:
\[\mathbb{I}(X \geq a) \leq \frac{X}{a} \]因此我们可以得到一个不等式
\[P(X \geq a) = \sum_x P(x) \mathbb{I}(X \geq a) \leq \sum_x P(x) \frac{X}{a} = \frac{\mathbb{E}[X]}{a} \]proof end
Chebyshev Inequality
如果\(X\)是一个随机变量，那么对于任意的\(\epsilon > 0\)，有
\[P(|X - \mathbb{E}[X]| \geq \epsilon) \leq \frac{\text{var}(X)}{\epsilon^2} \]这个不等式粗略刻画了随机变量取值与期望值的偏离程度。使用了随机变量的期望与方差的信息。
proof
我们定义示性函数
\[\mathbb{I}((X - \mathbb{E}[X])^2 \geq \epsilon^2) = \begin{cases} 1, & (X - \mathbb{E}[X])^2 \geq \epsilon^2 \\ 0, & (X - \mathbb{E}[X])^2 < \epsilon^2 \end{cases} \]我们可知
\[\mathbb{I}((X - \mathbb{E}[X])^2 \geq \epsilon^2) \leq \frac{(X - \mathbb{E}[X])^2}{\epsilon^2} \]因此我们可以得到一个不等式
\[P(| X - \mathbb{E}[X] | \geq \epsilon) = P((X - \mathbb{E}[X])^2 \geq \epsilon^2) = \\ \sum_x P(x) \mathbb{I}((X - \mathbb{E}[X])^2 \geq \epsilon^2) \leq \sum_x P(x) \frac{(X - \mathbb{E}[X])^2}{\epsilon^2} = \frac{\text{var}(X)}{\epsilon^2} \]proof end
切比雪夫不等式并不要求随机变量非负
依概率收敛
数列的收敛
若对于任意的\(\epsilon > 0\)，存在\(N\)，当\(n > N\)时，有\(|a_n - a| < \epsilon\)，则称数列\(a_n\)收敛于\(a\)，记为\(\lim_{n \to \infin} a_n = a\)
随机变量序列的收敛
若对于任意的\(\epsilon > 0\)，有\(\lim_{n \to \infin} P(| Y_n - a | \geq \epsilon) = 0\)，则称随机变量序列\(Y_n\)依概率收敛于\(a\)，记为\(Y_n \xrightarrow{P} a\)
如果我们将其中的\(\lim\)展开，有
对于任意的\(\epsilon > 0\)，有对于任意的\(\delta > 0\)，存在\(N\)，当\(n > N\)时，有\(P(|Y_n - a| \geq \epsilon) < \delta\)，则称随机变量序列\(Y_n\)依概率收敛于\(a\)，记为\(Y_n \xrightarrow{P} a\)
Laws of Large Numbers
Weak Law of Large Numbers
弱大数定律是指，在大样本的情况下，样本的经验均值会以很大概率接近随机变量的期望。
我们考虑随机变量序列\(X_1, X_2, \cdots, X_n\).我们定义随机变量序列的经验均值为\(M_n = \frac{1}{N} \sum_{i=1}^n X_i\)，注意到\(M_n\)也是一个随机变量。
如果对于任意的\(\epsilon > 0\), 有
\[\lim_{n \to \infty} P(|M_n - \mathbb{E}[M_n ]| \geq \epsilon) = 0 \]则称随机变量序列\(X_1, X_2, \cdots, X_n\)满足弱大数定律。也称\(M_n\)依概率收敛于\(\mathbb{E}[M_n]\)
现在我们开始一一分析各个大数定律
限制方差的大数定律--马尔可夫大数定律
任取\(\epsilon > 0\)，有
\[P(|M_n - \mathbb{E}[M_n ]| \geq \epsilon) \leq \frac{\text{var}(M_n)}{\epsilon^2} \]其中\(\text{var}(M_n) = \frac{\text{var}(\sum_{i=1}^n X_i)}{n^2}\)，因此
\[P(|M_n - \mathbb{E}[M_n ]| \geq \epsilon) \leq \frac{\text{var}(\sum_{i=1}^n X_i)}{n^2 \epsilon^2} \]如果\(\lim_{n \to \infin} \frac{\text{var}(\sum_{i=1}^n X_i)}{n^2} = 0\), 那么\(M_n\)满足弱大数定律。
限制随机变量不相关+方差有界的大数定律--切比雪夫大数定律
如果在 Markov 大数定律中，我们假设\(X_i\)两两不相关，那么\(\text{var}(\sum_{i=1}^n X_i) = \sum_{i=1}^n \text{var}(X_i)\)
同时如果所有的\(X_i\)的方差都有上界\(\sigma^2\)，那么
\[P(|M_n - \mathbb{E}[M_n ]| \geq \epsilon) \leq \frac{\text{var}(\sum_{i=1}^n X_i)}{n^2 \epsilon^2} = \frac{\sum_{i=1}^n \text{var}(X_i)}{n^2 \epsilon^2} \leq \frac{n \sigma^2}{n^2 \epsilon^2} = \frac{\sigma^2}{n \epsilon^2} \]因此得到结论：如果\(X_i\)两两不相关，且有共同上界\(\sigma^2\)，那么\(M_n\)满足弱大数定律。
限制独立同分布+方差有限的大数定律
如果\(X_i\)是独立同分布的随机变量，且有限方差\(\sigma^2\)，那么
\[P(|M_n - \mathbb{E}[M_n ]| \geq \epsilon) \leq \frac{\text{var}(\sum_{i=1}^n X_i)}{n^2 \epsilon^2} = \frac{n \sigma^2}{n^2 \epsilon^2} = \frac{\sigma^2}{n \epsilon^2} \]满足弱大数定律,并且此时\(\mathbb{E}[M_n] = \mathbb{E}[X]\)
限制独立同分布+二项分布--伯努利大数定律
如果\(X_i\)是独立同分布的伯努利随机变量，那么\(M_n\)满足弱大数定律。
同时可以进行扩展，我们将一个事件\(A\)嵌入一个实行函数中，转换为一个伯努利随机变量，那么我们可以得到
\[\mathbb{E}[\frac{1}{n} \sum_{i=1}^n I_{A,i}] = \frac{1}{n} \sum_{i=1}^n \mathbb{E}[I_{A,i}] = \frac{1}{n} \sum_{i=1}^n P(A) = P(A) \]又因为\(I_{A,i}\)独立同分布且有限方差，因此\(M_n\)满足弱大数定律，可得\(A\)的频率收敛于概率。
方差无界的大数定律--辛钦大数定律
如果\(X_i\)是独立同分布且期望有界的随机变量，但是方差无界，那么\(M_n\)满足弱大数定律。
Strong Law of Large Numbers
强大数定律是指，样本的经验均值会以概率 1 收敛于随机变量的期望。
若有独立同分布的随机变量序列\(X_1, X_2, \cdots, X_n\)，那么
\[P(\lim_{n \to \infty} M_n = \mathbb{E}[X]) = 1 \]可以理解为，在一个无限序列 X_1, X_2, \cdots, X_n 的样本空间中，存在一个子集满足\(M_n = \mathbb{E}[X]\)，这个子集的概率为 1。
Central Limit Theorem
大数定律研究了随机变量序列的经验均值与期望之间的联系，而中心极限定理研究了随机变量序列经验均值的分布。
Lindeberg-Levy/独立同分布 Central Limit Theorem
如果\(X_i\)是独立同分布的随机变量，且有限期望\(\mu\)和方差\(\sigma^2\)，那么
\[\lim_{n \to \infty} P(\frac{\sum_{i=1}^n X_i - n\mu}{\sqrt{n}\sigma} \leq x) = \Phi(x) \]即\(M_n\)依分布收敛于正态分布。
独立不同分布下的中心极限定理
pass
参考
大数定律与中心极限定理
概率导论