04 大数定律

到目前为止，我们所作的只是构建“概率空间”、“随机变量”、“分布”、“期望”等概念在Kolmogorov公理体系下的数学定义。我们的讨论未曾涉及任何有关物理世界（现实）的事实。概率论只是一套数学理论，但概率论所讨论的数学定义则来源于物理世界。例如，我们会不假思索地承认“抛一枚均匀硬币，正面向上的概率是$1/2$”是真命题，但是这是一个经验结果，而不是概率论中的一个结论。在概率论中，我们通过把概率分布设置为$(1/2,1/2)$，建立一套概率空间，然后我们可以得出很多关于硬币的结论。这些结论可以应用到物理世界中并且能够被检验正确，因为这些结论的正确性依赖于概率论理论的正确性，以及“硬币正面向上的概率是$1/2$”这一经验事实。这一经验事实值得我们深入思考。假如在真空中由一台极其精确的机器来抛硬币（也即保证硬币被抛出时的初始运动状态总是完全相同），那么经典物理学会告诉我们硬币的结果是确定性的，而不是$1/2$的概率。但是，现实中由于人在发力时无法保证每一次施力都相同，且硬币受到空气中的气流与复杂的振动的干扰，导致抛硬币的结果变得无法预测。正是因为“抛硬币”这一物理过程具有“难以预测”的特点，所以人们喜欢把它当作一种获得“随机性”的方式。世界上各种各样的人在各种各样的地方做了许许多多次的实验，统计的结果告诉我们大约有将近一半次实验硬币正面朝上，一半次实验反面朝上。于是，人们做出“硬币正面向上的概率是$1/2$”这一论断，并且发现把这一论断结合概率论理论，得出的结论和现实符合得很好。

根据上面的过程，我们总结出这样一条法则：“将同一个动作重复足够多次，这一过程中某一结果出现的频率可以当作这一结果出现的‘概率’”。普通人只是把这条法则当作一种经验上的事实，但是数学家想要从数学上找到这条法则的依据。既然我们已经有了关于“概率”的严格定义，那么只需要定义清楚什么是“重复足够多次”，什么是“可以当作”，我们就可以从数学上验证这条法则。前者对应的就是分析学中的极限理论，后者对应的就是我们马上要介绍的随机变量的收敛理论。这条法则就被称为“大数定律(the Law of Large Numbers, LLN)”。

让我们通过抛硬币的例子直观理解一下这条法则将会具有怎样的形式。假设每一次抛硬币有$p$的概率向上，$1-p$的概率向下（注意，这个概率是物理世界的概率，并不是实验者提前已知的）。实验者进行$n$次实验，第$i$次实验结果记为$X_i$，其中$X_i=1$表示正面向上，$X_i=0$表示正面向下。实验者最终会计算$\dfrac{\sum_{i\in [n]}X_i}{n}$，并把它作为“认知上”的硬币正面向上的概率。数学家想要证明，当$n$足够大的时候，$\dfrac{\sum_{i\in [n]}X_i}{n}$的值和$p$是“接近”的。关键在于，如何从数学上定义这种“接近”：注意到，$\dfrac{\sum_{i\in [n]}X_i}{n}$是一个不确定的值，它的值取决于具体的实验结果。极端一点看，“实验者进行了一亿次实验，每次实验的结果都是正面向上”这样的事也是可能发生的，只不过可能性很小。所以，$\dfrac{\sum_{i\in [n]}X_i}{n}$和$p$的“接近”也只能是“概率性”的。

上面的例子中我们研究的是“事件的概率”，而通常我们所说的“大数定律”研究的是“随机变量的期望”。这二者其实是一回事，后者是前者的推广。我们可以把“硬币正面向上”看作一个事件，也可以把硬币的结果看作一个取值为$0$或$1$的随机变量$X$，那么“硬币正面向上的概率”就等于$\mathbb{E}[X]$。这样，大数定律就可以（不严格地）表述为：“进行$n$次实验，第$i$次实验结果记为$X_i$，那么当$n$足够大时$\dfrac{\sum_{i\in [n]}X_i}{n}$会有很大概率‘逼近’$\mathbb{E}[X]$”。

大数定律的意义不仅在于验证了上面这条经验法则，这条定律本身也具有巨大的应用价值。一旦我们能够将这条定律形式化，并且证明其正确性，我们就有了一套严格的根据“采样(sampling)”来估计“概率”的方法，它会告诉我们我们对概率的估计有多大的可能会成功，会产生多大的偏差等等。

随机变量的收敛形式

为了严格定义“接近”，我们下面介绍随机变量的收敛形式理论。

点态收敛

随机变量是概率测度空间上的可测函数，所以可以直接沿用测度论中可测函数列的点态收敛的定义，称为随机变量列点态收敛：如果$(\Omega,\mathcal{F},P)$上的随机变量$X$和随机变量列$X_1,X_2,\cdots$满足$\forall \omega \in \Omega,\lim\limits_{n\to\infty}X_i(\omega)=X(\omega)$，就称$\{X_i\}$点态收敛到$X$。

Almost Surely 点态收敛

在概率论中，经常使用的一种收敛模式称为“almost surely点态收敛”，简记为“a.s.点态收敛”或“a.s.收敛”。其定义为：如果$(\Omega,\mathcal{F},P)$上的随机变量$X$和随机变量列$X_1,X_2,\cdots$满足$\exists E \in \mathcal{F},P(E)=1\land \forall \omega \in E,\lim\limits_{n\to\infty}X_i(\omega)=X(\omega)$，就称$\{X_i\}$ a.s.收敛到$X$，记为$X_n \stackrel{a.s.}{\to} X$。

对于a.s.收敛的随机变量列，我们可以找到一个概率测度为$1$的集合，这个集合上随机变量列点态收敛。换言之，这个随机变量列只在一个零测集上不收敛。当我们并不关心随机变量在这个零测集上的表现时，我们就可以用a.s.收敛来放宽点态收敛的要求。

依概率收敛

如果$(\Omega,\mathcal{F},P)$上的随机变量$X$和随机变量列$X_1,X_2,\cdots$满足$\forall \varepsilon>0,$ $\lim\limits_{n \to \infty}P(|X_n-X|>\varepsilon)=0$，就称$X_n$依概率收敛(converge in probability)到$X$，记为$X_n \stackrel{p}{\to} X$。

