本讲要解决的问题

期望告诉你随机变量「平均」是多少，却不告诉你它有多容易偏离平均值。一个随机变量可以以极小概率取一个极大的值，把期望抬得很高，而绝大多数时候都贴近 $0$。

尾界要回答的是：随机变量离期望很远，概率有多大？ 本讲按「用到的信息越来越多」这条线索推进：

时间轴

Markov 不等式

定理。 设 $X\ge0$，则对任意 $C>0$，

$$\mathbb P(X\ge C)\le\frac{\mathbb E[X]}{C}.$$

证明。 用全期望公式，按事件 $\{X\ge C\}$ 及其补集拆开：

$$\mathbb E[X] =\mathbb E\big[X\mid X\ge C\big]\mathbb P(X\ge C) +\mathbb E\big[X\mid X<C\big]\mathbb P(X<C).$$

第一项中，给定 $X\ge C$ 时 $X$ 至少是 $C$，故条件期望至少为 $C$；第二项中 $X\ge0$，故条件期望非负。于是

$$\mathbb E[X]\ge C\cdot\mathbb P(X\ge C),$$

两边除以 $C$ 即得。$\square$

非负性用在哪里

只用在了「丢掉第二项」这一步。若 $X$ 可以取负值，$\mathbb E[X\mid X<C]$ 可能为负，丢掉它就不再是下界，不等式不成立。

反例：$X=1$ 与 $X=-1$ 各以 $1/2$ 的概率取值，则 $\mathbb E[X]=0$。取 $C=1$，则

$$\mathbb P(X\ge1)=\tfrac12>0=\frac{\mathbb E[X]}{C}.$$

界彻底失效。期望为 $0$ 时右边没有任何约束力。

推论形式

令 $C'=C/\mathbb E[X]$，即取 $C=C'\mathbb E[X]$：

$$\mathbb P\big(X\ge C'\,\mathbb E[X]\big)\le\frac{1}{C'}.$$

最常用的是 $C'=2$：非负随机变量超过其期望两倍的概率不超过 $1/2$。

身高例子

美国成年男性平均身高约 $69$ 英寸。于是

$$\mathbb P(X\ge2\times69=138\text{ 英寸})\le\frac12 .$$

$138$ 英寸约合 $11$ 英尺 $6$ 英寸。这个界在数学上正确，却没有实际意义——Markov 只用了期望，信息太少。身高例子贯穿全讲，用来衡量每个新工具进步了多少。

Chebyshev 不等式

定理。 对任意随机变量 $X$（不要求非负），

$$\mathbb P\big(|X-\mathbb E[X]|\ge C\big)\le\frac{\operatorname{Var}(X)}{C^2}.$$

证明。 两个技巧。

第一步：两个事件相同，因此概率相等。

$$|X-\mathbb E[X]|\ge C \iff \big(X-\mathbb E[X]\big)^2\ge C^2 .$$

第二步：制造一个非负随机变量，好使用 Markov。令

$$Y=\big(X-\mathbb E[X]\big)^2\ge0 .$$

对 $Y$ 用 Markov，阈值取 $C^2$：

$$\mathbb P(Y\ge C^2)\le\frac{\mathbb E[Y]}{C^2} =\frac{\operatorname{Var}(X)}{C^2}.$$

左边正是第一步的事件，证毕。$\square$

推论形式

设 $\sigma(X)=\sqrt{\operatorname{Var}(X)}$ 为标准差。取 $C=c\sigma(X)$：

$$\mathbb P\big(|X-\mathbb E[X]|\ge c\sigma(X)\big)\le\frac{1}{c^2}.$$

$c=2$ 时：偏离两个标准差的概率不超过 $1/4$。

身高的第二个例子

已知男性身高标准差约 $2.7$ 英寸，则 $69+2\times2.7=74.4$ 英寸（约 $6$ 英尺 $2.4$ 英寸）以上（或对称地，以下）的概率不超过 $1/4$。

这个界仍然不紧，但至少不是「$11$ 英尺 $6$ 英寸」这种荒谬结论。信息越多，界越紧——这是全讲的主题。

弱大数定律

陈述

固定 $\varepsilon>0$。设 $X_1,\dots,X_n$ 是某随机变量 $X$ 的独立同分布副本，$\mathbb E[X]=C$，方差有限。令

$$S_n=\frac{1}{n}\sum_{i=1}^{n}X_i .$$

则

$$\lim_{n\to\infty}\mathbb P\big(|S_n-C|\ge\varepsilon\big)=0 .$$

量词顺序很重要：先固定精度 $\varepsilon$（例如民调误差 $0.01$），再找足够大的 $n$。结论说「存在足够大的 $n$ 使概率任意小」，而不是「对所有 $n$ 都小」。

证明

第一步，估计均值。由线性期望，

$$\mathbb E[S_n]=\frac1n\sum_{i=1}^{n}\mathbb E[X_i]=C .$$

$S_n$ 是 $C$ 的无偏估计。

第二步，估计方差——这是全证的关键。缩放一个随机变量时，方差乘以缩放的平方：

