机器学习基础：大数定律与中心极限定理

机器学习必备基础知识，力求以最简洁的语言，描述最完整的内容。
很多知识没有深入剖析，也没必要深入剖析。大致了解知识框架之后，即可开始学习机器学习，有不懂的再回过头再仔细研究，驱动式学习才是最高效的学习。

极限理论

大数定律

• 揭示了随即变量平均值的收敛规律

• 依概率收敛

  设 { X n } \{X_n\} {Xn​}是一个随机变量序列，$X$为随机变量，若对任意给定实数$\epsilon >0$，都有
  lim ⁡ n → ∞ P { ∣ X n − X ∣ < ε } = 1 \lim_{n\to\infty}P\{|X_n-X|<\varepsilon \}=1 n→∞lim​P{∣Xn​−X∣<ε}=1
  则称 { X n } \{X_n\} {Xn​}依概率收敛于$X$，记为
  $$X_n->[P]X$$

  • 比如$X_n->[P]a$，就是说当$n\to +\infty$时，$X_n$落在$(a-\epsilon ,a+\epsilon )$内的概率越来越大，与极限的定义区分开！（极限中$X_n->a$是指对$\forall \epsilon >0,\exists n_0,当n>n_0,|X_n-a|<\epsilon$）

• 常用大数定律

切比雪夫大数定律

设 { X k , k = 1 , 2 , . . . } \{X_k,k=1,2,...\} {Xk​,k=1,2,...}为独立的随机变量序列，且有相同的数学期望$\mu$，及方差${\sigma }^2>0$，则
$$Y_n=\frac{1}{n}\sum _{k=1}^n{X}_k->[P]\mu$$
即对任给$\epsilon >0$，都有
lim ⁡ n → + ∞ P { ∣ Y n − μ ∣ < ε } = 1 \lim_{n\rightarrow+\infin}P\{|Y_n-\mu|<\varepsilon\}=1 n→+∞lim​P{∣Yn​−μ∣<ε}=1

• 证明：

  由切比雪夫不等式$P(|Y_n-E(Y_n)|⩾\epsilon )⩽\frac{D(Y_n)}{{\epsilon }^2}$

  即$P(|Y_n-E(Y_n)|<\epsilon )⩾1-\frac{D(Y_n)}{{\epsilon }^2}$

  这里$$\begin{gathered} E(Y_n)=\frac{1}{n}{\sum }_{k=1}^{n}E(X_k)=\mu \\ D(Y_n)=\frac{1}{n^2}{\sum }_{k=1}^{n}D(X_k)=\frac{{\sigma }^2}{n} \end{gathered}$$

  代回上式：
  $$\begin{gathered} P(|Y_n-\mu |<\epsilon )⩾1-\frac{{\sigma }^2}{n{\epsilon }^2},所以 \\ \underset{n\to +\infty }{\lim }P(|Y_n-\mu |<\epsilon )=1 \end{gathered}$$

伯努利大数定律

设进行$n$次独立重复试验，每次试验中事件$A$发生的概率为$p$，记$f_n$为$n$次试验中事件$A$发生的频率，则
$$\begin{gathered} f_n->[p]p,即 \\ \underset{n\to +\infty }{\lim }P(|\frac{n_A}{n}-p|<\epsilon )=1 \end{gathered}$$