我们需要仔细理解依概率收敛的定义。对于任意一个$n$，$X_n-X$是一个$(\Omega,\mathcal{F},P)$上的随机变量，所以对于任何一个固定的正实数，$|X_n-X|>\varepsilon$是一个事件，$P(|X_n-X|>\varepsilon)$是这个事件的概率。当$n$变化时，概率$P(|X_n-X|>\varepsilon)$也随之变化。如果对于任何固定的$\varepsilon$，这个概率当$n\to\infty$时都趋向$0$，那么就称$X_n$依概率收敛到$X$。直观上，依概率收敛意味着当$n$充分大时，$X_n$和$X$只在一个很小的样本集上有超过$\varepsilon$的偏差，这个样本集的测度随着$n$的增大而趋向0，同时$\varepsilon$还可以是任意小的。那么，依概率收敛和almost surely点态收敛是否是不同的收敛模式呢？我们需要用数学语言来证明。

下面证明，对于$(\Omega,\mathcal{F},P)$上的随机变量$X$和随机变量列$X_1,X_2,\cdots$，如果$X_n \stackrel{a.s.}{\to} X$，那么一定有$X_n \stackrel{p}{\to} X$。证明：根据$X_n \stackrel{a.s.}{\to} X$，所以存在$E\in \mathcal{F}$使得$P(E)=1$，$\forall \omega\in E,\lim\limits_{n\to\infty}X_n(\omega)=X(\omega)$。其中，$\lim\limits_{n\to\infty}X_n(\omega)=X(\omega)$当且仅当$\lim\limits_{n\to\infty}|X_n(\omega)-X(\omega)|=0$。因为$|X_n(\omega)-X(\omega)|$是非负数列，所以其极限为$0$当且仅当其上极限为0，也即$\lim\limits_{n\to\infty}\sup\limits_{k\geq n}|X_k(\omega)-X(\omega)|=0$。设$Z_n=\sup\limits_{k\geq n}|X_k(\omega)-X(\omega)|$（这也是一个随机变量），那么我们有$\forall \omega\in E,\lim\limits_{n\to\infty}Z_n(\omega)=0$。于是对于任意$\varepsilon>0$，设$\Gamma_n:=\{Z_n\geq \varepsilon\}$，那么$\forall \omega \in \bigcap\limits_{n\in \N}\Gamma_n$，有$\lim\limits_{n\to\infty}Z_n(\omega)\geq \varepsilon$，因此$\omega\not\in E$。可见$\bigcap\limits_{n\in \N}\Gamma_n\subseteq \Omega\setminus E$。由此可得$P(\bigcap\limits_{n\in \N}\Gamma_n)=0$。由概率测度的连续性可知$\lim\limits_{n\to\infty}P(\Gamma_n)=0$。也即$\lim\limits_{n\to\infty}P(Z_n\geq \varepsilon)=0$。也即$\lim\limits_{n\to\infty}P(\sup\limits_{k\geq n}|X_k(\omega)-X(\omega)|\geq \varepsilon)=0$。这意味着$\lim\limits_{n\to\infty}P(|X_n(\omega)-X(\omega)|\geq \varepsilon)=0$，也即$X_n \stackrel{p}{\to} X$。证毕。

下面证明，存在$(\Omega,\mathcal{F},P)$上的随机变量$X$和随机变量列$X_1,X_2,\cdots$，$X_n \stackrel{p}{\to} X$成立，而$X_n \stackrel{a.s.}{\to} X$不成立。反例：令$\Omega=[0,1],\mathcal{F}=\mathcal{B}([0,1]),P$为勒贝格测度。令$X$为全零函数。$\forall n \geq 1$，设$m = \lceil \log_2(n+1) \rceil - 1$，对于$k\in [1, 2^m]$，定义$X_n = \begin{cases} 1, & \omega \in [(k-1)\cdot 2^{-m}, k\cdot 2^{-m}) \\ 0, & \text{otherwise}. \end{cases}$。例如，$X_1=\mathbb{1}[\omega\in[0,1)]$,$X_2=\mathbb{1}[\omega\in[0,1/2)]$,$X_3=\mathbb{1}[\omega\in[1/2,1)]$,$X_4=\mathbb{1}[\omega\in[0,1/4)]$,$X_5=\mathbb{1}[\omega\in[1/4,1/2)]$,$X_6=\mathbb{1}[\omega\in[1/2,3/4)]$,$X_7=\mathbb{1}[\omega\in[3/4,1)]$,$X_8=\mathbb{1}[\omega\in[0,1/8)],\cdots$，依次类推。于是，我们发现对于任意$\omega\in [0,1)$，$X_n(\omega)$都是不收敛的，因为区间会“无穷次”扫过$\omega$所在的位置。

上面的这个反例直观地展现出a.s.点态收敛和依概率收敛的区别：a.s.点态收敛是说，取定一组测度为$1$的样本点，在这组固定的样本点上随着$n$的增大，$X_n$在每一个样本点上都趋向$X$；依概率收敛是说，随着$n$的增大，$X_n$趋向$X$的样本点集合的测度趋向$1$，但是这个样本点集合可能是在变化的过程中保持总测度为$1$，而无法保证在每个固定点上随机变量收敛。

依$L^p$收敛

对于正整数$p$，如果$(\Omega,\mathcal{F},P)$上的随机变量$X$和随机变量列$X_1,X_2,\cdots$满足$\lim\limits_{n \to \infty}\mathbb{E}[|X_n-X|^p]=0$，就称$X _n$依$L^p$收敛到$X$(converge in $L^p$)，记为$X_n \stackrel{L^p}{\to} X$。

这里的L是Lebesgue的缩写。事实上，测度论中有专门的对“$L^p$空间”的讨论。

下面证明，若$q>p$，则$X_n \stackrel{L^q}{\to} X$可以推出$X_n \stackrel{L^p}{\to} X$。$\mathbb{E}[|X_n-X|^p]=$ $\mathbb{E}[(|X_n-X|^q)^{\frac{p}{q}}]$。因为$y=x^{\frac{p}{q}}$是上凸函数，所以$\mathbb{E}[(|X_n-X|^q)^{\frac{p}{q}}]\leq \mathbb{E}[(|X_n-X|^q)]^{\frac{p}{q}}$。所以$\lim\limits_{n\to\infty}\mathbb{E}[|X_n-X|^p]\leq \lim\limits_{n\to\infty}\mathbb{E}[|X_n-X|^q]^{\frac{p}{q}}$。因为$X_n \stackrel{L^q}{\to} X$，所以$\lim\limits_{n\to\infty}\mathbb{E}[|X_n-X|^q]^{\frac{p}{q}}=0$。于是$\lim\limits_{n\to\infty}\mathbb{E}[|X_n-X|^p]=0$。证毕。