$$\operatorname{Var}(S_n)=\frac{1}{n^2}\operatorname{Var}\Big(\sum_{i=1}^{n}X_i\Big).$$

这里必须用独立性：独立随机变量之和的方差等于方差之和。于是

$$\operatorname{Var}\Big(\sum_{i=1}^{n}X_i\Big)=\sum_{i=1}^{n}\operatorname{Var}(X_i)=n\,\sigma^2,$$ $$\operatorname{Var}(S_n)=\frac{n\sigma^2}{n^2}=\frac{\sigma^2}{n}.$$

第三步，用 Chebyshev：

$$\mathbb P\big(|S_n-C|\ge\varepsilon\big) \le\frac{\operatorname{Var}(S_n)}{\varepsilon^2} =\frac{\sigma^2}{n\varepsilon^2}\xrightarrow[n\to\infty]{}0 .$$

定量版本

证明顺带给出了具体的 $n$：要让失败概率不超过 $\delta$，只需

$$n\ge\frac{\sigma^2}{\delta\,\varepsilon^2}.$$

精度要求缩小 $k$ 倍，样本量要增加 $k^2$ 倍。例如误差从 $0.05$ 降到 $0.01$（缩小 $5$ 倍），样本量要增加到 $25$ 倍。

赌博与破产

以掷骰子的 craps 为例，押注接近五五开，庄家优势（house edge）约 $0.0141$。设每局赢 \1$的概率为$p$，输$$1$的概率为$1-p$，则

$$(1-p)-p=0.0141 \Longrightarrow p=0.4929 .$$

每局的期望收益是

$$1\cdot p+(-1)\cdot(1-p)=2p-1=-0.0142<0 .$$

由弱大数定律，局数 $n$ 很大时，平均每局收益以概率 $1$ 逼近 $-0.0142$。累计收益约为 $-0.0142n$，随 $n$ 线性下降。

赌徒破产（gambler's ruin）的通俗表述：任何负期望的游戏，长期玩下去一定破产。直觉上你也许担心「万一运气特别好，一直赢呢」——大数定律说的正是：这种情形发生的概率趋于 $0$。

随机算法的失败概率

设随机算法 $\mathcal A$ 每次运行有 $2/3$ 的概率给出正确答案，$1/3$ 的概率出错。想知道「重复多少次，错误率才能降到可接受的水平」。

把第 $i$ 次运行的结果记为 $X_i\in\{0,1\}$，$X_i=1$ 表示正确，$\mathbb E[X_i]=2/3$。取多数票，即看平均值 $S_n$ 是否低于 $1/2$。失败意味着

$$\Big|S_n-\tfrac23\Big|\ge\tfrac16 .$$

取 $\varepsilon=1/9<\tfrac16$，则失败事件包含在事件 $\{|S_n-\tfrac23|\ge\varepsilon\}$ 之中，所以对这个更大事件的上界也是失败概率的上界。

方差：

$$\operatorname{Var}(X_i)=\tfrac23\cdot\tfrac13=\tfrac29 .$$

Chebyshev 给出

$$\mathbb P(\text{出错})\le\frac{2/9}{n\cdot(1/9)^2}=\frac{2/9}{n/81}=\frac{18}{n}.$$

要让失败概率低于 $10^{-10}$，需要 $n\approx1.8\times10^{11}$ 次。这个数字在实际中不可接受——一台机器每秒跑十亿次也要跑几分钟到几小时。正是这个瓶颈促成了下一讲的 Chernoff 界：同样的目标只需 $n=O(\log(1/\delta))$ 次。

具体场景：素性测试

密码学中要判断一个大整数 $q$ 是否为素数。最好的算法是随机的，每次以 $2/3$ 的概率给出正确答案。若把合数误判为素数，加密方案可能被攻破，代价是敏感信息泄露；因此需要失败概率低到 $10^{-10}$ 甚至 $10^{-30}$。

用 Chebyshev 需要 $10^{10}$ 到 $10^{30}$ 次重复，不现实；Chernoff 把次数降到对数级，这才让随机素性测试成为工程上可用的方案。

成对独立已经够用

回看弱大数定律的证明，独立性只在方差相加这一步用到：

$$\operatorname{Var}\Big(\sum_i X_i\Big)=\sum_i\operatorname{Var}(X_i)+2\sum_{i<j}\operatorname{Cov}(X_i,X_j).$$

只要每一对 $X_i,X_j$ 独立，协方差全为 $0$，方差照样相加。成对独立就足够，不需要三元组、四元组的独立性。

这既是好消息（条件更弱），也是坏消息：Chebyshev 只用到二阶信息，因此给出的界偏松。下一讲的 Chernoff 界会用上「相互独立」这一更强条件，换取指数级的衰减。

Chernoff 界预告

设 $X_1,\dots,X_n$ 相互独立，$X_i\in\{0,1\}$ 且 $\mathbb P(X_i=1)=p_i$，令

$$X=\sum_{i=1}^{n}X_i,\qquad \mu=\mathbb E[X]=\sum_{i=1}^{n}p_i .$$

则对 $0<\delta<1$，

