离散概率在组合中的使用

容斥原理

对于两个有交集的事件$A,B$，如何求出$\Pr(A \cup B)$？直觉就是$\Pr(A \cup B)=\Pr(A)+\Pr(B)-\Pr(A \cap B)$。但我们必须用公理来推导它。根据公理，我们只会计算无交集的两个集合的并的概率，所以我们做这样的的拆分：$\Pr(A) = \Pr(A \setminus (A \cap B))+\Pr(A \cap B)$，$\Pr(B) = \Pr(B \setminus (A \cap B))+\Pr(A \cap B)$。而$\Pr(A \cup B)=\Pr(A \setminus (A \cap B))+\Pr(B \setminus (A \cap B))+\Pr(A \cap B)$。这样我们就解出来$\Pr(A \cup B)=\Pr(A)+\Pr(B)-\Pr(A \cap B)$。

用同样的方法，类比集合中我们采用的算贡献的想法，可以证明概率的容斥原理$\Pr[\bigcap\limits_{i\in [n]} \overline{A_i}]=\sum\limits_{J\subseteq [n]}(-1)^{|J|}\cdot \Pr(\bigcap\limits_{j\in J} A_j)$。（证明每个基本事件在等式两边的贡献相等）

Union Bound

从二元情形的容斥原理$\Pr(A \cup B)=\Pr(A)+\Pr(B)-\Pr(A \cap B)$中可以看出，如果我们丢掉$-\Pr(A \cap B)$这一项，因为概率函数一定是非负的，我们就会直接得到$\Pr(A \cup B)\leq\Pr(A)+\Pr(B)$，推广到$n$元就是$\Pr\left(\bigcup\limits_{i \in I}A_i\right)\leq \sum\limits_{i \in I}\Pr(A_i)$，这个结论称为“Union Bound”。

这个结论虽然推导很简单，但却在应用中有着巨大的价值。

为了看到Union Bound的巨大价值，我们来看一个复杂的例子。

我们发现一个事实，6个人之间要么至少有三个人互相之间都认识，要么至少有三个人之间互相都不认识。用一般的数学语言来描述，在6个节点的完全图（$K_6$）上，每条边要么染成红色要么染成蓝色（代表认识与不认识），那么对于任何一种染色方案，“所有边都是红色的$K_3$子图”和“所有边都是蓝色的$K_3$子图”都至少存在一个。

我们可以证明（枚举），在5个点的完全图上这一点是做不到的。也即要做到这一点至少需要6个节点，在5个点的图上至少存在一种染色方案使得红色和蓝色的$K_3$子图都不存在。

由此我们定义Ramsey数$R(r,s)$，他表示使得完全图$K_N$的边任意红蓝染色始终存在“红色的$K_r$子图”或“蓝色的$K_s$子图”中的至少一个的最小的$N$。这是Well-Defined的，因为我们已经看到太小的$N$是不行的，而显然$N$足够大时一定是可行的，所以它被限制在一个闭区间里，所以最小值一定存在。上面这个例子可以描述为$R(3,3)=6$。

我们可以证明$\dbinom{r+s-2}{r-1}$是$R(r,s)$的一个上界，这并不需要用到概率的知识：我们首先证明$R(r,s) \le R(r-1,s)+R(r,s-1)$。令$M=R(r-1,s)+R(r,s-1)$，只需证明$K_M$中一定存在红色$K_r$或蓝色$K_s$。对于任意某个特定的染色，考虑与某个点（比如点1）相邻的$M-1$条边的染色情况，由于$M=R(r-1,s)+R(r,s-1)$，因此根据鸽巢原理，这$M-1$条边中“至少有$R(r-1,s)$条红边”与“至少有$R(r,s-1)$”条蓝边中总有一个成立，不然总边数就小于等于$M-2$，矛盾。如果是前者满足，那么把这些边连出去的点收集在一起就有$R(r-1,s)$个点了，根据定义，这些点构成的完全子图里一定要么存在一个红色$K_{r-1}$或者蓝色$K_s$。如果存在蓝色$K_s$则证毕，否则对于得到的$K_{r-1}$附加上原先固定的点1就一定能得到一个红色$K_r$，因此无论如何都成立。“至少有$R(r,s-1)$”的情况也是完全相同的。所以我们证明了这个递推不等式。对$r+s$归纳，那么$R(r,s) \leq R(r-1,s)+R(r,s-1) \leq \dbinom{r+s-3}{r-2}+\dbinom{r+s-3}{r-1}=\dbinom{r+s-2}{r-1}$，得证。