若$q>p$，则$X_n \stackrel{L^p}{\to} X$不能推出$X_n \stackrel{L^q}{\to} X$。反例：$([0,1],\mathcal{B}([0,1]),P)$，其中$P$是勒贝格测度。令$X_n=n^{1/q} \cdot \mathbb{1}_{[\frac{1}{n},\frac{2}{n}]}$，$X$是全零函数。于是，$\mathbb{E}[|X_n-X|^p]=\mathbb{E}[X_n^p]=$ $n^{p/q}\cdot (1/n)=n^{p/q-1}$。所以$\lim\limits_{n\to\infty}\mathbb{E}[|X_n-X|^p]=\lim\limits_{n\to\infty}n^{p/q-1}=0$。但是$\mathbb{E}[|X_n-X|^q]=\mathbb{E}[X_n^q]=(n^{1/q})^q\cdot 1/n=1$，可见$X_n \stackrel{L^q}{\to} X$不成立。

下面证明，$X_n \stackrel{L^1}{\to} X$可以推出$X_n \stackrel{p}{\to} X$。根据$\lim\limits_{n \to \infty}\mathbb{E}[|X_n-X|]=0$，所以$\forall \varepsilon>0$，$\exists N>0,\forall n>N,\mathbb{E}[|X_n-X|]<\varepsilon$。由Markov不等式，$P(|X_n-X|>\varepsilon)\leq\dfrac{\mathbb{E}[|X_n-X|]}{\varepsilon}$。因此对于任意固定的$\varepsilon$，$\lim\limits_{n\to\infty}P(|X_n-X|>\varepsilon)\leq\lim\limits_{n\to\infty}\dfrac{\mathbb{E}[|X_n-X|]}{\varepsilon}=\dfrac{\lim\limits_{n\to\infty}\mathbb{E}[|X_n-X|]}{\varepsilon}=0$。综上我们得到了$\forall \varepsilon>0$，$\lim\limits_{n\to\infty}P(|X_n-X|>\varepsilon)=0$。证毕。

$X_n \stackrel{p}{\to} X$不能推出$X_n \stackrel{L^1}{\to} X$。反例：$([0,1],\mathcal{B}([0,1]),P)$，其中$P$是勒贝格测度。令$X_n=n \cdot \mathbb{1}_{[\frac{1}{n},\frac{2}{n}]}$，$X$是全零函数。$\forall \varepsilon>0$，对于$\forall n\in \N$，$P(|X_n-X|>\varepsilon)=1/n$，因此$\lim\limits_{n\to\infty}P(|X_n-X|>\varepsilon)=0$，可见$X_n \stackrel{p}{\to} X$。但是$\mathbb{E}[|X_n-X|]=\mathbb{E}[X_n]=1$，因此$\lim\limits_{n \to \infty}\mathbb{E}[|X_n-X|^p]\neq 0$，可见$X_n \stackrel{L^1}{\to} X$不成立。

一般而言，$X_n \stackrel{a.s.}{\to} X$与$X_n \stackrel{L^1}{\to} X$的关系是不可比较的。左推右的反例：$X_n=n \cdot \mathbb{1}_{[\frac{1}{n},\frac{2}{n}]}$，$X\equiv 0$，其中$\mathbb{E}[|X_n-X|]=\mathbb{E}[X_n]=1$。右推左的反例：$X_n = \begin{cases} 1, & \omega \in [(k-1)\cdot 2^{-m}, k\cdot 2^{-m}) \\ 0, & \text{otherwise}. \end{cases}$，其中$\E[|X_n-X|]=\E[X_n]=2^{-m}\to 0$，但是$X_n$在任何一点处都不收敛。

下面我们证明，如果$X_n \stackrel{a.s.}{\to} X$，且存在一个随机变量$Y$满足$\mathbb{E}[Y]<\infty$，且可以找到一个测度为1的集合使得在这个集合上$\forall n,|X_n|\leq Y$处处成立（也即满足“控制收敛定理”的条件，那么可以推出$X_n \stackrel{L^1}{\to} X$。根据控制收敛定理，$\lim\limits_{n\to\infty}\mathbb{E}[X_n]=\mathbb{E}[\lim\limits_{n\to\infty}X_n]=\mathbb{E}[X]$。而$X_n-X$又可以被随机变量$2Y$控制，所以再次由控制收敛定理$\lim\limits_{n\to\infty}\mathbb{E}[X_n-X]=\mathbb{E}[\lim\limits_{n\to\infty}X_n-X]=\mathbb{E}[\lim\limits_{n\to\infty}X_n]-\mathbb{E}[X]=0$，因此$\lim\limits_{n\to\infty}\mathbb{E}[|X_n-X|]=0$，所以$X_n \stackrel{L^1}{\to} X$成立。

依分布收敛

设$X$的累积分布函数为$F(x)$，$X_n$的累积分布函数为$F_n(x)$。如果在$F$的任意一个连续点$a$上都有$\lim\limits_{n \to \infty}F_n(a)= F( a )$，就称依分布收敛(converge in distribution)到$X$，记为$X_n \stackrel{d}{\to} x$。

和前几类收敛形式不同，依分布收敛并不要求$X$与各个$X_n$是基于同一个概率空间$(\Omega,\mathcal{F},P)$的，而是抛开概率空间，仅考虑其分布函数的性质。

下面证明，$X_n \stackrel{p}{\to} X$可以推出$X_n \stackrel{d}{\to} X$。固定$a$是$X$的分布函数的一个连续点。对于同一概率空间上的任意两个随机变量$A,B$，如果已知事件$A\leq a$发生，那么取定一个$\varepsilon>0$，此时要么$|A-B|>\varepsilon$，要么$B\leq a+\varepsilon$。所以总是成立$P(A\leq a)\leq P(|A-B|>\varepsilon)+P(B\leq a+\varepsilon)$。那么，对于$X_n \stackrel{p}{\to} X$所在的概率空间$(\Omega,\mathcal{F},P)$，我们有$P(X_n\leq a)\leq$ $P(|X_n-X|>\varepsilon)+$ $P(X\leq a+\varepsilon)$。又有$P(X\leq a-\varepsilon)\leq P(|X-X_n|>\varepsilon)+$ $P(X_n\leq a)$。所以$P(X\leq a-\varepsilon)-P(|X-X_n|>\varepsilon)\leq P(X_n\leq a)\leq P(|X-X_n|>\varepsilon)+P(X\leq a+\varepsilon)$。因为$X_n \stackrel{p}{\to} X$，所以$\lim\limits_{n\to\infty}P(|X-X_n|>\varepsilon)=0$。所以在上式中两边同时令$n\to\infty$，可得$\lim\limits_{n\to\infty}P(X\leq a-\varepsilon)\leq\lim\limits_{n\to\infty}P(X_n\leq a)\leq\lim\limits_{n\to\infty}P(X\leq a+\varepsilon)$。再同时令$\varepsilon\to 0$，可得$\lim\limits_{n\to\infty}P(X\leq a)\leq\lim\limits_{n\to\infty}P(X_n\leq a)\leq\lim\limits_{n\to\infty}P(X\leq a)$。由夹逼准则可得$\lim\limits_{n\to\infty}P(X_n\leq a)=P(X\leq a)$。所以$X_n \stackrel{d}{\to} X$，证毕。