$$\mathbb P\big(|X-\mu|\ge\delta\mu\big)\le2e^{-\mu\delta^2/3}.$$

右边随 $\mu$（也就是随 $n$）指数衰减，而不是 $1/n$ 这种多项式衰减。证明在下一讲。

概率方法

核心思想

要证明某类组合对象存在，不直接构造它，而是证明「随机选一个，以正概率满足要求」。

引理。 设 $X$ 是非负整数值随机变量，且 $\mathbb E[X]<1$。则 $\mathbb P(X=0)>0$。

证明。 由期望的定义并按 $i$ 拆项：

$$\mathbb E[X]=\sum_{i\ge0}i\,\mathbb P(X=i) \ge\sum_{i\ge1}i\,\mathbb P(X=i) \ge\sum_{i\ge1}\mathbb P(X=i) =1-\mathbb P(X=0).$$

于是 $\mathbb P(X=0)\ge1-\mathbb E[X]>0$。$\square$

用法：让 $X$ 数「坏事件」的个数。只要坏事件的期望个数小于 $1$，就存在一个对象，一个坏事件都没有。

Ramsey：六人聚会

任意六个人中，必有三个人两两相识，或者三个人两两陌生。用图论说：对 $K_6$ 的边任意染两色，必存在单色三角形。这就是 Ramsey 数 $R(3,3)=6$。

Ramsey 理论的一般形态是：足够大的对象中，某些有序子结构无法避免。课上还提到「圣经密码」——在《托拉》中按等距取字母能「找到」名人名字与日期；这其实是 Ramsey 现象的伪装，同样的「发现」在《战争与和平》的希伯来文译本里也能找到，并不具有统计显著性。

van der Waerden 定理

$k$ 项等差数列是形如

$$a,\ a+b,\ a+2b,\ \dots,\ a+(k-1)b$$

的整数集合。

定理（van der Waerden）。 对任意 $k$，存在 $n$，使得把 $1,2,\dots,n$ 任意染成红蓝两色，都必然出现一个单色的 $k$ 项等差数列。

把最小的这样的 $n$ 记为 $W(k)$。已知 $W(3)=9$：$1$ 到 $8$ 可以染色避开三项等差，$1$ 到 $9$ 不行。

下面的染色（R 红、B 蓝）在 $1$ 到 $8$ 上避开了所有三项等差数列：

$$1,2,3,4,5,6,7,8 \;\longmapsto\; R,R,B,B,R,R,B,B .$$

逐一检查公差 $b=1,2,3$ 的所有三项等差即可验证。而要证明 $1$ 到 $9$ 无法避免，需要穷举所有染色——这正是计算机暴力搜索的用武之地。

下界：随机染色

定理。 对任意 $k\ge2$，

$$W(k)\ge\sqrt{k-1}\cdot2^{(k-1)/2}.$$

证明。 取 $n<\sqrt{k-1}\cdot2^{(k-1)/2}$，对 $[n]$ 做独立均匀的随机红蓝染色。设 $X$ 为单色 $k$ 项等差数列的个数。

对每一个具体的等差数列 $Q_{a,b}$，令 $I_{a,b}$ 为其单色指示变量。第一个元素颜色任意，其余 $k-1$ 个必须与它相同：

$$\mathbb E[I_{a,b}]=\mathbb P(Q_{a,b}\text{ 单色})=\frac{2}{2^k}=\frac{1}{2^{k-1}}.$$

落在 $[n]$ 内的等差数列个数：起点 $a\le n$，公差 $b\le\dfrac{n}{k-1}$（否则末项超过 $n$），故至多

$$n\cdot\frac{n}{k-1}=\frac{n^2}{k-1}.$$

由期望的线性性（不需要独立性）：

$$\mathbb E[X]\le\frac{n^2}{k-1}\cdot\frac{1}{2^{k-1}}.$$

当 $n<\sqrt{k-1}\cdot2^{(k-1)/2}$ 时，

$$\mathbb E[X]<\frac{(k-1)2^{k-1}}{k-1}\cdot\frac{1}{2^{k-1}}=1 .$$

由概率方法引理，$\mathbb P(X=0)>0$：存在一种染色，没有任何单色 $k$ 项等差数列。因此 $W(k)>n$，取下确界即得所述下界。$\square$

这个证明的妙处在于：我们不知道那种染色长什么样，却知道它一定存在。概率方法把「构造」问题转化成了「算期望」问题。

本节结论

• Markov：$X\ge0$ 时 $\mathbb P(X\ge C)\le\mathbb E[X]/C$；非负性用在丢掉第二项。
• Chebyshev：$\mathbb P(|X-\mathbb E X|\ge C)\le\operatorname{Var}(X)/C^2$；平方造出非负变量。
• 弱大数定律：独立同分布、方差有限时，样本均值依概率收敛到期望；独立性用于方差相加。
• 定量地，$n\ge\sigma^2/(\delta\varepsilon^2)$；精度提高 $k$ 倍需要样本量提高 $k^2$ 倍。
• 负期望游戏长期必输（赌徒破产）。
• 随机算法重复 $n$ 次，Chebyshev 给出 $O(1/n)$ 的失败率，实际不够用。
• 概率方法：$\mathbb E[X]<1$ 且 $X$ 非负整数值 $\Rightarrow$ 存在 $X=0$ 的对象。
• van der Waerden：$W(k)\ge\sqrt{k-1}\,2^{(k-1)/2}$，随机染色证明。