下面我们证明下界。这里我们只能给出$r=s$时的下界$R(s,s) > 2^{s/2}$。只需证明对于$M=2^{s/2}$，存在一种染色方案使得$K_M$中不存在任何同色的$K_s$子图。这里我们要用到概率方法——转而证明如果给$K_M$随机着色，出现“不存在同色$K_s$子图”这一事件的概率大于0，这等价于“存在同色$K_s$子图”这一事件的概率小于1。在这里，概率空间中样本集就是所有可能的染色方案（每条边可以选择染红或染蓝，共有$2^{|E|}$种）。“存在同色$K_s$子图”这一事件对应着样本集中的一个子集，即那些符合我们条件的染色方案。这是不容易计算的。然而，如果我们枚举所有的大小为$s$的子图，那么每一个子图的“同色”也是一个事件。并且我们发现对于我们枚举的所有的子图，这些事件的并集恰好就是“存在同色$K_s$子图”这一事件（如果一个子图同色，那么它在“存在同色$K_s$”里有贡献；如果它在“存在同色$K_s$”里有贡献，那么一定在适当的时候被枚举到）。这些事件之间可能有交集，因此精确计算他们的并集的概率必须要容斥，但我们可以用Union Bound给出上界，而对于每个事件的概率是容易计算的——只需保证枚举到的点集里的所有边同色，边的个数为$\dbinom{s}{2}$，因此每个事件的概率就是$\left[\dfrac{1}{2}\right]^{\binom{s}{2}} \times 2$（乘以2是因为有两种可能的“同色”）。因此总的概率就可以被放缩为$\dbinom{M}{s}\times 2^{1-\binom{s}{2}}$，代入$M=2^{s/2}$，$\dfrac{2^{s/2}!}{s!(2^{s/2}-s)!} \times 2 \times \dfrac{1}{2^{\frac{s(s-1)}{2}}}$，它是小于1的！这样证明就结束了。

当我们要证明“可能出现不存在的情况”时，只需证明“存在的概率小于1”。为此，我们可以枚举所有可能情况，这些可能情况的并集恰好构成“存在”这一事件。我们不直接计算这个并集的概率，而是计算每个可能情况的概率之和，这个和通过Union Bound给出了“存在的概率”一个上界，如果这个上界都已经小于1，那么我们想证明的概率就一定小于1。这就是证明“存在”的一种概率方法。

独立事件

对于概率空间$(\Omega,\mathcal{F},\Pr)$中的两个事件$A,B \in\mathcal{F}$，定义两个事件是独立的当且仅当$\Pr(A \cap B)=\Pr(A) \cdot \Pr(B)$。对于多个事件$A_1,\cdots,A_n$，定义它们“互相独立”当且仅当对于任何$I\subseteq [n]$，$\Pr(\bigcap\limits_{i \in I}A_i) = \prod\limits_{i \in I}\Pr(A_i)$。

特别需要注意的是，“互相独立”的定义与“两两独立”有所不同。它们并不是一回事。“互相独立”的要求更高。我们将会在随机变量一节中给出两两独立但并不“互相独立”的反例。