显然，$X_n \stackrel{d }{\to} X$不能推出$X_n \stackrel{p}{\to} X$。只需取$(\{0,1\},\sigma(\{0,1\}),(1/2,1/2))$，令$X_n(0)=0,X_n(1)=1,X(0)=1,X(1)=0$，那么$X_n \stackrel{d }{\to} X$，但是$P(|X_n-X|>\varepsilon)=1$，可见$X_n \stackrel{p}{\to} X$不成立。

各种收敛形式的强弱关系

把我们上面得到的各种收敛形式的强弱关系画出来，得到：

\xymatrix{ L^q \ar[r] & L^p \ar[r] & L^1 \ar[r] & p \ar[r] & d \\ & & a.s.\text{ pointwise}\ar[u]^{\text{(DCT)}} \ar[ur] & & \\ & & \text{pointwise} \ar[u] \ar[lluu]& & }

Borel-Cantelli Lemma

在测度空间$(\Omega,\mathcal{F},P)$上，对于一列事件$E_1,E_2,\cdots$，如果$\sum\limits_{n=1}^{\infty}P(E_n)<\infty$，那么有P(\overline{\lim}\limits_{n\to\infty}E_n)=0。这个定理称为Borel-Cantelli第一引理。

关于集合列的上下极限的定义，见测度一文。

证明：P(\overline{\lim}\limits_{n\to\infty}E_n)=P(\bigcap\limits_{n=1}^{\infty}\bigcup\limits_{k=n}^{\infty}E_k)=P(\lim\limits_{n\to\infty}\bigcup\limits_{k=n}^{\infty}E_k)，由测度的连续性，这就等于$\lim\limits_{n\to\infty}P(\bigcup\limits_{k=n}^{\infty}E_k)\leq\lim\limits_{n\to\infty}\sum\limits_{k=n}^{\infty}P(E_k)$。$\forall N\in \N$，$\sum\limits_{n=1}^{\infty}P(E_n)=\sum\limits_{n=1}^{N}P(E_n)+$ $\sum\limits_{n=N+1}^{\infty}P(E_n)$，两边同时令$N\to\infty$，可得$\sum\limits_{n=1}^{\infty}P(E_n)=\sum\limits_{n=1}^{\infty}P(E_n)+$ $\lim\limits_{n\to\infty}\sum\limits_{k=n}^{\infty}P(E_n)$，由$\sum\limits_{n=1}^{\infty}P(E_n)<\infty$可得$\lim\limits_{n\to\infty}\sum\limits_{k=n}^{\infty}P(E_k)=0$。因此P(\overline{\lim}\limits_{n\to\infty}E_n)=0。

\overline{\lim}\limits_{n\to\infty}E_n中的元素是那些在$\{E_n\}$中出现无数次的元素。Borel-Cantelli第一引理告诉我们，只要$\sum\limits_{n=1}^{\infty}P(E_n)<\infty$，那么“几乎”所有元素都只在$\{E_n\}$出现有限次。

Borel-Cantelli第一引理的逆命题并不成立。如果P(\overline{\lim}\limits_{n\to\infty}E_n)=0，并不能推出$\sum\limits_{n=1}^{\infty}P(E_n)<\infty$。反例：令$E_n=[0,1/n]$，那么\overline{\lim}\limits_{n\to\infty}E_n=\{0\}，可见P(\overline{\lim}\limits_{n\to\infty}E_n)=0。但是$\sum\limits_{n=1}^{\infty}P(E_n)=\sum\limits_{n=1}^{\infty}\dfrac{1}{n}=\infty$。

如果事件序列$\{E_n\}$是mutually independent(相互独立)的，那么Borel-Cantelli第一引理的逆命题成立，这称为Borel-Cantelli第二引理：在测度空间$(\Omega,\mathcal{F},P)$上，对于一列mutually independent的事件$E_1,E_2,\cdots$，如果P(\overline{\lim}\limits_{n\to\infty}E_n)=0，那么$\sum\limits_{n=1}^{\infty}P(E_n)<\infty$。

我们证明其逆否命题：如果$\sum\limits_{n=1}^{\infty}P(E_n)=\infty$，那么有P(\overline{\lim}\limits_{n\to\infty}E_n)>0。事实上，我们可以得到更强的结论P(\overline{\lim}\limits_{n\to\infty}E_n)=1。根据De-Morgen律，\overline{\lim}\limits_{n\to\infty}E_n=\bigcap\limits_{n=1}^{\infty}\bigcup\limits_{k=n}^{\infty}E_k=\bigcap\limits_{n=1}^{\infty}\left(\bigcap\limits_{k=n}^{\infty}E_k^C\right)^C=\left(\bigcup\limits_{n=1}^{\infty}\bigcap\limits_{k=n}^{\infty}E_k^C\right)^C=\left(\varliminf\limits_{n\to\infty}E_n^C\right)^C。所以P(\overline{\lim}\limits_{n\to\infty}E_n)=1-P(\varliminf\limits_{n\to\infty}E_n^C)=1-P(\lim\limits_{n\to\infty}\bigcap\limits_{k=n}^{\infty}E_k^C)=1-\lim\limits_{n\to\infty}P(\bigcap\limits_{k=n}^{\infty}E_k^C)，由独立性可得$P(\bigcap\limits_{k=n}^{\infty}E_k^C)=\prod\limits_{k=n}^{\infty}P(E_k^C)=\prod\limits_{k=n}^{\infty}(1-P(E_k))$。于是P(\overline{\lim}\limits_{n\to\infty}E_n)=1-\lim\limits_{n\to\infty}\prod\limits_{k=n}^{\infty}(1-P(E_k))，根据不等式$1-x\leq e^{-x}$，我们有P(\overline{\lim}\limits_{n\to\infty}E_n)\geq 1-\lim\limits_{n\to\infty}\prod\limits_{k=n}^{\infty}(e^{-P(E_k)})=1-\lim\limits_{n\to\infty}e^{-\sum\limits_{k=n}^{\infty}P(E_k)}=1-e^{-\lim\limits_{n\to\infty}\sum\limits_{k=n}^{\infty}P(E_k)}。因为$\sum\limits_{n=1}^{\infty}P(E_n)=\infty$，所以$\lim\limits_{n\to\infty}\sum\limits_{k=n}^{\infty}P(E_k)=\infty$，因此$1-e^{-\lim\limits_{n\to\infty}\sum\limits_{k=n}^{\infty}P(E_k)}=1$。综上，P(\overline{\lim}\limits_{n\to\infty}E_n)=1，证毕。