理解检验

1. Markov 不等式的证明中，非负性用在哪一步？构造一个去掉非负性后不等式失效的例子。

参考答案：全期望分解 $\mathbb E[X]=\mathbb E[X\mid X\ge C]\mathbb P(X\ge C)+\mathbb E[X\mid X<C]\mathbb P(X<C)$ 之后，第一项至少是 $C\mathbb P(X\ge C)$，第二项被直接丢掉——只有在 $X\ge0$ 时第二项才非负，丢掉它才是「减小」。若 $X$ 可取负值，第二项可能为负，$\mathbb E[X]\ge C\mathbb P(X\ge C)$ 不成立。反例：$\mathbb P(X=1)=\mathbb P(X=-1)=1/2$，$\mathbb E[X]=0$；取 $C=1$，则 $\mathbb P(X\ge1)=1/2$，而 $\mathbb E[X]/C=0$，不等式失效。

2. 完整写出 Chebyshev 的证明：事件等价是什么？新随机变量怎么定义？为什么可以用 Markov？

参考答案：事件 $\{|X-\mathbb E X|\ge C\}$ 与事件 $\{(X-\mathbb E X)^2\ge C^2\}$ 完全相同，因此概率相等。令 $Y=(X-\mathbb E X)^2$，它是平方，故 $Y\ge0$，满足 Markov 的非负性要求。对 $Y$ 在阈值 $C^2$ 处用 Markov： $\mathbb P(Y\ge C^2)\le\mathbb E[Y]/C^2=\operatorname{Var}(X)/C^2$。 而左边就是原事件的概率，证毕。

3. 弱大数定律的证明中，独立性用在哪一步？为什么成对独立就够？

参考答案：独立性只用在 $\operatorname{Var}(\sum_i X_i)=\sum_i\operatorname{Var}(X_i)$ 这一步。一般地， $\operatorname{Var}(\sum_iX_i)=\sum_i\operatorname{Var}(X_i)+2\sum_{i<j}\operatorname{Cov}(X_i,X_j)$， 而成对独立保证每个 $\operatorname{Cov}(X_i,X_j)=0$，于是方差仍然相加。因此只需要成对独立，不需要所有子集的相互独立。

4. 用 Chebyshev 估计「重复运行 2/3 正确率的算法 n 次、多数投票」的失败率，并算出达到 $10^{-10}$ 所需的 $n$。

参考答案：$X_i$ 为第 $i$ 次是否正确，$\operatorname{Var}(X_i)=\frac23\cdot\frac13=\frac29$。多数投票失败意味着 $S_n<1/2$，即 $|S_n-\frac23|>1/6$。取 $\varepsilon=\frac19$，失败事件包含于 $\{|S_n-\frac23|\ge\frac19\}$，Chebyshev 给出 $\mathbb P(\text{失败})\le\frac{2/9}{n\cdot(1/81)}=\frac{18}{n}$。 令 $18/n\le10^{-10}$，得 $n\ge1.8\times10^{11}$，约 $10^{11}$ 量级，实践上不可行。

5. 证明概率方法引理：$X$ 非负整数值且 $\mathbb E[X]<1$，则 $\mathbb P(X=0)>0$。

参考答案： $\mathbb E[X]=\sum_{i\ge0}i\mathbb P(X=i)\ge\sum_{i\ge1}i\mathbb P(X=i)\ge\sum_{i\ge1}\mathbb P(X=i)=1-\mathbb P(X=0)$。 因此 $\mathbb P(X=0)\ge1-\mathbb E[X]>0$。直观上，若 $X=0$ 几乎不可能，$X$ 就几乎总是至少 $1$，期望不可能小于 $1$。

6. 用随机染色证明 van der Waerden 的下界，写出期望计算的每一步。

参考答案：取 $n<\sqrt{k-1}\,2^{(k-1)/2}$，每个整数独立均匀染红或蓝。设 $X$ 为单色 $k$ 项等差数列的个数。对固定等差列，首项颜色有 $2$ 种选择，其余 $k-1$ 项必须同色，故单色概率为 $2/2^k=2^{-(k-1)}$。落在 $[n]$ 内的等差列个数至多 $n\cdot\frac{n}{k-1}$（起点至多 $n$ 种，公差至多 $n/(k-1)$ 种）。由线性期望， $\mathbb E[X]\le\frac{n^2}{k-1}2^{-(k-1)}<\frac{(k-1)2^{k-1}}{k-1}2^{-(k-1)}=1$。 由引理，存在一种染色使 $X=0$，即无单色 $k$ 项等差列，故 $W(k)>n$。

7. 为什么 $1$ 到 $8$ 上的染色 $RRBBRRBB$ 只证明了 $W(3)\ge9$，而不是 $W(3)=9$？