• 证明

  设
  X i = { 1 , 第 i 次试验中事件 A 发生 0 , 第 i 次试验中事件 A 不发生 X_i=

  {1,第i次试验中事件A发生0,第i次试验中事件A不发生" role="presentation">{1,0,第i次试验中事件A发生第i次试验中事件A不发生$$\{\begin{array}{ll}1,& 第i次试验中事件A发生\\ 0,& 第i次试验中事件A不发生\end{array}$$
  Xi​={1,0,​第i次试验中事件A发生第i次试验中事件A不发生​
  则$E(X_i)=p,D(X_i)=p(1-p)$，那么就转化成了切比雪夫大数定律，有

  $$f_n=\frac{1}{n}\sum _{k=1}^n{X}_k->[P]p$$

辛钦大数定律

若 { X k , k = 1 , 2 , . . . } \{X_k,k=1,2,...\} {Xk​,k=1,2,...}为独立同分布随机变量序列，且$E(X_k)=\mu <\infty ,k=1,2,...$，则
$$Y_n=\frac{1}{n}\sum _{k=1}^n{X}_k->[P]\mu$$
看起来和切比雪夫大数定律差不多？那么再看一下该定律的推论：

若 { X i , i = 1 , 2 , . . . } \{X_i,i=1,2,...\} {Xi​,i=1,2,...}为独立同分布随机变量序列，且$E(X_1^k)<\infty$，则
$$\frac{1}{n}\sum _{i=1}^n{X}_i^k->[P]E(X_1^k)$$
即在独立同分布条件下，可以推至$k$次的情况也满足大数定律

• 大数定律给出了频率稳定性的严格数学定义，即大量独立随即观测的平均值依概率收敛于分布的期望值

中心极限定理

• 依分布收敛

  设随机变量序列$X_n(n=1,2,...)$和随机变量$X$的分布函数分别为$F_n(x)(n=1,2,...)$和$F(x)$，若在$F(x)$的所有连续点$x$上都有
  $$\underset{n\to \infty }{\lim }{F}_n(x)=F(x)$$
  则称随机变量序列 { X n } \{X_n\} {Xn​}依分布收敛于随机变量$X$，简记为
  $$X_n->[w]X$$
  依分布收敛的意思是，当$n$很大的时候，$X_n$的分布函数$F_n(x)$收敛于$F(x)$，也就是分布函数的收敛性，这是一种比较弱的收敛性，只能保证分布一致，无法保证概率密度对应一致。也就是二者之间可能不存在联系。（比如说抛硬币和袋子里一个白球一个黑球来摸，两者的分布相同，但是八竿子打不着的关系）

  • 现令$Y_n={\sum }_{k=1}^n{X}_k$，若$Y_n$的标准化$Y_n^{\ast }->[w]\xi \sim N(0,1)$，则称 { X n } \{X_n\} {Xn​}满足中心极限定理

• 几个常用的中心极限定理

独立同分布中心极限定理

设 { X n } \{X_n\} {Xn​}为独立同分布随机变量序列，若$E(X_k)=\mu <\infty ,D(X_k)={\sigma }^2>0,k=1,2,...$，则 { X n } \{X_n\} {Xn​}满足中心极限定理

根据上述定理，当$n$充分大时
lim ⁡ n → ∞ P { ∑ i = 1 n X i − n μ n σ ≤ x } = Φ ( x ) 或者 P { ∑ i = 1 n X i ⩽ x } ≈ Φ ( x − n μ n σ ) 其中 Φ ( x ) 是标准正态分布的分布函数 Φ ( x ) = P ( X ⩽ x ) = 1 2 π ∫ − ∞ x e − t 2 2 d t \lim_{n\to\infty}P\{\frac{\sum_{i=1}^nX_i-n\mu}{\sqrt{n}\sigma}\leq x\}=\Phi(x)\\ 或者P\{\sum_{i=1}^nX_i\leqslant x\}\approx\Phi(\frac{x-n\mu}{\sqrt{n}\sigma})\\ 其中\Phi(x)是标准正态分布的分布函数\\ \Phi(x)=P(X\leqslant x)=\frac{1}{\sqrt {2\pi}}\int _{-\infin}^x e^{-\frac{t^2}{2}}dt\\ n→∞lim​P{n ​σ∑i=1n​Xi​−nμ​≤x}=Φ(x)或者P{i=1∑n​Xi​⩽x}≈Φ(n ​σx−nμ​)其中Φ(x)是标准正态分布的分布函数Φ(x)=P(X⩽x)=2π ​1​∫−∞x​e−2t2​dt
解读一下这个式子，实际上是把$Y_n={\sum }_{i=1}^n{X}_i$进行了标准化后，得到的$Y_n^{\ast }$近似于标准正态分布，也就是说
$$\begin{gathered} Y_n^{\ast }=\frac{Y_n-E(Y_n)}{\sqrt{D(Y_n)}} \\ 其中E(Y_n)=E(\sum _{i=1}^n{X}_i)=\sum _{i=1}^{n}E(X_i)=n\mu \\ D(Y_n)=D(\sum _{i=1}^n{X}_i)=\sum _{i=1}^{n}D(X_i)=n{\sigma }^2 \\ 故Y_n^{\ast }=\frac{{\sum }_{i=1}^n{X}_i-n\mu }{\sqrt{n}\sigma } \end{gathered}$$
$Y_n^{\ast }$近似$\sim N(0,1)$，或者

$Y_n$近似$\sim N(n\mu ,n{\sigma }^2)$，再清晰点，
$$\sum _{i=1}^n{X}_i近似\sim N(E(\sum _{i=1}^n{X}_i),D(\sum _{i=1}^n{X}_i))$$
也就是说，$n$个独立同分布随机变量的和，当$n$足够大时，可以认为该和近似服从正态分布

拉普拉斯中心极限定理

设随机变量${\eta }_n,n=1,2,...$服从参数为$n,p(0<p<1)$的二项分布，则

$$\frac{{\eta }_n-np}{\sqrt{npq}}->\xi \sim N(0,1)$$

证明：

设
X i = { 1 , 第 i 次试验中事件 A 发生 0 , 第 i 次试验中事件 A 不发生 X_i=

Xi​={1,0,​第i次试验中事件A发生第i次试验中事件A不发生​
则$E(X_i)=p,D(X_i)=p(1-p),{\eta }_n={\sum }_{i=1}^n{X}_i$

转化成了独立同分布中心极限定理，得证