由Borel-Cantelli第一引理和第二引理，我们得知：如果$\{E_n\}$是mutually independent的，那么\sum\limits_{n=1}^{\infty}P(E_n)<\infty\implies P(\overline{\lim}\limits_{n\to\infty}E_n)=0，\sum\limits_{n=1}^{\infty}P(E_n)=\infty\implies P(\overline{\lim}\limits_{n\to\infty}E_n)=1。可见任何时候，P(\overline{\lim}\limits_{n\to\infty}E_n)都只有$0$和$1$两种取值：

\sum\limits_{n=1}^{\infty}P(E_n)<\infty\iff P(\overline{\lim}\limits_{n\to\infty}E_n)=0\\ \sum\limits_{n=1}^{\infty}P(E_n)=\infty\iff P(\overline{\lim}\limits_{n\to\infty}E_n)=1

这种0-1特性在概率论中经常出现，我们将会看到这是Kolmogorov 0-1 Law的一个特例。

根据Borel-Cantelli引理，我们可以证明：如果一列随机变量$X_n$依概率收敛到$X$，那么存在$X_n$的一个子列$X_{m_k}$，使得$X_{m_k}$ a.s.点态收敛到$X$。$\forall k\in \N$，由$X_n\stackrel{p}{\to}X$，我们可以选取一个足够大的$m_k$使得$P(|X_{m_k}-X|>\dfrac{1}{k})<\dfrac{1}{2^k}$。我们要求随着$k$增大，每次选取的$m_k$依次增大，这样我们就得到了一个子列$X_{m_k}$。令$E_k=\{\omega\in \Omega\mid |X_{m_k}(\omega)-X(\omega)|>\dfrac{1}{k}\}$，这样就有$\sum\limits_{k\geq 1}P(E_k)<\sum\limits_{k \geq 1}\dfrac{1}{2^k}<\infty$，于是由Borel-Cantelli引理可知$P(\varlimsup\limits_{E\to\infty} A_k)=0$。也即，满足“存在无穷个$k\in \N$使得$|X_{m_k}(\omega)-X(\omega)|>\dfrac{1}{k}$”的样本点的测度为0。所以“只有有限个$k\in \N$使得$|X_{m_k}(\omega)-X(\omega)|>\dfrac{1}{k}$”的样本点的测度为$1$。其中，“只有有限个$k\in \N$使得$|X_{m_k}(\omega)-X(\omega)|>\dfrac{1}{k}$”等价于“存在$K>0$，使得$\forall k>K$，$|X_{m_k}(\omega)-X(\omega)|\leq$ $\dfrac{1}{k}$”，这能推出“$\forall \varepsilon>0,\exists N,\forall n>N,|X_{m_n}(\omega)-X(\omega)|<\varepsilon$”，也即$\lim\limits_{n\to\infty}X_{m_n}(\omega)=X(\omega)$。可见，使得$X_{m_k}$收敛的样本点的测度为$1$，也即$X_{m_k}$ a.s.点态收敛。

有了这个结论，我们就可以把控制收敛定理中的条件“a.s.点态收敛”放弱到“依概率收敛”：如果$X_n\stackrel{p}{\to}X$，且存在一个随机变量$Y$使得$\mathbb{E}[Y]<\infty$，并且对任意$n$以及几乎所有$\omega\in \Omega$满足$|X_n(\omega)|\leq Y(\omega)$，那么$\lim\limits_{n\to\infty}\mathbb{E}[X_n]=\mathbb{E}[X]$。证明：反证法，假设$\lim\limits_{n\to\infty}\mathbb{E}[X_n]=\mathbb{E}[X]$不成立。由于$X_n$被$Y$控制，所以$\mathbb{E}[X_n]$是有界数列。根据有界数列必有收敛子列，存在$L\in \R$使得$\lim\limits_{n\to\infty}\mathbb{E}[X_{m_k}]=L$。显然，$X_{m_k}\stackrel{p}{\to}X$，那么由Borel-Cantelli引理，我们可以找到子列$X_{m_k}$的一个子列$X_{p_k}$，使得$X_{p_k}\stackrel{a.s.}{\to}X$。显然，$\lim\limits_{k\to\infty}\mathbb{E}[X_{p_k}]=L$。然而，根据“a.s.点态收敛”条件下的控制收敛定理，我们会得到$\lim\limits_{k\to\infty}\mathbb{E}[X_{p_k}]=\mathbb{E}[X]$的结论，这就推出了矛盾。证毕。

弱大数定律

有了上面这套关于随机变量列的收敛形式的理论，我们就可以形式化地描述大数定律了。我们将会证明两种大数定律，一种用的是“a.s.点态收敛”，一种用的是“依概率收敛”。因为我们证明了“a.s.点态收敛”是比“依概率收敛”更强的条件，所以我们把前者称为“强大数定律(Strong Law of Large Numbers, SLLN)”，后者称为“弱大数定律(Weak Law of Large Numbers, WLLN)”。

设$\{X_n\}$是概率空间$(\Omega,\mathcal{F},P)$上一列独立且同分布(independent and identically distributed, i.i.d.)的随机变量，定义$S_n:=\sum\limits_{i =1}^{n}X_i$，那么$\{\dfrac{S_n}{n}\}$也是一列$(\Omega,\mathcal{F},P)$上的随机变量。下面这个结论称为Khinchin弱大数定律：如果$\mathbb{E}[X_1]<\infty$，则$\dfrac{S_n}{n}\stackrel{p}{\to}\mathbb{E}[X_1]$。

i.i.d中的“independent”是指“mutually independent”。