参考答案：给出一个染色避开三项等差，只说明「$n=8$ 时存在坏染色」，即 $W(3)>8$，也就是 $W(3)\ge9$。要证明 $W(3)\le9$，必须证明 $1$ 到 $9$ 的每一种红蓝染色都含有单色三项等差——这是对 $2^9=512$ 种染色的穷举检验，无法用单个例子代替。

与前后课的关系

上一讲是生成函数；本讲回到概率，建立尾界的工具箱。下一讲证明 Chernoff 界，把尾部衰减从多项式提升到指数级，并说明为什么「相互独立」这个更强条件换来如此大的收益。

再往后依次进入模运算、群论与编码理论。概率方法本身会在后续单元反复出现——它是离散数学里证明「存在性」的标准武器。

What this lecture is for

Expectation tells you what a random variable averages, not how likely it is to drift away from that average. A variable may take a huge value with tiny probability, inflating the expectation while almost always staying near $0$.

A tail bound answers: how likely is a random variable to be far from its expectation? The lecture is organised around using more and more information:

Timeline

Markov's inequality

Theorem. If $X\ge0$, then for every $C>0$,

$$\mathbb P(X\ge C)\le\frac{\mathbb E[X]}{C}.$$

Proof. Split the expectation by the law of total expectation:

$$\mathbb E[X] =\mathbb E\big[X\mid X\ge C\big]\mathbb P(X\ge C) +\mathbb E\big[X\mid X<C\big]\mathbb P(X<C).$$

Given $X\ge C$, the conditional expectation is at least $C$; given $X<C$, non-negativity makes the conditional expectation at least $0$. Hence

$$\mathbb E[X]\ge C\cdot\mathbb P(X\ge C),$$

and dividing by $C$ completes the proof. $\square$

Where non-negativity is used

Only in dropping the second term. If $X$ can be negative, $\mathbb E[X\mid X<C]$ may be negative, and discarding it is no longer a lower bound.

Counterexample: let $X=1$ and $X=-1$ each with probability $1/2$, so $\mathbb E[X]=0$. With $C=1$,

$$\mathbb P(X\ge1)=\tfrac12>0=\frac{\mathbb E[X]}{C}.$$

The bound fails completely. When the expectation is zero the right side constrains nothing.

Corollary form

Put $C'=C/\mathbb E[X]$, i.e. $C=C'\mathbb E[X]$:

$$\mathbb P\big(X\ge C'\,\mathbb E[X]\big)\le\frac{1}{C'}.$$

The most quoted case is $C'=2$: a non-negative variable exceeds twice its expectation with probability at most $1/2$.

The height example

The average US male height is about $69$ inches. Hence

$$\mathbb P(X\ge2\times69=138\text{ inches})\le\frac12 .$$

That is about $11$ feet $6$ inches. The bound is mathematically correct but practically useless — Markov uses only the expectation. The height example runs through the lecture as a yardstick for each new tool.

Chebyshev's inequality

Theorem. For any random variable $X$ (non-negativity not required),

$$\mathbb P\big(|X-\mathbb E[X]|\ge C\big)\le\frac{\operatorname{Var}(X)}{C^2}.$$

Proof. Two tricks.

First, the two events are the same, so their probabilities are equal:

$$|X-\mathbb E[X]|\ge C \iff \big(X-\mathbb E[X]\big)^2\ge C^2 .$$

Second, manufacture a non-negative variable so Markov applies. Let

$$Y=\big(X-\mathbb E[X]\big)^2\ge0 .$$

Apply Markov to $Y$ with threshold $C^2$:

$$\mathbb P(Y\ge C^2)\le\frac{\mathbb E[Y]}{C^2} =\frac{\operatorname{Var}(X)}{C^2}.$$

The left side is the event from step one. $\square$

Corollary form

Let $\sigma(X)=\sqrt{\operatorname{Var}(X)}$ be the standard deviation. Taking $C=c\sigma(X)$,

$$\mathbb P\big(|X-\mathbb E[X]|\ge c\sigma(X)\big)\le\frac{1}{c^2}.$$

For $c=2$: the probability of straying two standard deviations is at most $1/4$.

The second height example

Male height has standard deviation about $2.7$ inches, so the probability of exceeding $69+2\times2.7=74.4$ inches (about $6$ feet $2.4$ inches), or symmetrically falling below, is at most $1/4$.

Still loose, but no longer absurd — nothing like the $11$-foot-$6$ answer. More information yields tighter bounds, the theme of the lecture.

The weak law of large numbers

Statement

Fix $\varepsilon>0$. Let $X_1,\dots,X_n$ be independent copies of a random variable $X$ with $\mathbb E[X]=C$ and finite variance, and let

$$S_n=\frac{1}{n}\sum_{i=1}^{n}X_i .$$

Then

$$\lim_{n\to\infty}\mathbb P\big(|S_n-C|\ge\varepsilon\big)=0 .$$

The order of quantifiers matters: fix the accuracy $\varepsilon$ first (say a polling error of $0.01$), then find a large enough $n$. The claim is not that the probability is small for every $n$, but that a sufficiently large $n$ exists.

Proof

First, the mean. By linearity,