“独立”这个概念根据字面意思来理解，就是两个事件之间“没有关联”。比如就“在1，2，3，4中选数”这个样本空间中，“选到1或2”这个事件对应着$A=\{1,2\}$，“选到1或3”这个事件对应着$B=\{1,3\}$，那么发现$\Pr(A \cap B)=\Pr(A)\Pr(B)$，所以这两个事件根据我们的定义就是独立的！

我们来看一个多项式恒等判定的例子。如果两个多项式$P(x),Q(x)$是黑箱，那么如何判定它们是否恒等？假设它们的次数都不超过$d$次，那么假如我们选取$d$个不同的实数$x_i$，对于每个都满足$P(x_i)=Q(x_i)$，那么对于多项式$T(x)=P(x)-Q(x)$，$x_1,\cdots,x_d$就是$T(x)$的$d$个根。如果我们再选一个$x_{d+1}$，依然满足$T(x_{d+1})=0$，那说明$T$有$d+1$个根——这只可能是$T(x) \equiv 0$，因为代数基本定理告诉我们一个$d$次多项式最多只能有$d$个不同的实数根。

由此我们可以采用概率方法来判定两个多项式是否恒等。我们选取一个样本集$A$，里面是一些不同的实数（整数或许更加方便）。均匀随机（Uniformly At Random, u.a.r.）从$A$中选取一个数字$a$，如果$P(a)=Q(a)$就返回二者恒等，否则返回二者不等。这个算法怎么样呢？如果$P,Q$确实恒等，那么我们的算法始终返回的是正确结果；如果$P,Q$不等， 我们的算法返回“恒等”的概率是多少？由于$P,Q$不等， 能满足$P(x_i)=Q(x_i)$的$x_i$在实数范围内就一定不超过$d$个，因此我们抽取的$a$恰好满足的概率不超过$\dfrac{d}{|A|}$。因此如果选择大小为$100d$的样本集，算法的出错概率就达到了$\leq \dfrac{1}{100}$。

由于$|A|$的增大是有代价的，使得$|A|$越大并不一定越是好事。如何进一步提高算法的正确性呢？如果我们多次选择$a$，比如选$t$次，只有当每一次都满足$P(a_i)=Q(a_i)$才返回“恒等”，否则只要有一个不相等就返回“不恒等”，这样的算法在多项式明明不恒等却返回恒等的概率是多少？此时我们的样本空间变成了$A^t$，其中的基本事件为“一种取$t$次的方法”。我们考虑“第$i$次选到的数$x$满足$P(x)=Q(x)$”这一事件发生的概率，记为$\Pr[P(a_i)=Q(a_i)]$。我们可以验证$P(a_i)=Q(a_i)$与$P(a_j)=Q(a_j)$是独立的，因为$\Pr[P(a_i)=Q(a_i) \cap P(a_j)=Q(a_j)]=\dfrac{|D|^2}{|A|^2}$，其中$D$是$A$中$P(x)-Q(x)$的根的集合；而$\Pr[P(a_i)=Q(a_i)]=\Pr[P(a_j)=Q(a_j)]=\dfrac{|D|}{|A|}$，这样我们就验证了独立性，并且可以用类似的方法验证第$1$次到第$n$次每一次满足$P(a_i)=Q(a_i)$所有这些事件是“两两独立的”，因此直接得到$\Pr[\bigcap\limits_{i \in [t]}P(a_i)=Q(a_i)]=\prod\limits_{i=1}^{t}\Pr[P(a_i)=Q(a_i)]=\dfrac{|D|^t}{|A|^t}$，当$|A|$取$100d$时，可放缩为$\dfrac{1}{100^t}$。

条件概率

对于概率空间$(\Omega,\mathcal{F},\Pr)$中的两个事件$A,B \in\mathcal{F}$，定义$A$事件在$B$事件发生下的条件概率为$\Pr(A|B)=\dfrac{\Pr(A \cap B)}{\Pr(B)}$，记为$A \perp B$。这是符合我们的直观的，当我们讨论“$B$发生的条件下”时，我们把讨论区域限制在了$B$内，因此$B$就“好像是整个空间”了——所以我们除掉$B$发生的概率。