注意，因为$\{X_n\}$是独立同分布的，所以$\mathbb{E}[X_1]<\infty$这个条件指的其实是$\forall i\in \N,\mathbb{E}[X_i]<\infty$，因为所有$\mathbb{E}[X_i]$都是同一个值。同理，$\dfrac{S_n}{n}\stackrel{p}{\to}\mathbb{E}[X_1]$中的$\mathbb{E}[X_1]$也可以是任何一个$\mathbb{E}[X_i]$。注意，$\dfrac{S_n}{n}\stackrel{p}{\to}\mathbb{E}[X_1]$中的$\mathbb{E}[X_1]$是指一个常值随机变量而不是一个实数，严格的写法应该是：令$Y$满足$\forall \omega\in \Omega,Y(\omega)=\mathbb{E}[X_1]$，有$\dfrac{S_n}{n}\stackrel{p}{\to}Y$。

在证明Khinchin弱大数定律之前，我们应该指出这样一件事。如果我们在Khinchin弱大数定律的前提中附加上一个“二阶矩有界”条件，那么证明会变得很容易：存在$\sigma\in \R$，使得$\mathbb{E}[X_1^2]<\sigma^2$。有了这个条件以后，证明只需要用一次Chebyshev不等式：要证$\dfrac{S_n}{n}\stackrel{p}{\to}\mathbb{E}[X_1]$，即证$\forall \varepsilon>0$，$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)=0$。对于任意$n\in \N$，我们有$\mathbb{E}\left[\dfrac{S_n}{n}\right]=\dfrac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}[X_i]=\dfrac{1}{n}\cdot n\mathbb{E}[X_1]=\mathbb{E}[X_1]$，$\text{Var}\left[\dfrac{S_n}{n}\right]=\dfrac{1}{n^2}\sum\limits_{i=1}^{n}\text{Var}[X_i]=\dfrac{\text{Var}[X_1]}{n}=\dfrac{\mathbb{E}[X_1^2]-\mathbb{E}[X_1]^2}{n}\leq \dfrac{\sigma^2}{n}$。所以$P\left(\left|\dfrac{S_n}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)=P\left(\left|\dfrac{S_n}{n}-\mathbb{E}\left[\dfrac{S_n}{n}\right]\right|>\varepsilon\right)\leq \dfrac{\text{Var}\left[\dfrac{S_n}{n}\right]}{\varepsilon^2}\leq\dfrac{\sigma^2}{n\varepsilon^2}$。于是$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)\leq\lim\limits_{n\to\infty}\dfrac{\sigma^2}{n\varepsilon^2}=0$，证毕。

从上面的证明可以看到，我们只用到了$\{X_n\}$的独立性，而没有用到关于同分布的任何条件。同时，$\mathbb{E}[X_1^2]<\sigma^2$的条件也可以取代$\mathbb{E}[X_1]<\infty$的条件。所以我们实际得出了这样一个结论，这可以看作弱大数定理的另一种形式：设$\{X_n\}$是概率空间$(\Omega,\mathcal{F},P)$上一列mutually independent的随机变量，令$S_n=\sum\limits_{i=1}^{n}X_i$，如果存在$\sigma\in \R$使得$\mathbb{E}[X_1^2]<\sigma^2$，则$\dfrac{S_n}{n}\stackrel{p}{\to}\mathbb{E}[X_1]$。

现在我们来看如何证明Khinchin弱大数定律。上面的证明的关键在于利用$X_1$的二阶矩的上界，由Chebyshev不等式给出了$P\left(\left|\dfrac{S_n}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)$的上界。但是现在如果只知道$X_1$的一阶矩有界，我们就无法再直接用concentration不等式来令上界趋向于$0$。比如，我们可以假设$X_1$非负，尝试Markov不等式，则$P\left(\dfrac{S_n}{n}-\mathbb{E}[X_1]>\varepsilon\right)=P\left(\dfrac{S_n}{n}>\mathbb{E}[X_1]+\varepsilon\right)\leq\dfrac{\mathbb{E}[X_1]}{\mathbb{E}[X_1]+\varepsilon}$，无法成功。

为了证明Khinchin弱大数定律，我们可以采用一种称为“截断法(truncation)”的证明技巧。对于随机变量$X_i$，我们把它分解为两个随机变量之和，其中一个是$X_i$取值不超过上界$M$的部分，另一个是剩余部分。这样，前一部分的随机变量就有了用二阶矩有界的性质，而通过选取恰当的$M$（可以是一个关于$n$的值），我们可以使得第二部分随机变量被取到的概率趋向$0$，这样就完成了证明。具体地，令$X_i^{\leq M}(\omega):=X_i(\omega)\cdot \mathbb{1}[|X_i(\omega)|\leq M]$，$X_i^{>M}(\omega):=X_i(\omega)\cdot \mathbb{1}[|X_i(\omega)|>M]$，那么$X_i=X_i^{\leq M}+X_i^{>M}$。于是$S_n=\sum\limits_{i=1}^{n}(X_i^{\leq M}+X_i^{>M})$，记$S_n^{\leq M}:=\sum\limits_{i=1}^{n}X_i^{\leq M}$，$S_n^{>M}:=\sum\limits_{i=1}^{n}X_i^{>M}$，那么$S_n=S_n^{\leq M}+S_n^{>M}$。对于任意$\varepsilon>0$，$P\left(\left|\dfrac{S_n}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)=P\left(\left|\dfrac{S_n^{\leq M}}{n}-\mathbb{E}[X_1]+\dfrac{S_n^{> M}}{n}\right|>\varepsilon\right)$，其中，$P\left(\left|\dfrac{S_n^{\leq M}}{n}-\mathbb{E}[X_1]+\dfrac{S_n^{> M}}{n}\right|>\varepsilon\right)=P\left(\left|\dfrac{S_n^{\leq M}}{n}-\mathbb{E}[X_1]+\dfrac{S_n^{> M}}{n}\right|>\varepsilon\land S_n^{>M}=0\right)+$ $P\left(\left|\dfrac{S_n^{\leq M}}{n}-\mathbb{E}[X_1]+\dfrac{S_n^{> M}}{n}\right|>\varepsilon\land S_n^{>M}\neq 0\right)\leq P\left(\left|\dfrac{S_n^{\leq M}}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)+P(S_n^{>M}\neq 0)$。

现在我们只需选取一个合适的$M$，使得$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n^{\leq M}}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)=0$和$\lim\limits_{n\to\infty}P(S_n^{>M}\neq 0)=0$同时成立。显然$M$不能取常数，因为只要有一个$X_i$使得$P(X_i^{>M}\neq 0)>0$，根据$X_i$是独立同分布的，有$P(S_n^{>M}\neq 0)\geq P(X_1^{>M}\neq 0)$，于是$\lim\limits_{n\to\infty}P(S_n^{>M}\neq 0)\geq P(X_1^{>M}\neq 0)>0$。所以，无论$M$取什么常数，只要取满足$P(X_1^{>M}\neq 0)>0$的$X_1$，截断法就会失效。所以$M$必须取一个关于$n$的值。下面我们证明，为使得截断法有效，只需取$M=n$。