$$\mathbb E[S_n]=\frac1n\sum_{i=1}^{n}\mathbb E[X_i]=C .$$

So $S_n$ is an unbiased estimator of $C$.

Second, the variance — the heart of the proof. Scaling a random variable by a constant scales the variance by its square:

$$\operatorname{Var}(S_n)=\frac{1}{n^2}\operatorname{Var}\Big(\sum_{i=1}^{n}X_i\Big).$$

Independence enters here: the variance of a sum of independent variables is the sum of the variances. Hence

$$\operatorname{Var}\Big(\sum_{i=1}^{n}X_i\Big)=\sum_{i=1}^{n}\operatorname{Var}(X_i)=n\,\sigma^2,$$ $$\operatorname{Var}(S_n)=\frac{n\sigma^2}{n^2}=\frac{\sigma^2}{n}.$$

Third, Chebyshev:

$$\mathbb P\big(|S_n-C|\ge\varepsilon\big) \le\frac{\operatorname{Var}(S_n)}{\varepsilon^2} =\frac{\sigma^2}{n\varepsilon^2}\xrightarrow[n\to\infty]{}0 .$$

A quantitative version

The proof also yields a concrete sample size: to make the failure probability at most $\delta$, it suffices that

$$n\ge\frac{\sigma^2}{\delta\,\varepsilon^2}.$$

Cutting the error by a factor $k$ multiplies the sample size by $k^2$. Going from $0.05$ to $0.01$ (a factor of $5$) needs $25$ times as many samples.

Gambling and ruin

In craps, the closest bet to even money has a house edge of about $0.0141$. Let each round win \1$with probability$p$and lose$$1$ otherwise. Then

$$(1-p)-p=0.0141 \Longrightarrow p=0.4929 .$$

The expected gain per round is

$$1\cdot p+(-1)\cdot(1-p)=2p-1=-0.0142<0 .$$

By the weak law, for large $n$ the average gain per round approaches $-0.0142$ with probability $1$, so cumulative winnings fall roughly linearly at $-0.0142n$.

Gambler's ruin, informally: a game with negative expectation eventually bankrupts you. One might hope for a lucky streak, but the law of large numbers says the probability of sustaining one vanishes.

Failure probability of randomized algorithms

Suppose a randomized algorithm $\mathcal A$ returns the correct answer with probability $2/3$ and an incorrect one with probability $1/3$. How many repetitions are needed to make the error rate acceptable?

Let $X_i\in\{0,1\}$ indicate a correct run, so $\mathbb E[X_i]=2/3$. Take a majority vote, i.e. check whether the average $S_n$ falls below $1/2$. Failure implies

$$\Big|S_n-\tfrac23\Big|\ge\tfrac16 .$$

Choose $\varepsilon=1/9<\tfrac16$; then the failure event is contained in $\{|S_n-\tfrac23|\ge\varepsilon\}$, so a bound on the larger event bounds the failure probability. Since

$$\operatorname{Var}(X_i)=\tfrac23\cdot\tfrac13=\tfrac29 ,$$

Chebyshev gives

$$\mathbb P(\text{failure})\le\frac{2/9}{n\cdot(1/9)^2}=\frac{2/9}{n/81}=\frac{18}{n}.$$

To push the failure probability below $10^{-10}$ requires $n\approx1.8\times10^{11}$ repetitions — impractical. This bottleneck motivates the Chernoff bound of the next lecture, which achieves the same target with $n=O(\log(1/\delta))$.

A concrete setting: primality testing

Cryptography needs to decide whether a large integer $q$ is prime. The best algorithms are randomized and answer correctly with probability $2/3$. Mistaking a composite for a prime can break the scheme and leak sensitive data, so failure probabilities of $10^{-10}$ or even $10^{-30}$ are wanted.

Chebyshev demands $10^{10}$ to $10^{30}$ repetitions, which is hopeless; Chernoff reduces the count to a logarithmic factor, making randomized primality testing practical.

Pairwise independence suffices

Look back at the proof of the weak law. Independence is used only to add variances:

$$\operatorname{Var}\Big(\sum_i X_i\Big)=\sum_i\operatorname{Var}(X_i)+2\sum_{i<j}\operatorname{Cov}(X_i,X_j).$$

If every pair is independent, all covariances vanish and the variances still add. Pairwise independence is enough; no triple or quadruple independence is needed.

That is both good news (a weaker hypothesis) and bad news (Chebyshev uses only second-order information, so the bound is loose). The Chernoff bound will use full mutual independence and buy exponential decay.

Chernoff preview

Let $X_1,\dots,X_n$ be mutually independent with $X_i\in\{0,1\}$ and $\mathbb P(X_i=1)=p_i$, and let

$$X=\sum_{i=1}^{n}X_i,\qquad \mu=\mathbb E[X]=\sum_{i=1}^{n}p_i .$$

Then for $0<\delta<1$,

$$\mathbb P\big(|X-\mu|\ge\delta\mu\big)\le2e^{-\mu\delta^2/3}.$$

The right side decays exponentially in $\mu$ (hence in $n$), not polynomially like $1/n$. The proof is the subject of the next lecture.