两个互相独立的事件其中一个在另一个的条件下发生的概率应该就是它本身发生的概率，代入验证这确实成立：由于$\Pr(A \cap B)=\Pr(A) \cdot \Pr(B)$恰好得到$\Pr(A|B)=\dfrac{\Pr(A \cap B)}{\Pr(B)}=\dfrac{\Pr(A)\Pr(B)}{\Pr(B)}=\Pr(A)$。这也是我们理解独立的一种方法，两事件独立等价于其中一个在另一个发生下的条件概率就是它自己，这表明$A,B$是“没有关系”的。

我们可以把条件概率的等式变形为$\Pr(A\cap B) = \Pr(A|B) \cdot \Pr(B)$。于是我们能够得到一个求解事件的交集的概率的链式法则：$\Pr(A_1 \cap \cdots \cap A_n)$ $=\Pr(A_n|A_1 \cap \cdots \cap A_{n-1}) \cdot \Pr(A_1 \cap \cdots \cap A_{n-1})$ $=\cdots$ $=\Pr(A_1)\cdot \Pr(A_2 | A_1)\cdot \Pr(A_3|A_1 \cap A_2) \cdots \cap \Pr(A_{n-1}|A_1 \cap \cdots \cap A_{n-2})\cdot\Pr(A_n|A_1 \cap \cdots \cap A_{n-1})$。它在直观上似乎更好理解，因为所有事件同时发生的概率可以写作“第一个事件发生的概率乘上在第一个事件发生的条件下第二个事件发生的概率乘上第一个事件和第二个事件都发生的条件下第三个事件发生的概率……”

Birthday Paradox

23个人里有两个人生日在同一天的概率达到50%，60个人里有两个人生日在同一天的概率达到99%。如何计算这个“生日悖论”的概率？

抽象为数学问题，我们可以这样描述：把$m$个小球随机放进$n$个箱子里，存在一个箱子里有至少两个小球的概率是多大？我们的概率空间是所有从$[m]$到$[n]$的映射$f$，要计算的是“映射不为单射”这一事件的概率。为此，我们再考虑一系列事件$A_i$，其中$A_i$表示“$f(i) \neq f(j)$对$j\in [i-1]$恒成立”这一事件，它对应了一系列映射，直观上表示的是如果我们把丢球的过程拆分成一个个按顺序丢球的过程，这个事件代表第$i$个球在丢的时候箱子里还是空的。于是“映射不为单射”这一事件等价于所有$A_i$都发生，因此我们要算的就是$\Pr[A_1 \cap A_2 \cap \cdots \cap A_m]$。利用链式法则，我们可以把它转化为条件概率：$\Pr[A_i|A_1 \cap \cdots \cap A_{i-1}]$是容易计算的，由于前$i-1$个球都对应了不同的箱子，留下的空箱子只有$n-(i-1)$个，因此它的值就是$\dfrac{n-i+1}{n}$。于是求得$\Pr[A_1 \cap A_2 \cap \cdots \cap A_m]=\prod\limits_{i=1}^{m}\dfrac{n-i+1}{n}$，它可以写作$\left( 1-\dfrac{1}{n}\right)\cdots \left( 1-\dfrac{m-1}{n}\right)$，根据$1+x\leq e^x$恒成立，$1-\dfrac{k}{n} < e^{-\frac{k}{n}}$，因此原式放缩为$e^{-\frac{1}{n}[1+2+\cdots+(m-1)]}=e^{-\frac{m(m-1)}{2n}}$。

取$n=365$，则当$m=23$时值恰好在0.5左右。当$m=60$时它小于0.01，因此生日重复的概率高达99%。

全概率公式