考虑$P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)$这一项。由于做了截断，$\mathbb{E}\left[\dfrac{S_n^{\leq n}}{n}\right]=\mathbb{E}[X_1^{\leq n}]\neq\mathbb{E}[X_1]$，因此不能直接用Chebyshev不等式。但是，如果令$n\to\infty$，那么随机变量列$X_1^{\leq n}$点态收敛到$X_1$。而显然$|X_1^{\leq n}|<|X_1|$，而$\mathbb{E}[X_1]<\infty$，因此由控制收敛定理可得$\lim\limits_{n\to\infty}\mathbb{E}[X_1^{\leq n}]=\mathbb{E}[X_1]$。现在，要证明$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)=0$。注意到，如果$\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1]\right|>\varepsilon$成立，那么$\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1^{\leq n}]\right|+|\mathbb{E}[X_1^{\leq n}]-\mathbb{E}[X_1]|>\varepsilon$成立，所以“$\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1^{\leq n}]\right|>\varepsilon/2$或$|\mathbb{E}[X_1^{\leq n}]-\mathbb{E}[X_1]|>\varepsilon/2$”成立。因此$P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)\leq P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1^{\leq n}]\right|>\varepsilon/2\right)+P(|\mathbb{E}[X_1^{\leq n}]-\mathbb{E}[X_1]|>\varepsilon/2)$。因此，只需证$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1^{\leq n}]\right|>\varepsilon/2\right)=0$以及$\lim\limits_{n\to\infty}P(|\mathbb{E}[X_1^{\leq n}]-\mathbb{E}[X_1]|>\varepsilon/2)=0$。其中，后者是显然的，因为对于任意固定的$n$，$|\mathbb{E}[X_1^{\leq n}]-\mathbb{E}[X_1]|$是一个常数，因此当$n$足够大时总是有$P(|\mathbb{E}[X_1^{\leq n}]-\mathbb{E}[X_1]|>\varepsilon/2)=0$。而证明$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1^{\leq n}]\right|>\varepsilon/2\right)=0$就可以用Chebyshev不等式了：$P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1^{\leq n}]\right|>\varepsilon/2\right)\leq\dfrac{\text{Var}[X_1^{\leq n}]}{n\varepsilon^2/4}$ $\leq\dfrac{\mathbb{E}[(X_1^{\leq n})^2]}{n\varepsilon^2}\leq \dfrac{1}{\varepsilon^2}\cdot \mathbb{E}\left[\dfrac{(X_1^{\leq n})^2}{n}\right]$。因此$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1^{\leq n}]\right|>\varepsilon/2\right)\leq$ $\dfrac{1}{\varepsilon^2}\cdot \lim\limits_{n\to\infty}\mathbb{E}\left[\dfrac{(X_1^{\leq n})^2}{n}\right]$。根据定义，$|X_1^{\leq n}|\leq n$，因此$\left|\dfrac{(X_1^{\leq n})^2}{n}\right|=\left|\dfrac{X_1^{\leq n}}{n}\right|\cdot \left|X_1^{\leq n}\right|\leq |X_1^{\leq n}|\leq |X_1|$。可见$\dfrac{(X_1^{\leq n})^2}{n}$能被$X_1$控制，所以由控制收敛定理，$\lim\limits_{n\to\infty}\mathbb{E}\left[\dfrac{(X_1^{\leq n})^2}{n}\right]=\mathbb{E}\left[\lim\limits_{n\to\infty}\dfrac{(X_1^{\leq n})^2}{n}\right]$。对于任意$\omega$，当$n$充分大时都有$\dfrac{(X_1^{\leq n}(\omega))^2}{n}=\dfrac{(X_1(\omega))^2}{n}$，因此$\lim\limits_{n\to\infty}\dfrac{(X_1^{\leq n}(\omega))^2}{n}=0$。由此可得$\mathbb{E}\left[\lim\limits_{n\to\infty}\dfrac{(X_1^{\leq n})^2}{n}\right]=0$。综上可知$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1^{\leq n}]\right|>\varepsilon/2\right)=0$，因此$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n^{\leq n}}{n}-\mathbb{E}[X_1]\right|>\varepsilon\right)=0$。

最后只需证明$\lim\limits_{n\to\infty}P(S_n^{>n}\neq 0)=0$。对于任意$n$，如果“$S_n^{>n}\neq 0$”成立，那么“$\bigvee\limits_{i=1}^{n}X_i^{>n}\neq 0$”成立，因此由Union Bound可知$P(S_n^{>n}\neq 0)\leq\sum\limits_{i=1}^{n}P(X_i^{>n}\neq 0)$ $=n\cdot P(X_1^{>n}\neq 0)$。其中，$P(X_1^{>n}\neq 0)=P(\{\omega\mid X_1(\omega)>n\})$ $=P(X_1>n)=\mathbb{E}[\mathbb{1}[X_1>n]]$。所以，只需证$\lim\limits_{n\to\infty}\mathbb{E}[n\cdot \mathbb{1}[X_1>n]]=0$。注意到，恰好成立$|n\cdot \mathbb{1}[X_1>n]|\leq |X_1|$，所以由控制收敛定理可得$\lim\limits_{n\to\infty}\mathbb{E}[n\cdot \mathbb{1}[X_1>n]]=\mathbb{E}[\lim\limits_{n\to\infty}(n\cdot \mathbb{1}[X_1>n])]=0$，证毕。

这样我们就证明了Khinchin弱大数定律。

圣彼得堡悖论

为了更好地理解截断法，让我们考虑这样一个问题：“抛一枚均匀硬币，直到出现第一次正面为止。如果第一次正面出现在第$n$次抛掷，玩家将获得$2^n$元。现在的问题是，假设要设定玩一次这个游戏的票价，票价应该设定为多少？”

关于这个问题，一个自然的想法是用“期望获得的钱”来估计票价。然而，期望获得的钱为$\sum\limits_{i=n}^{\infty}\dfrac{1}{2^n}\cdot 2^n=\infty$。这说明从理论上，玩家期望赢得无穷大的钱，因此票价设成任意有限值都是不合理的。但是在现实中，玩家肯定不愿意花大价钱买票，因为有$1/2$的概率玩家只被返还$2$块钱，有$1/4$的概率玩家只被返还$4$块钱。简单的计算可以告诉我们，假如票价设为$100$，那么玩家有$98\%$的概率亏钱。看来，理论和直观产生了严重的偏差，所以这个问题被称为“圣彼得堡悖论(St. Petersburg Paradox)”。