The probabilistic method

The core idea

To prove that an object of a certain kind exists, do not construct it; prove that a random object satisfies the requirement with positive probability.

Lemma. Let $X$ be a non-negative integer-valued random variable with $\mathbb E[X]<1$. Then $\mathbb P(X=0)>0$.

Proof. By definition, grouping by the value of $X$:

$$\mathbb E[X]=\sum_{i\ge0}i\,\mathbb P(X=i) \ge\sum_{i\ge1}i\,\mathbb P(X=i) \ge\sum_{i\ge1}\mathbb P(X=i) =1-\mathbb P(X=0).$$

So $\mathbb P(X=0)\ge1-\mathbb E[X]>0$. $\square$

Usage: let $X$ count bad events. If the expected number of bad events is below $1$, some object has none.

Ramsey: six people at a party

Among any six people, either three are pairwise acquainted or three are pairwise strangers. In graph language: in any two-colouring of the edges of $K_6$ there is a monochromatic triangle. This is the Ramsey number $R(3,3)=6$.

Ramsey theory in general: in a large enough object, certain ordered substructures cannot be avoided. The lecture also mentions the "Bible codes" — equally spaced letters in the Torah supposedly revealing names and dates. That is Ramsey theory in disguise: the same "discoveries" appear in a Hebrew translation of War and Peace and carry no statistical significance.

van der Waerden's theorem

A $k$-term arithmetic progression is a set of integers

$$a,\ a+b,\ a+2b,\ \dots,\ a+(k-1)b .$$

Theorem (van der Waerden). For every $k$ there is an $n$ such that every red-blue colouring of $1,2,\dots,n$ contains a monochromatic $k$-term arithmetic progression.

Let $W(k)$ be the least such $n$. It is known that $W(3)=9$: $1$ through $8$ can be coloured to avoid three-term progressions, $1$ through $9$ cannot.

The following colouring (R red, B blue) avoids every three-term progression on $1,\dots,8$:

$$1,2,3,4,5,6,7,8 \;\longmapsto\; R,R,B,B,R,R,B,B .$$

One checks all progressions with common difference $b=1,2,3$. Proving that $1,\dots,9$ admits no such colouring requires exhaustive search over all colourings.

A lower bound by random colouring

Theorem. For every $k\ge2$,

$$W(k)\ge\sqrt{k-1}\cdot2^{(k-1)/2}.$$

Proof. Take $n<\sqrt{k-1}\cdot2^{(k-1)/2}$ and colour $[n]$ independently and uniformly red or blue. Let $X$ count monochromatic $k$-term progressions.

For a fixed progression $Q_{a,b}$, let $I_{a,b}$ indicate that it is monochromatic. The first element may have either colour and the other $k-1$ must match it:

$$\mathbb E[I_{a,b}]=\mathbb P(Q_{a,b}\text{ monochromatic})=\frac{2}{2^k}=\frac{1}{2^{k-1}}.$$

The number of progressions inside $[n]$: the starting point satisfies $a\le n$, and the common difference satisfies $b\le\dfrac{n}{k-1}$ (otherwise the last term exceeds $n$). So there are at most

$$n\cdot\frac{n}{k-1}=\frac{n^2}{k-1}.$$

By linearity of expectation (no independence needed),

$$\mathbb E[X]\le\frac{n^2}{k-1}\cdot\frac{1}{2^{k-1}}.$$

For $n<\sqrt{k-1}\cdot2^{(k-1)/2}$,

$$\mathbb E[X]<\frac{(k-1)2^{k-1}}{k-1}\cdot\frac{1}{2^{k-1}}=1 .$$

The lemma then gives $\mathbb P(X=0)>0$: some colouring has no monochromatic $k$-term progression. Hence $W(k)>n$, and taking the supremum over admissible $n$ yields the stated bound. $\square$

The remarkable feature: we never learn what that colouring looks like, only that it must exist. The probabilistic method turns a construction problem into an expectation computation.

What this lecture establishes

• Markov: for $X\ge0$, $\mathbb P(X\ge C)\le\mathbb E[X]/C$; non-negativity is used to drop the second term.
• Chebyshev: $\mathbb P(|X-\mathbb E X|\ge C)\le\operatorname{Var}(X)/C^2$; squaring creates a non-negative variable.
• Weak law: with i.i.d. finite-variance variables, the sample mean converges in probability to the expectation; independence is used to add variances.
• Quantitatively $n\ge\sigma^2/(\delta\varepsilon^2)$: a $k$-fold accuracy gain costs $k^2$ times the samples.
• Negative-expectation games ruin the player in the long run.
• Repeating a randomized algorithm $n$ times, Chebyshev gives an $O(1/n)$ failure rate — insufficient in practice.
• Probabilistic method: if $X\ge0$ is integer-valued with $\mathbb E[X]<1$, some outcome has $X=0$.
• van der Waerden: $W(k)\ge\sqrt{k-1}\,2^{(k-1)/2}$, proved by random colouring.

Comprehension check

1. Where does the proof of Markov's inequality use non-negativity? Give a counterexample showing the inequality fails without it.