对于$A,B \in \mathcal{F}$，恒成立$\Pr(A)=\Pr(A \cap B)+\Pr(A \cap \overline{B})$。它可以推广，因为关键在于$B,\overline{B}$构成了全集$\Omega$的一个划分。如果全集能被划分为$n$个部分$B_1, \cdots ,B_n$，那么

$\forall A, \Pr(A)=\sum\limits_{i=1}^{n}\Pr(A \cap B_i)$。

给定三个$n \times n$ 的矩阵$A,B,C$，验证是否成立$AB=C$。

如果采用随机算法，我们可以随机一个长度为$n$的01向量$x$，验证是否成立$ABx=Cx$，如果成立返回等于，否则返回不等于。这和验证多项式是否恒等的例子很相似，我们来分析这个算法出错的概率——同样的，只有可能在$AB \neq C$而$ABx=Cx$时算法出错。由于移项可得$AB-C \neq 0,(AB-C)x=0$，我们的问题等价于验证对于给定的一个矩阵$D$且$D \neq 0$，要求u.a.r随机一个01向量$x$时$Dx=0$的概率。

注意，$D$是固定的。我们的随机在于向量$x$的随机，因此我们的样本空间就是$\{0,1\}^n$，我们想求出$\Pr[Dx=0]$。我们做一点放缩，如果只要求满足$\sum\limits_{i=1}^{n}D_{1i}x_i=0$，即只令$Dx$的第一维坐标取0，那么满足要求的$x$相比于$Dx=0$更多了，换言之事件$Dx=0$被包含于事件$\sum\limits_{i=1}^{n}D_{1i}x_i=0$，因此肯定有$\Pr[Dx=0] \leq \Pr[\sum\limits_{i=1}^{n}D_{1i}x_i=0]$。这里我们不妨假设存在一个$D_{1k}=0$（不然这一行$D$全0，我们会得到概率1，放缩放得太大了！所以我们不能取全0行来做这个放缩，这时我们得换一行），那么$\sum\limits_{i=1}^{n}D_{1i}x_i=0$可以移项得$x_k=-\dfrac{1}{D_{1k}}\sum\limits_{i \neq k}D_{1i}x_i$。如果除了$x_k$以外都固定，只有$x_k$随机，那我们发现等式右边就是一个固定的值，因此0和1中最多只有一个值是答案，所以概率小于等于$1/2$。这是我们的直观想法，把“局部固定”这件事严格化就恰好用到了全概率公式——对于每个固定的$x_1,\cdots,x_{k-1},x_{k+1},\cdots ,x_n$，让它附带上$x_k=0$和$x_k=1$，就构成了样本空间的一个划分$E_j$。把$x_k=-\dfrac{1}{D_{1k}}\sum\limits_{i \neq k}D_{1i}x_i$记为事件$G$，于是$\Pr[G]=\sum\limits_{j}\Pr[G \cap E_j]$，转化为条件概率$=\sum\limits_{j}\Pr[G|E_j]\cdot \Pr[E_j]$。易知$\Pr[E_j]$是常数，由于是划分求和后为1。而此时$\Pr[G|E_j]$这个条件概率就转化成我们显然能理解的了，有$\Pr[G|E_j] \leq 1/2$。因此$\sum\limits_{j}\Pr[G|E_j]\cdot \Pr[E_j] \leq \dfrac{1}{2}\sum\limits_{j}\Pr[E_j]$，由于$E_j$是划分，$\sum\limits_{j}\Pr[E_j]=1$。综上$\Pr[G]\leq 1/2$。因此$\Pr[Dx=0] \leq 1/2$。

随机变量

随机变量是从样本空间到实数的映射$\Omega \to \R$。比如“投两个骰子”的样本集有36个基本事件，此时“点数之和”是一个随机变量，$(2,5)$这个样本映射到实数$7$。