上面的思考暗示我们，在这个游戏中，不能思考“单轮”的票价。因为对于任何设定“较高”的票价$T$，想要“玩一次就把票价赚回来”的概率是极小的。除非运气特别好，想要“赚回票价”至少得玩好多轮。于是，我们假设总共玩$n$轮，那么总票价为$nT$。用随机变量$X_i$表示第$i$轮游戏玩家赢得钱，记$S_n=\sum\limits_{i=1}^{n}X_i$。如果票价是合理的，那么$S_n$应当与$nT$“接近”，也即$T$应该与$\dfrac{S_n}{n}$“接近”。可见，这是一个与大数定律形式很相近的问题。然而，现在$\mathbb{E}[X_i]=\infty$，所以不能用大数定律给出$\dfrac{S_n}{n}$的极限。事实上，我们应该已经注意到，票价不应该是一个常数，而应该是一个关于轮数$n$的函数$T(n)$。$T(n)$应当关于$n$递增，因为玩的轮数越多，玩家赢得大钱的概率越高。那么随着$n$的增长，$\dfrac{S_n}{n}$和$T(n)$都在变化，那么应该如何定义“$\dfrac{S_n}{n}$接近$T(n)$”呢？

一个自然的想法是类比依概率收敛，希望可以找到$T(n)$的表达式，使得$\forall \varepsilon>0$，$\lim\limits_{n\to\infty}P\left(\left|\dfrac{S_n}{n}-T(n)\right|>\varepsilon\right)=0$。但是事实证明这样做并不能成功。我们能够做到的是找到这样的实数函数$T(n),\varepsilon(n),q(n),\delta(n)$，使得

$$P\left(\left|\dfrac{S_n}{nT(n)}-q(n)\right|>\varepsilon(n)\right)\leq \delta(n)$$

其中当$n\to\infty$时，$q(n)\to 1,\varepsilon(n)\to 0,\delta(n)\to 0$。让我们来理解这一定义。当$n$比较小的时候，$\dfrac{S_n}{nT(n)}$具有较大的随机性；而当$n$很大时，$\dfrac{S_n}{nT(n)}$的分布几乎集中在“$1$”这一点处。如果能找到这样的$T(n)$，我们就可以认为$nT(n)$是对$n$轮票价的一个合理估计。

用截断法。方便起见，不妨设$M=2^m$，$m$是一个正整数。那么$\mathbb{E}\left[\dfrac{S_n^{\leq 2^m}}{n}\right]=\mathbb{E}[X_1^{\leq 2^m}]$。根据游戏的定义，$X_1^{\leq 2^m}$对应“被截断到$m$轮的游戏”，因此$\mathbb{E}[X_1^{\leq 2^m}]=\sum\limits_{i=1}^{m}\dfrac{1}{2^i}\cdot 2^i=m$。同时，$\text{Var}\left[\dfrac{S_n^{\leq 2^m}}{n}\right]=\dfrac{1}{n}\text{Var}[X_1^{\leq 2^m}]$ $\leq\dfrac{1}{n}\mathbb{E}[(X_1^{\leq 2^m})^2]=\dfrac{1}{n}\sum\limits_{i=1}^{m}\dfrac{1}{2^i}\cdot(2^i)^2=\dfrac{2^{m+1}-2}{n}\leq\dfrac{2^{m+1}}{n}$。由Chebyshev不等式，对任意$\varepsilon$，$P\left(\left|\dfrac{S_n^{\leq 2^m}}{n}-m\right|>\varepsilon\right)\leq\dfrac{2^{m+1}}{n\varepsilon^2}$。仿照Khinchin弱大数定律中的论证，我们凑出：$P\left(\left|\dfrac{S_n}{n}-m\right|>\varepsilon\right)\leq P\left(\left|\dfrac{S_n^{\leq 2^m}}{n}-m\right|>\varepsilon\right)+P(S_n^{>2^m}\neq 0)$。我们有$P(S_n^{>2^m}\neq 0)\leq n\cdot P(X_1^{>2^m}\neq 0)=\dfrac{n}{2^m}$。这样我们就得到了$P\left(\left|\dfrac{S_n^{\leq 2^m}}{n}-m\right|>\varepsilon\right)+P(S_n^{>2^m}\neq 0)\leq\dfrac{2^{m+1}}{n\varepsilon^2}+\dfrac{n}{2^m}$。

把$\varepsilon,m$都看作关于$n$的函数，我们需要$n\to\infty$时让$\dfrac{2^{m+1}}{n\varepsilon^2}+\dfrac{n}{2^m}\to 0$。首先，为了使$\dfrac{n}{2^m}\to 0$，$m$的增长速率必须快于$\log_2 n$。但是这样就需要$\varepsilon^2\to \infty$。事实上，我们不用担心这一点，因为这里的$\varepsilon$并不是我们最终所求的$\varepsilon(n)$，它只是截断法的一个中间结果。为了给再给$m$分配一部分增长速率，可以选择给它一个低于$\log_2 n$增长。令$m=\log_2 n+\dfrac{1}{2}\log_2\log_2 n$。这样，我们就需要用$\varepsilon^2$抵消速率为$\log_2n$的增长，因此令$\varepsilon=\sqrt{\log_2 n}$。于是我们得到这样一个结果：$P\left(\left|\dfrac{S_n}{n}-(\log_2 n+\dfrac{1}{2}\log_2\log_2 n)\right|>\sqrt{\log_2 n}\right)\leq \dfrac{2}{\sqrt{\log_2 n}}+\dfrac{1}{\sqrt{\log_2 n}}=\dfrac{3}{\sqrt{\log_2 n}}$。在概率的括号里两边同时除以$\log_2 n$，就得到：

$$P\left(\left|\dfrac{S_n}{n\log_2 n}-(1+\dfrac{\log_2\log_2 n}{2\log_2 n})\right|>\dfrac{1}{\sqrt{\log_2 n}}\right)\leq\dfrac{3}{\sqrt{\log_2 n}}$$

于是，令$T(n)=\log_2 n,q(n)=1+\dfrac{\log_2\log_2 n}{2\log_2 n}$，$\varepsilon(n)=\dfrac{1}{\sqrt{\log_2 n}}$，$\delta(n)=\dfrac{3}{\sqrt{\log_2 n}}$，就得到了我们想要的结果。由此可见，$n$轮票价的合理定价为每轮$\log_2 n$元。