Reference answer: After the total-expectation split $\mathbb E[X]=\mathbb E[X\mid X\ge C]\mathbb P(X\ge C)+\mathbb E[X\mid X<C]\mathbb P(X<C)$, the first term is at least $C\mathbb P(X\ge C)$ and the second is discarded — discarding is only a lowering step when the second term is non-negative, which requires $X\ge0$. Without non-negativity the inequality $\mathbb E[X]\ge C\mathbb P(X\ge C)$ can fail. Counterexample: $\mathbb P(X=1)=\mathbb P(X=-1)=1/2$, so $\mathbb E[X]=0$; with $C=1$, $\mathbb P(X\ge1)=1/2$ while $\mathbb E[X]/C=0$.

2. Write out the proof of Chebyshev: what is the event equivalence, what is the new variable, and why may Markov be applied?

Reference answer: The events $\{|X-\mathbb E X|\ge C\}$ and $\{(X-\mathbb E X)^2\ge C^2\}$ are identical, hence have equal probability. Set $Y=(X-\mathbb E X)^2$, which is a square and therefore non-negative, so Markov applies. Applying Markov to $Y$ at threshold $C^2$, $\mathbb P(Y\ge C^2)\le\mathbb E[Y]/C^2=\operatorname{Var}(X)/C^2$. The left side is the original event, completing the proof.

3. Where does the proof of the weak law use independence? Why is pairwise independence enough?

Reference answer: Independence is used only in $\operatorname{Var}(\sum_iX_i)=\sum_i\operatorname{Var}(X_i)$. In general $\operatorname{Var}(\sum_iX_i)=\sum_i\operatorname{Var}(X_i)+2\sum_{i<j}\operatorname{Cov}(X_i,X_j)$, and pairwise independence makes every covariance zero, so variances still add. Triple or higher-order independence is never used.

4. Use Chebyshev to bound the failure probability of majority vote over $n$ runs of a $2/3$-correct algorithm, and compute the $n$ needed for $10^{-10}$.

Reference answer: Let $X_i$ indicate a correct run, so $\operatorname{Var}(X_i)=\frac23\cdot\frac13=\frac29$. Majority vote fails when $S_n<1/2$, i.e. $|S_n-\frac23|>1/6$. Taking $\varepsilon=\frac19$, the failure event lies inside $\{|S_n-\frac23|\ge\frac19\}$, so Chebyshev gives $\mathbb P(\text{failure})\le\frac{2/9}{n\cdot(1/81)}=\frac{18}{n}$. Requiring $18/n\le10^{-10}$ gives $n\ge1.8\times10^{11}$ — impractical.

5. Prove the probabilistic-method lemma: if $X\ge0$ is integer-valued and $\mathbb E[X]<1$, then $\mathbb P(X=0)>0$.

Reference answer: $\mathbb E[X]=\sum_{i\ge0}i\mathbb P(X=i)\ge\sum_{i\ge1}i\mathbb P(X=i)\ge\sum_{i\ge1}\mathbb P(X=i)=1-\mathbb P(X=0)$. Hence $\mathbb P(X=0)\ge1-\mathbb E[X]>0$. Intuitively, if $X=0$ were almost impossible then $X$ would almost always be at least $1$, and the expectation could not be below $1$.

6. Prove the van der Waerden lower bound by random colouring, showing each step of the expectation computation.

Reference answer: Take $n<\sqrt{k-1}\,2^{(k-1)/2}$ and colour each integer independently red or blue with probability $1/2$. Let $X$ count monochromatic $k$-term progressions. For a fixed progression, the first term has $2$ colour choices and the remaining $k-1$ must match, so the monochromatic probability is $2/2^k=2^{-(k-1)}$. The number of progressions inside $[n]$ is at most $n\cdot\frac{n}{k-1}$ (at most $n$ starting points, at most $n/(k-1)$ common differences). Linearity of expectation gives $\mathbb E[X]\le\frac{n^2}{k-1}2^{-(k-1)}<\frac{(k-1)2^{k-1}}{k-1}2^{-(k-1)}=1$. The lemma then guarantees a colouring with $X=0$, i.e. no monochromatic $k$-term progression, so $W(k)>n$.

7. Why does the colouring $RRBBRRBB$ on $1$–$8$ prove only $W(3)\ge9$, not $W(3)=9$?

Reference answer: Exhibiting one colouring without a three-term progression only shows that $n=8$ is not enough, i.e. $W(3)>8$, hence $W(3)\ge9$. To prove $W(3)\le9$ one must show that every red-blue colouring of $1,\dots,9$ contains a monochromatic three-term progression — a check over all $2^9=512$ colourings, which a single example cannot replace.

Relation to neighbouring lectures

The previous lecture concerned generating functions; this one returns to probability and builds the tail-bound toolkit. The next lecture proves the Chernoff bound, lifting tail decay from polynomial to exponential, and explains why the stronger hypothesis of mutual independence buys so much.

The course then moves to modular arithmetic, group theory and coding theory. The probabilistic method itself recurs throughout the remaining units — it is the standard tool for proving existence in discrete mathematics.