形式化地，我们用$X=a$来表示随机变量$X$的取值为$a$这一事件，它其实表示的是集合$\{s\in \Omega|X(s)=a\}$。从映射的角度，我们要在样本空间里找到$a$对应的原像的所有那些事件。更一般的，对于实数中的集合$I$类似的也可以定义事件$X \in I$，它对应着$\{s \in \Omega| X(s) \in I\}$。

我们特别地定义一个记号$\mathbb{1}[A]$表示一个随机变量（函数），其中$A$是一个事件。这个随机变量作用在一个基本事件上，$\mathbb1 [A](\omega)=1$当且仅当$\omega \in A$，否则函数值为0。它直观上用来指示事件$A$是否会发生。

根据基本事件的定义，$\Pr(X=a)=\sum\limits_{X(s)=a,s\in\Omega}\Pr(s)$。由此可见我们其实是在用随机变量描述事件！因此我们可以把事件的性质应用到随机变量上。比如我们可以定义随机变量的独立性：$X$与$Y$独立当且仅当对于任意的$a,b$始终成立$\Pr((X=a)\cap (Y=b))=\Pr(X=a)\cdot\Pr(Y=b)$，记为$X \perp Y$。同样地，对于多个随机变量$X_1,\cdots,X_n$定义它们“互相独立”当且仅当对于任何$I\subseteq [n]$，$\Pr[\bigcap\limits_{i \in I}(X_i=a_i)] = \prod\limits_{i \in I}\Pr(X_i=a_i)$。

现在我们给出两两独立但不互相独立的反例：假设我们抛两次硬币，抛到正面取1，抛到反面取0。因此基本事件就是一个长度为2的01串。设随机变量$X(\omega)$是从基本事件到其第一位的数字的映射（表示第一次的结果），$Y(\omega)$是到第二位数字的映射，而定义$Z(\omega)=X(\omega) \oplus Y(\omega)$（异或），我们可以验证它们两两独立，但当$I=[3]$时$\Pr[X=0 \cap Y=0\cap Z=0]=1/4$，而$\Pr[X=0]=1/2$，$\Pr[Y=0]=1/2$，$\Pr[Z=0]=1/2$，因此不成立，所以它们“两两独立”但是并不是“互相独立”的。

期望的线性性

期望是随机变量的一个重要特征：随机变量的期望定义为其概率的加权平均值。$E[X]=\sum\limits_{i}i\Pr(X=i)$。它也可以按照基本事件来给出$E[X]=\sum\limits_{\omega}X(\omega)\Pr(\omega)$。

一个最重要的定理称为“期望的线性性”，它指出当“期望”这样一个映射作用在若干个随机变量的“和”上时，等价于分别作用于每个随机变量再对它们求和：对于有限个随机变量$X_1,\cdots,X_n$始终满足$E\left[\sum\limits_{i=1}^{n}X_i\right]=\sum\limits_{i=1}^{n}E[X_i]$。证明就是根据定义：$E[X+Y]=\sum\limits_{i}\sum\limits_{j}(i+j)\Pr((X=i)\cap(Y=j))$，提出固定的变量得到$\sum\limits_{i}i\sum\limits_{j}\Pr((X=i)\cap(Y=j))+\sum\limits_{j}j\sum\limits_{i}\Pr((X=i)\cap(Y=j))$，而后面的那个和式恰好就是全概率公式，因此直接可以化简得到$\sum\limits_{i}i\Pr(X=i)+\sum\limits_{j}j\Pr(Y=j)$，这就是$E[X]+E[Y]$。这就证明了期望的线性性。从更高的角度看，期望的线性性其实来自于我们的求和的性质，这个性质在连续世界里就是“积分的线性性”。

重要的是，期望的线性性没有对随机变量提出任何的要求，即使两个随机变量不是“独立”的，它们的期望也始终符合“线性性”这一特征。这对我们计算期望提供极大的方便。

例如，我们求掷两次骰子的期望点数之和，一种方法是令$X$这个随机变量为点数之和，求得$E=\sum\limits_{i=2}^{12}i \cdot \dfrac{1}{6}\cdot \dfrac{1}{6} \cdot \min\{i-1,13-i\}=7$，而如果分别用$X_1$和$X_2$表示单独掷一次骰子的期望（实际上是只看某一次结果的随机变量），容易算出$E_0 = \sum\limits_{i=1}^{6}\dfrac{i}{6}=7/2$，两者相加就能直接得到$7$。

再例如，我们想知道一个给定的长度为$k$的01串在长度为$n$的01随机串里出现的期望次数。 利用期望的线性性，我们只需求出每个固定位置上出现该串的概率，再把它们相加即可。（这里我们用到了“某事件是否发生的期望就是它的概率”这一事实，严格化书写就是$E[\mathbb1[A]]=1 \cdot \Pr[A]+0\cdot \Pr[\overline{A}]=\Pr[A]$）

再看一个有趣的例子。假设在我们在数轴上随机游走，从原点出发，每秒钟等概率向左或向右移动1，问$t$秒以后期望走到哪里。那么根据期望的线性性，每一步都期望移动距离0，因此$t$秒之后还是期望移动距离0，因为我们没有理由偏爱任何一个方向，我们不可能破坏对称性。事实上，对称性让这个问题变得无趣了，任意一个走到$x$的方案都会有一个走到$-x$的方案与它抵消。 一个更有意思的问题是问位移绝对值的期望，那样正负相消就不起效果了——我们从数学上来讨论他，记$Z_t = \sum\limits_{i=1}^{t}X_i$，其中$X_i$是表示第$i$步往右走还是往左走的随机变量。我们用一点数学技巧来解决这个问题，把$|Z_t|$写作$\sum\limits_{i=1}^{t}(|Z_i|-|Z_{i-1}|)$，于是$E[|Z_t|]=\sum\limits_{i=1}^{t}E[|Z_i|-|Z_{i-1}|]$，这是容易计算的，因为$E[|Z_i|-|Z_{i-1}|]=\dfrac{(|Z_{i-1}+1|-|Z_{i-1}|)+(|Z_{i-1}-1|-|Z_{i-1}|)}{2}$，画出函数图像注意到当$Z_{i-1} \geq 1$或$\leq -1$时函数值恒为0，只有在$[-1,1]$形成了一个45度角的突起。而由于任何一个$Z$都是整数，因此这个函数只有可能在$Z=0$时取到1，其余都为0。这样就得到$E[|Z_i|-|Z_{i-1}|]=\mathbb1[Z_{i-1}=0]$。因此$E=\sum\limits_{i=1}^{t}\mathbb1[Z_{i-1}=0]$。容易发现我们只有可能在偶数步的时候回到原点，因此也等价于$E=\sum\limits_{i=0}^{T/2}\mathbb1[Z_{2i}=0]$。这是组合问题，我们必须走相同个数的左边和右边才会回到原点，因此写出$E=\sum\limits_{i=0}^{T/2}\dbinom{2i}{i}\dfrac{1}{2^{2i}}$，用Stirling公式代换阶乘，每一项可以近似为$\dfrac{1}{\sqrt{\pi i}}$，于是$E \approx 1+\sum\limits_{i=1}^{T/2}\dfrac{1}{\sqrt{\pi i}}=O(\sqrt{T})$（用积分来估计）。

当然，为了完善“线性性”这一概念，我们还应当证明$E[cX]=cE[X]$：这是容易的，$E[cX]=\sum\limits_{i}i\Pr(cX=i)=c\sum\limits_{i}i/c\Pr(X=i/c)=cE[X]$。

必须要指出的是，期望的线性性只对“有限个变量求和”成立。当变量有无穷个时它会出问题。我们再次从连续世界来看它，期望本身是一个积分，而对无穷多个变量求和本质上也是一个积分，因此期望的线性性就是一个“重积分能否化为累次积分的问题”，我们知道这是不一定能做到的。