第 05 章 概率分析与随机算法

本章对应原书第 5 章。前几章只看最坏情况；本章引入两种新的分析视角：对输入分布做平均的概率分析，以及让算法自己掷骰子的随机算法。核心工具只有两个：指示器随机变量和期望的线性性。用它们可以几行算出雇用问题、生日悖论、集券问题、最长连续正面、秘书问题的答案。这些结论在量化研究里有直接用处：判断"连涨 10 天"是否异常、理解为什么在几百个因子里总能"挖"出显著的、正确实现置换检验所需的洗牌算法、理解"创新高"次数的零假设基准。概率基础见第 02 册。

学习目标

1. 区分概率分析（对输入分布求平均情况）与随机算法（对算法内部随机选择求期望），理解随机化如何消除"特定的坏输入"。
2. 熟练使用指示器随机变量 \(E[I\{A\}]=\Pr\{A\}\) 与期望的线性性，求雇用次数、逆序对数、同生日对数等期望。
3. 掌握两种产生均匀随机排列的算法（PERMUTE-BY-SORTING、RANDOMIZE-IN-PLACE），能用循环不变式证明 Fisher–Yates 洗牌的正确性，并识别常见的错误洗牌。
4. 记住并会推导生日悖论 \(\Theta(\sqrt n)\)、集券问题 \(b\ln b\)、最长连续正面 \(\Theta(\lg n)\)、秘书问题 \(k=n/e\) 等结论。
5. 能把这些结论用作量化研究的零假设基准：连涨连跌、创新高次数、多重检验、置换检验。

读前导读

这一章在解决什么问题

前几章分析算法时总是盯着"最坏情况"，就像压力测试只看最极端的情景。但很多算法的最坏情况极少发生，只看它会过于悲观。这一章换两种视角：

概率分析：假设输入是随机的，算"平均要花多少"。这像你给一个贷款组合算预期损失：不假设所有借款人同时违约，而是按违约概率加权平均。

随机算法：不去赌输入是否随机，而是让算法自己"掷骰子"，比如先把数据洗乱再处理。这样一来，没有哪个特定输入能稳定地让算法表现很差。这像做抽样审计时用随机数表选凭证：被审计方没法预先知道你会查哪几张，也就没法针对性地做手脚。

全章的核心技巧只有一个，而且你一定会喜欢：要算"某件事平均发生几次"，就给每个可能的发生点配一个 0/1 开关，分别算每个开关打开的概率，然后直接相加。 这一步不需要各个开关相互独立。比如一个 100 笔贷款的组合，每笔违约概率 2%，那么预期违约笔数就是 \(100\times2\%=2\) 笔，无论贷款之间相关性多强都成立（相关性影响的是违约笔数的分布和尾部，不影响期望）。用这个技巧，本章能几行推出：扫描数据时"创新高"的期望次数、多少人里大概率有两人同生日、抛硬币最长连续正面有多长，以及"先看 37% 再出手"的最优停止法则。这些结论直接给量化研究提供"零假设下应该看到什么"的基准。

需要先想起来的数学

• 期望与条件概率。 \(E[X]=\sum_x x\Pr\{X=x\}\)；\(\Pr\{A\cap B\}=\Pr\{A\}\Pr\{B\mid A\}\)（乘法法则，可以一直链下去）。你在 CFA 里都学过。详见 第 00 册第 07 章 概率中的分析工具。
• 几何分布的期望。 每次成功概率为 \(p\)，独立重复直到第一次成功，平均要试 \(1/p\) 次。例：掷骰子直到出现 6，平均 6 次。集券问题会用到它。
• 调和数 \(H_n\)。 \(H_n=1+\frac12+\cdots+\frac1n\approx\ln n+0.577\)。例：\(H_{10}\approx2.93\)，\(\ln10\approx2.30\)。它增长得和对数一样慢。详见 第 00 册第 04 章 级数与收敛。
• 不等式 \(1+x\le e^x\)。 对所有实数成立，\(x\) 接近 0 时两边几乎相等，例如 \(1-0.01=0.99\)，\(e^{-0.01}\approx0.99005\)。它让我们把一串连乘 \(\prod(1-\frac in)\) 换成指数，便于估算。详见 第 00 册第 02 章 导数与泰勒展开。
• 阶乘与排列数。 \(n\) 个不同元素有 \(n!\) 种排列；从 \(n\) 个中取 \(k\) 个排成一列有 \(\frac{n!}{(n-k)!}\) 种；从 \(n\) 个中选 \(k\) 个（不论顺序）有 \(\binom nk=\frac{n!}{k!(n-k)!}\) 种。\(\binom n2=\frac{n(n-1)}{2}\) 就是"两两配对"的对数。

怎么读这一章

5.1、5.2 节是核心：理解"概率分析 vs 随机算法"的区别，练熟指示器随机变量的用法，雇用问题的 \(H_n\) 推导务必看懂。5.3 节的 Fisher–Yates 洗牌和"错误的洗牌"对写置换检验、bootstrap 的人非常重要，循环不变式证明可以第二遍再细读。5.4 节带 ★，四个小专题相互独立：生日悖论和最长连续正面直接关系到"巧合是否显著"，建议读；球与箱子、秘书问题可以只看结论。量化实战的六条解读是本章最有用的部分，特别是第 1 条"收益创新高与价格创新高的基准不同"。

5.1 雇用问题

问题与代价模型

你要通过职业介绍所雇一名办公助理，每天来一位候选人。每面试一人付一笔小额费用 \(c_i\)；真正雇用的代价 \(c_h\) 很高（要解雇现任并付介绍所一大笔费用）。你的策略是：任何时候都要有目前见过的最好的人，所以面试后只要新人比现任好，就立即换人。

HIRE-ASSISTANT(n)
1  best = 0              // 0 号是虚拟的最差候选人
2  for i = 1 to n
3      面试候选人 i
4      if 候选人 i 比候选人 best 好
5          best = i
6          雇用候选人 i

若雇用了 \(m\) 人，总代价为 \(O(c_in+c_hm)\)。面试费 \(c_in\) 是固定的，需要分析的是随输入变化的雇用费 \(c_hm\)。这个情境是一种常见计算模式的模型：扫描序列并维护当前"胜者"（最大值），雇用问题问的是胜者被更新的频率。在量化里，它就是"数据扫描中创新高的次数"。

最坏情况：候选人按质量严格递增出现，每人都被雇用，代价 \(O(c_hn)\)。但我们既不知道也控制不了到达顺序，所以自然要问平均情况。

概率分析与随机算法

概率分析（probabilistic analysis）在分析中使用概率：了解或假设输入的分布，对所有可能的输入求平均，得到平均情况运行时间（average-case running time）。输入分布要选得合理；有些问题无法给出合理的输入分布，就不能用概率分析。

对雇用问题，假设候选人之间存在全序，用 \(rank(i)\in\{1,\dots,n\}\) 表示第 \(i\) 位的名次（越大越好）。"候选人以随机顺序到达"等价于 \(\langle rank(1),\dots,rank(n)\rangle\) 等可能地是 \(n!\) 个排列中的任何一个，称为均匀随机排列（uniform random permutation）。

但我们往往并不知道输入是否真的随机。随机算法（randomized algorithm）换了一个思路：不去假设输入分布，而是由算法强加一个分布。比如介绍所预先把全部名单发来，我们每天随机选一个人面试。若算法的行为不仅由输入决定，还由随机数发生器（random-number generator）产生的值决定，就称它是随机的。设 RANDOM(a, b) 等可能地返回 \(a\) 到 \(b\) 之间（含两端）的整数，每次调用相互独立。实践中用的是伪随机数发生器（pseudorandom-number generator）：确定性算法，产生统计上"看起来"随机的数。

术语区分：概率分布在输入上时，求得的是平均情况运行时间；概率来自算法自身的随机选择时，求得的是期望运行时间（expected running time）。

练习 5.1-2、5.1-3 是两个小技巧。只用 RANDOM(0,1) 实现 RANDOM(a,b)：生成 \(\lceil\lg(b-a+1)\rceil\) 位随机比特，超出范围就重来，期望 \(O(\lg(b-a))\)。用一个以未知概率 \(p\) 输出 1 的有偏硬币产生无偏比特（von Neumann 技巧）：连掷两次，01 输出 0，10 输出 1，相同则重来；因为 \(\Pr\{01\}=\Pr\{10\}=p(1-p)\)，期望调用 \(1/(p(1-p))\) 对。

5.2 指示器随机变量

定义与引理

给定样本空间 \(S\) 和事件 \(A\)，**指示器随机变量（indicator random variable）**定义为

引理 5.1 令 \(X_A=I\{A\}\)，则 \(E[X_A]=\Pr\{A\}\)。证明：\(E[X_A]=1\cdot\Pr\{A\}+0\cdot\Pr\{\bar A\}=\Pr\{A\}\)。

单独看它平淡无奇，威力在于与**期望的线性性（linearity of expectation）**结合：随机变量之和的期望等于期望之和，即使它们不独立。例如 \(n\) 次抛均匀硬币的正面数 \(X=\sum_iX_i\)，\(X_i=I\{\text{第 }i\text{ 次正面}\}\)，

远比先求出 \(\Pr\{X=k\}\) 再加权求和简单。

金融直觉：期望的线性性为什么不需要独立？因为期望只是"加权平均"，而加法可以和平均交换顺序。看一个两笔贷款的例子：两笔贷款违约概率都是 10%，但完全正相关（要么都违约，要么都不违约）。违约笔数 \(X\) 只有两种结果：0（概率 90%）或 2（概率 10%），\(E[X]=0.2\)。用指示器：\(E[X_1]+E[X_2]=0.1+0.1=0.2\)，一样。若两笔独立，\(X\) 的分布变成 0、1、2 三种结果，但期望仍是 0.2。相关性改变的是方差和尾部（这正是信用组合风险管理关心的），不改变期望。 指示器的作用是把"数个数"变成"求概率"：想知道某事平均发生几次，就把每个可能的发生点各自的发生概率加起来。

用指示器变量分析雇用问题

设候选人以随机顺序到达，\(X\) 为雇用次数。令 \(X_i=I\{\text{候选人 }i\text{ 被雇用}\}\)，\(X=X_1+\cdots+X_n\)。候选人 \(i\) 被雇用当且仅当他比前 \(i-1\) 人都好。由于随机到达，前 \(i\) 人也以随机顺序出现，其中每个人都等可能是这 \(i\) 人中最好的，所以

\(H_n\) 是调和数（harmonic number）。面试 \(n\) 人，平均只雇约 \(\ln n\) 人。

推导拆解：关键一步是 \(\Pr\{\text{候选人 }i\text{ 被雇用}\}=\frac1i\)。候选人 \(i\) 被雇用，等价于"他是前 \(i\) 个人里最好的"。前 \(i\) 个人以随机顺序到达，最好的那个落在第 1、第 2、……、第 \(i\) 个位置的可能性相同，落在最后（第 \(i\) 位）的概率就是 \(\frac1i\)。例如第 4 位候选人：前 4 人中最好的是他的概率为 \(\frac14\)。 然后对每一位求和：第 1 位一定被雇（\(\frac11\)），第 2 位一半机会（\(\frac12\)），第 3 位 \(\frac13\)……合计 \(H_n\)。\(n=2520\)（十年交易日）时 \(H_n\approx8.4\)。 金融直觉：把"候选人"换成"每天的日收益"，"被雇用"就是"当天收益创下样本期内的最高纪录"。如果收益是独立同分布的，十年里平均只会出现约 8 次这样的纪录，而且越往后越稀少：第 1000 天创纪录的概率只有千分之一。

引理 5.2 候选人以随机顺序出现时，HIRE-ASSISTANT 的平均情况总雇用费为 \(O(c_h\ln n)\)，远好于最坏情况的 \(O(c_hn)\)。

几个练习的结论

• 练习 5.2-1：恰好雇用 1 次的概率是 \(1/n\)（最好的人第一个来）；恰好雇用 \(n\) 次的概率是 \(1/n!\)（严格递增）。
• 练习 5.2-2：恰好雇用 2 次的概率。第一位的名次为 \(k<n\)（概率 \(1/n\)），且名次高于 \(k\) 的 \(n-k\) 人中，最好的那位最先出现（概率 \(\frac1{n-k}\)），所以 \(\Pr=\frac1n\sum_{k=1}^{n-1}\frac1{n-k}=\frac{H_{n-1}}n\)。对 \(n=6\) 枚举全部 720 个排列可验证两边都等于 \(0.38056\)。
• 练习 5.2-3：\(n\) 个骰子点数和的期望是 \(3.5n\)。
• 练习 5.2-4（帽子保管问题）：\(n\) 位顾客的帽子被随机归还，期望拿回自己帽子的人数是 \(n\cdot\frac1n=1\)，与 \(n\) 无关。
• 练习 5.2-5：均匀随机排列的期望逆序对数。每对 \((i,j)\) 逆序的概率是 \(1/2\)，共 \(\binom n2\) 对，期望 \(n(n-1)/4\)。结合第 01 章，插入排序在随机输入上的平均运行时间是 \(\Theta(n+n^2/4)=\Theta(n^2)\)。

5.3 随机算法

从假设分布到强加分布

把雇用问题改为先随机打乱候选人顺序，再执行原算法：

RANDOMIZED-HIRE-ASSISTANT(n)
1  随机排列候选人列表
2  best = 0
3  for i = 1 to n
4      面试候选人 i
5      if 候选人 i 比候选人 best 好
6          best = i
7          雇用候选人 i

引理 5.3 RANDOMIZED-HIRE-ASSISTANT 的期望雇用费为 \(O(c_h\ln n)\)。证明：打乱之后的情形与 5.2 节的概率分析完全相同。

两个引理结论一样，含义不同。确定性算法对固定输入的雇用次数是固定的：名次列表 \(\langle1,2,\dots,10\rangle\) 总是雇 10 次，\(\langle10,9,\dots,1\rangle\) 只雇 1 次，\(\langle5,2,1,8,4,7,10,9,3,6\rangle\) 雇 3 次（名次 5、8、10 的人）。存在固定的昂贵输入。随机化版本对同一个输入每次运行的结果都不同；没有哪个特定输入会必然引发最坏行为，即使对手也无法构造坏输入，只有随机数发生器产生"不走运"的排列时才表现差。引理 5.2 依赖输入分布的假设（平均情况），引理 5.3 不依赖任何假设（期望），代价是打乱输入要额外花时间。第 7 章的随机化快速排序就是这个思路。

方法一：PERMUTE-BY-SORTING

给每个元素赋一个随机优先级，再按优先级排序。例：\(A=\langle1,2,3,4\rangle\)，\(P=\langle36,3,62,19\rangle\)，得 \(B=\langle2,4,1,3\rangle\)。

PERMUTE-BY-SORTING(A)
1  n = A.length
2  令 P[1..n] 为新数组
3  for i = 1 to n
4      P[i] = RANDOM(1, n^3)
5  以 P 为键对 A 排序

时间瓶颈是排序，比较排序为 \(\Theta(n\lg n)\)。优先级取自 \(1..n^3\) 是为了让它们大概率互不相同：由联合界，存在相等的概率不超过 \(\binom n2/n^3<1/n\)（练习 5.3-5）。

引理 5.4 若所有优先级互不相同，PERMUTE-BY-SORTING 产生均匀随机排列。证明：先看恒等排列。令 \(E_i\) 为"\(A[i]\) 得到第 \(i\) 小的优先级"，则

因为给定前 \(i-1\) 个元素依次拿到最小的 \(i-1\) 个优先级，剩下 \(n-i+1\) 个元素等可能拿到第 \(i\) 小。对任意固定排列 \(\sigma\)，把 \(E_i\) 改为"\(A[i]\) 的优先级名次为 \(\sigma(i)\)"，同样得 \(1/n!\)。

推导拆解：那串连乘用的是概率的乘法法则 \(\Pr\{A\cap B\}=\Pr\{A\}\Pr\{B\mid A\}\)，反复用 \(n-1\) 次。以 \(n=3\) 为例：\(A[1]\) 拿到 3 个优先级中最小的，概率 \(\frac13\)（3 个元素地位对称）；已知如此，\(A[2]\) 在剩下 2 个元素中拿到较小的，概率 \(\frac12\)；最后 \(A[3]\) 只能拿剩下那个，概率 1。相乘得 \(\frac16=\frac1{3!}\)。每个具体排列都是 \(\frac16\)，所以 6 种排列等可能，这就是"均匀随机排列"的定义。

常见误区：以为证明"每个元素落在每个位置的概率都是 \(1/n\)"就够了。这个条件更弱，不充分。练习 5.3-4 的循环移位算法（随机取偏移量 \(s\)，把 \(A[i]\) 放到位置 \((i+s)\bmod n\)）满足它，但只能产生 \(n\) 种排列，远不是均匀的 \(n!\) 种。

方法二：RANDOMIZE-IN-PLACE（Fisher–Yates 洗牌）

更好的方法是原地洗牌：第 \(i\) 次迭代从 \(A[i..n]\) 中随机选一个元素放到 \(A[i]\)，此后 \(A[i]\) 不再改变。

RANDOMIZE-IN-PLACE(A)
1  n = A.length
2  for i = 1 to n
3      交换 A[i] 与 A[RANDOM(i, n)]

时间 \(\Theta(n)\)，额外空间 \(O(1)\)。这就是 Fisher–Yates 洗牌（Knuth 洗牌）。

引理 5.5 RANDOMIZE-IN-PLACE 产生均匀随机排列。

证明用循环不变式。先定义：从 \(n\) 个元素中取 \(k\) 个、不重复地排成一列，叫一个 \(k\) 排列（\(k\)-permutation），共 \(n!/(n-k)!\) 种。

不变式：第 \(i\) 次迭代之前，对每个可能的 \((i-1)\) 排列，子数组 \(A[1..i-1]\) 恰好是它的概率为 \((n-i+1)!/n!\)。

• 初始化：\(i=1\)，概率为 \(n!/n!=1\)。\(A[1..0]\) 为空，0 排列不含任何元素，空子数组以概率 1 "包含"它。
• 保持：考虑一个特定的 \(i\) 排列 \(\langle x_1,\dots,x_i\rangle\)。令 \(E_1\) 为前 \(i-1\) 次迭代在 \(A[1..i-1]\) 中产生 \(\langle x_1,\dots,x_{i-1}\rangle\)，由不变式 \(\Pr\{E_1\}=(n-i+1)!/n!\)；令 \(E_2\) 为第 \(i\) 次迭代把 \(x_i\) 放到 \(A[i]\)。第 3 行从 \(A[i..n]\) 的 \(n-i+1\) 个值中均匀选择，所以

• 终止：\(i=n+1\)，\(A[1..n]\) 是任一给定 \(n\) 排列的概率为 \(0!/n!=1/n!\)。

白话解释：Fisher–Yates 就是"从帽子里不放回地抽签"。第 1 步从全部 \(n\) 个里抽一个放在第 1 位；第 2 步从剩下 \(n-1\) 个里抽一个放第 2 位；依此类推。任何一个具体排列出现的概率都是 \(\frac1n\cdot\frac1{n-1}\cdots\frac11=\frac1{n!}\)。 不变式里那个看起来吓人的 \(\frac{(n-i+1)!}{n!}\) 其实就是"前 \(i-1\) 步恰好抽出某个指定序列"的概率：\(\frac1n\cdot\frac1{n-1}\cdots\frac1{n-i+2}\)。以 \(n=4\)、\(i=3\) 为例：前 2 位恰好是某个指定的两元素序列，概率 \(\frac14\cdot\frac13=\frac1{12}=\frac{2!}{4!}\)，与公式一致。 它和错误写法 PERMUTE-WITH-ALL 的区别在于：每一步只从"还没定位的那部分"里抽，已经放好的不再动。错误写法每一步都从整个数组里抽，相当于"放回抽签"，路径总数 \(n^n\) 无法平均分给 \(n!\) 种排列。

错误的洗牌

原书几道练习专门讨论看起来对、实际错的洗牌，这些都是实务中真实出现过的 bug：

• 练习 5.3-2：想产生"除恒等排列外的任意排列"，把第 3 行改成与 A[RANDOM(i+1, n)] 交换（循环到 \(n-1\)）。它只能产生 \((n-1)!\) 种排列（恰好是所有的 \(n\)-循环，即 Sattolo 算法），\(n=3\) 时只有两种，并非全部非恒等排列。
• 练习 5.3-3（PERMUTE-WITH-ALL）：每次与 A[RANDOM(1, n)] 交换，即总在整个数组中选。共有 \(n^n\) 条等可能的执行路径，要平均分给 \(n!\) 个排列，而 \(n^n\) 一般不能被 \(n!\) 整除（\(n=3\) 时 27 条路径分给 6 个排列），所以不可能均匀。
• 练习 5.3-4：上面的循环移位，只满足"每个元素落在每个位置的概率为 \(1/n\)"。
• 练习 5.3-1：若有人质疑"空子数组包含 0 排列的概率为 1"，可以先把 \(A[1]\) 与 \(A[\text{RANDOM}(1,n)]\) 交换，再从 \(i=2\) 开始循环，让不变式从非空子数组开始。
• 练习 5.3-6：PERMUTE-BY-SORTING 中出现相同优先级时，对这些并列元素重新抽取优先级并再排序。

随机抽样（练习 5.3-7）

要从 \(\{1,\dots,n\}\) 中均匀抽取一个 \(m\) 元子集，可以洗牌后取前 \(m\) 个，但要调用 \(n\) 次 RANDOM。\(n\gg m\) 时，下面的递归过程（Floyd 抽样）只调用 \(m\) 次，并且每个 \(m\) 子集等可能：

RANDOM-SAMPLE(m, n)
1  if m == 0
2      return ∅
3  else S = RANDOM-SAMPLE(m - 1, n - 1)
4      i = RANDOM(1, n)
5      if i ∈ S
6          S = S ∪ {n}
7      else S = S ∪ {i}
8      return S

5.4 ★ 概率分析的进一步应用

生日悖论

房间里至少要有多少人，才有 50% 的机会出现两人同生日？答案远少于 365，甚至少于其一半。

设有 \(k\) 人，一年 \(n=365\) 天，生日 \(b_i\) 独立且均匀分布。两人同生日的概率为

精确分析（补事件）。 令 \(B_k\) 为"\(k\) 人生日两两不同"。第 \(k\) 人要避开前 \(k-1\) 人已占的日子，所以

这里用了第 03 章的 \(1+x\le e^x\)。当 \(k(k-1)\ge2n\ln2\)，即 \(k\ge(1+\sqrt{1+(8\ln2)n})/2\) 时，\(\Pr\{B_k\}\le1/2\)。\(n=365\) 时 \(k\ge23\)（直接计算，23 人时至少两人同生日的概率为 \(0.5073\)）。火星一年 669 个火星日，需要 31 个火星人。

推导拆解：从连乘到指数这一步分两小步。第一步，每个因子 \(1-\frac in\) 都满足 \(1-\frac in\le e^{-i/n}\)（在 \(1+x\le e^x\) 里取 \(x=-\frac in\)），各因子都是正数，所以连乘也保持不等号。第二步，指数相乘变成指数相加：\(\prod_{i=1}^{k-1}e^{-i/n}=e^{-(1+2+\cdots+(k-1))/n}=e^{-k(k-1)/2n}\)，用了 \(1+2+\cdots+(k-1)=\frac{k(k-1)}2\)。 再令 \(e^{-k(k-1)/2n}\le\frac12\)，两边取对数得 \(\frac{k(k-1)}{2n}\ge\ln2\)，即 \(k(k-1)\ge2n\ln2\)。\(n=365\) 时右边约 506，\(23\times22=506\)，所以 23 人就够。 直觉：\(k\) 个人能组成 \(\binom k2\approx\frac{k^2}2\) 对，每对撞日的概率是 \(\frac1n\)。配对数随人数的平方增长，所以人数只要到 \(\sqrt n\) 量级，"至少有一对撞上"就变得很可能。

指示器变量的近似分析。 对每对 \(i<j\) 令 \(X_{ij}=I\{i,j\text{ 同生日}\}\)，\(E[X_{ij}]=1/n\)。同生日的对数 \(X=\sum_{i<j}X_{ij}\)，

\(k(k-1)\ge2n\) 时期望至少有一对，即约 \(\sqrt{2n}+1\) 人。\(n=365\)、\(k=28\) 时 \(E[X]=\frac{28\cdot27}{2\cdot365}\approx1.0356\)；火星需 38 人。两种分析回答的问题不同（概率过半 vs 期望达到 1），具体人数不同，但量级相同，都是 \(\Theta(\sqrt n)\)。注意指示器分析只用到了两两独立（练习 5.4-3）。

几个变体（练习 5.4-1、5.4-4、5.4-5）：要使"有人与你同生日"的概率至少 1/2，需 \(1-(364/365)^k\ge1/2\)，\(k\ge253\)；要使"7 月 4 日至少两人生日"的概率超过 1/2，需 \(k=613\)；要使期望的三人同生日组数 \(\binom k3/n^2\) 至少为 1，需 \(k=94\)，量级是 \(\Theta(n^{2/3})\)；长度 \(k\) 的串构成 \(k\) 排列的概率是 \(\frac{n!}{(n-k)!n^k}\)，就是生日两两不同的概率。

球与箱子

把球独立地随机投入 \(b\) 个箱子，每次落入任一箱子的概率为 \(1/b\)。这个模型是分析散列表（第 11 章）的基础。

• 投 \(n\) 个球后某个给定箱子里的球数服从二项分布，期望 \(n/b\)。
• 给定箱子第一次有球平均要投几次？几何分布，期望 \(b\) 次。
• 要使每个箱子至少有一个球，平均要投几次？把"落入空箱"称为命中，把投掷过程按命中次数分成 \(b\) 个阶段。第 \(i\) 阶段时已有 \(i-1\) 个箱子非空，命中概率 \((b-i+1)/b\)，该阶段的投掷次数是几何分布，期望 \(\frac b{b-i+1}\)。由线性性，

这就是集券问题（coupon collector's problem）：集齐 \(b\) 种优惠券期望要收集约 \(b\ln b\) 张。

白话解释：拆成阶段后，每个阶段都是"重复尝试直到成功"，平均次数 = 1 / 成功概率。以 \(b=4\) 为例：第 1 个球必然落进空箱（平均 1 次）；之后有 3 个空箱，命中概率 \(\frac34\)，平均 \(\frac43\) 次；再之后 \(\frac24\)，平均 2 次；最后只剩 1 个空箱，命中概率 \(\frac14\)，平均 4 次。合计 \(1+\frac43+2+4\approx8.33=4H_4\)。可见大部分时间花在最后几个"难凑的"箱子上。量化里的例子：想通过有放回随机抽样把 500 只股票全部"见过一遍"，平均要抽约 \(500\times H_{500}\approx3400\) 次，是股票数的近 7 倍。

练习 5.4-2：投到某个箱子有两个球为止，期望投掷次数为 \(\Theta(\sqrt b)\)，这又是生日悖论。练习 5.4-6：\(n\) 个球投入 \(n\) 个箱子，期望空箱数为 \(n(1-1/n)^n\approx n/e\)，恰有一个球的箱子期望数为 \(n(1-1/n)^{n-1}\approx n/e\)。

最长连续正面

抛均匀硬币 \(n\) 次，最长连续正面的期望长度是 \(\Theta(\lg n)\)。

上界。 令 \(A_{ik}\) 为"从第 \(i\) 次开始至少 \(k\) 次连续正面"，\(\Pr\{A_{ik}\}=1/2^k\)。取 \(k=2\lceil\lg n\rceil\)，则 \(\Pr\{A_{ik}\}\le1/n^2\)。由 Boole 不等式（并集概率不超过概率之和，不要求独立），

令 \(L\) 为最长连续正面长度，把期望拆成两部分：\(L<2\lceil\lg n\rceil\) 时 \(L\) 小；\(L\ge2\lceil\lg n\rceil\) 时概率小于 \(1/n\)，而 \(L\le n\)。于是

推导拆解：这个上界的手法是"把期望拆成两段，各自往大里估"。\(E[L]=\sum_\ell\ell\Pr\{L=\ell\}\) 分成 \(\ell<2\lceil\lg n\rceil\) 和 \(\ell\ge2\lceil\lg n\rceil\) 两部分。前一部分里每个 \(\ell\) 都小于 \(2\lceil\lg n\rceil\)，而这些概率加起来不超过 1，所以这部分不超过 \(2\lceil\lg n\rceil\)。后一部分里每个 \(\ell\) 都不超过 \(n\)（最长不可能超过抛掷次数），而这些概率加起来小于 \(\frac1n\)，所以这部分小于 \(n\cdot\frac1n=1\)。两部分相加就是 \(O(\lg n)\)。 Boole 不等式（也叫联合界）\(\Pr\{A_1\cup A_2\cup\cdots\}\le\sum\Pr\{A_i\}\) 在这里很关键：不同起点的长连串彼此重叠、并不独立，但联合界不需要独立。风险管理里"各子组合 VaR 违规概率之和是整体至少一处违规概率的上界"就是同一个不等式。

尾部衰减很快：最长连续正面至少 \(r\lceil\lg n\rceil\) 的概率不超过 \(1/n^{r-1}\)。\(n=1000\) 时，出现至少 20 个连续正面的概率至多 \(1/1000\)，至少 30 个的概率至多 \(10^{-6}\)。

下界。 把 \(n\) 次抛掷切成长度 \(s=\lfloor(\lg n)/2\rfloor\) 的不重叠组，约 \(2n/\lg n\) 组。某组全为正面的概率 \(1/2^s\ge1/\sqrt n\)，各组独立，所以所有组都不全为正面的概率至多

因此 \(L\ge\lfloor(\lg n)/2\rfloor\) 的概率至少 \(1-O(1/n)\)，\(E[L]=\Omega(\lg n)\)。

指示器近似。 长度至少 \(k\) 的连续正面段（按起点计）的期望个数是 \(\frac{n-k+1}{2^k}\)。取 \(k=c\lg n\) 得 \(\Theta(1/n^{c-1})\)：\(c>1\) 时几乎不会出现，\(c=1/2\) 时期望个数约 \(\sqrt n\)，几乎必然出现。仅凭这个粗算就能看出答案是 \(\Theta(\lg n)\)。练习 5.4-7 进一步强化下界：不出现长于 \(\lg n-2\lg\lg n\) 的连续正面的概率小于 \(1/n\)。

在线雇用问题（秘书问题）

变体：只想雇一次，每次面试后必须当场决定录用或拒绝，愿意接受"接近最好"以换取只雇一次。策略：选定 \(k\)，面试并拒绝前 \(k\) 人，记住其中最高分；此后录用第一个超过这个分数的人；若一直没有，录用最后一人。

ON-LINE-MAXIMUM(k, n)
1  bestscore = -∞
2  for i = 1 to k
3      if score(i) > bestscore
4          bestscore = score(i)
5  for i = k + 1 to n
6      if score(i) > bestscore
7          return i
8  return n

分析。 令 \(S_i\) 为"最好的人在位置 \(i\) 且被录用"，\(i\le k\) 时不可能成功。最好的人在位置 \(i>k\) 并被录用，需要两件事：\(B_i\) 为最好的人在位置 \(i\)，概率 \(1/n\)；\(O_i\) 为位置 \(k+1..i-1\) 的人都没被录用，即前 \(i-1\) 人中的最高者落在前 \(k\) 个位置，概率 \(k/(i-1)\)。\(B_i\) 只依赖位置 \(i\) 是否是全局最大，\(O_i\) 只依赖前 \(i-1\) 个位置的相对顺序，两者独立。所以

对 \(k\) 求导，\(\frac1n(\ln n-\ln k-1)=0\)，得 \(k=n/e\)，此时成功概率至少 \(1/e\approx0.368\)。这就是著名的 1/e 法则：先只看不选约 37% 的候选人，之后选第一个超过此前所有人的。

推导拆解：三个步骤。 其一，\(\Pr\{O_i\}=\frac k{i-1}\)：前 \(i-1\) 人里最好的那位等可能落在这 \(i-1\) 个位置中的任意一个，落在前 \(k\) 个（观察期）的概率是 \(\frac k{i-1}\)。只有这样，位置 \(k+1\) 到 \(i-1\) 的人才都不会超过观察期的最高分，从而都不会被录用。 其二，和式换下标后是调和数的一段 \(\frac1k+\cdots+\frac1{n-1}\)，它大于积分 \(\int_k^n\frac{dx}{x}=\ln n-\ln k\)（每个 \(\frac1i\) 是宽度为 1 的矩形，盖住了曲线 \(\frac1x\) 在 \([i,i+1]\) 上的面积）。 其三，求下界 \(g(k)=\frac kn(\ln n-\ln k)\) 的最大值：对 \(k\) 求导，用乘积法则，\(g'(k)=\frac1n(\ln n-\ln k)+\frac kn\cdot(-\frac1k)=\frac1n(\ln n-\ln k-1)\)；令其为 0 得 \(\ln\frac nk=1\)，即 \(k=\frac ne\)。代回去 \(g=\frac1e\cdot1=\frac1e\)。 这里求导与"求使利润最大的产量"是同一套操作，详见 第 00 册第 02 章 导数与泰勒展开。

5.5 思考题

概率计数（思考题 5-1，R. Morris）。 \(b\) 位计数器通常只能计到 \(2^b-1\)。概率计数让计数器值 \(i\) 代表计数 \(n_i\)（递增序列，\(n_0=0\)），每次 INCREMENT 以概率 \(\frac1{n_{i+1}-n_i}\) 把 \(i\) 加 1。每次调用使"代表值"增加的期望恰为 1，所以 \(n\) 次调用后代表值的期望恰为 \(n\)。若 \(n_i=2^{i-1}\)，\(b\) 位就能计到约 \(2^{2^b}\)。若 \(n_i=100i\)，每次增量是"以概率 \(1/100\) 取 100、否则取 0"，方差 \(100^2\cdot\frac1{100}\cdot\frac{99}{100}=99\)，\(n\) 次后方差 \(99n\)。这是流数据近似计数（如 HyperLogLog 等 sketch）的思想源头。

在无序数组中查找（思考题 5-2）。 三种策略的期望检查次数（\(n\) 个元素，目标 \(x\) 出现 \(k\) 次）：

结论是通常选确定性线性查找：简单，\(O(n)\) 有保证；随机查找在目标不存在时反而多出一个 \(\ln n\) 因子。随机化不是万能的。

量化实战：用概率分析建立零假设基准

下面的程序依次演示六件事。

import numpy as np
from collections import Counter
rng = np.random.default_rng(2026)

# 1) 雇用问题 = “创新高”次数。i.i.d. 序列（如日收益）的记录次数期望为 H_n ≈ ln n
n, trials = 2520, 20000
H = np.sum(1 / np.arange(1, n + 1))
def n_records(X):                          # 每行严格创新高的次数（第 1 天算一次）
    return (X == np.maximum.accumulate(X, axis=1)).sum(axis=1)   # 连续分布下无并列
iid  = n_records(rng.standard_normal((trials, n)))              # 日收益本身
walk = n_records(np.cumsum(rng.standard_normal((trials, n)), axis=1))  # 价格 = 收益累加
print(f"H_n={H:.2f}, ln n={np.log(n):.2f} | i.i.d. 收益的记录数均值 {np.mean(iid):.2f}"
      f" | 随机游走价格的新高次数均值 {np.mean(walk):.1f}, 2*sqrt(n/pi)={2*np.sqrt(n/np.pi):.1f}")

# 2) 最长连涨：1000 个交易日、涨跌各半时的最长连续上涨天数
def longest_run(b):
    d = np.diff(np.concatenate(([0], b, [0])))
    s, e = np.flatnonzero(d == 1), np.flatnonzero(d == -1)
    return (e - s).max() if s.size else 0
L = np.array([longest_run(rng.integers(0, 2, 1000)) for _ in range(20000)])
print(f"最长连涨: 均值 {L.mean():.2f}, 中位数 {np.median(L):.0f}, 95% 分位 {np.percentile(L, 95):.0f},"
      f" P(>=20)={np.mean(L >= 20):.4f}  (lg 1000 = {np.log2(1000):.2f})")

# 3) 洗牌算法：Fisher-Yates 正确，PERMUTE-WITH-ALL（练习 5.3-3）有偏
def fisher_yates(a, rng):
    a = a.copy()
    for i in range(len(a) - 1, 0, -1):
        j = rng.integers(0, i + 1)          # 从 a[0..i] 中均匀选一个
        a[i], a[j] = a[j], a[i]
    return a
def permute_with_all(a, rng):
    a = a.copy()
    for i in range(len(a)):
        j = rng.integers(0, len(a))         # 错误：总在整个数组里选
        a[i], a[j] = a[j], a[i]
    return a
base, m = np.arange(3), 60000
for f in (fisher_yates, permute_with_all):
    c = Counter(tuple(f(base, rng)) for _ in range(m))
    freq = np.array([c[k] for k in sorted(c)]) / m
    print(f"{f.__name__:17s}", np.round(freq, 4), " 理论均匀=0.1667")

# 4) 置换检验：因子 IC 是否显著。洗牌打乱因子与收益的对应关系，得到零分布
N = 500
factor = rng.standard_normal(N)
ret = 0.08 * factor + rng.standard_normal(N)
ic = np.corrcoef(factor, ret)[0, 1]
null = np.array([np.corrcoef(rng.permutation(factor), ret)[0, 1] for _ in range(5000)])
print(f"IC={ic:.4f}, 置换检验 p 值={np.mean(np.abs(null) >= abs(ic)):.4f}")

# 5) 多重检验：200 个纯噪声因子里，有多少个 |t|>2
T, K = 250, 200
r = rng.standard_normal(T)
F = rng.standard_normal((T, K))
corr = (F - F.mean(0)).T @ (r - r.mean()) / (T * F.std(0) * r.std())
t = corr * np.sqrt((T - 2) / (1 - corr**2))
print(f"200 个噪声因子中 |t|>2 的个数: {np.sum(np.abs(t) > 2)}（期望约 {K*0.0455:.1f}）")

# 6) 秘书问题：先观察前 k=n/e 个再选第一个超过它们的
def online_max(scores, k):
    best = scores[:k].max()
    for i in range(k, len(scores)):
        if scores[i] > best:
            return i
    return len(scores) - 1
n = 100
for k in (10, 25, 37, 50, 70):
    win = np.mean([(lambda s: s[online_max(s, k)] == s.max())(rng.permutation(n)) for _ in range(20000)])
    print(f"k={k:3d}: 选中最佳者的频率 {win:.3f}")

输出：

H_n=8.41, ln n=7.83 | i.i.d. 收益的记录数均值 8.44 | 随机游走价格的新高次数均值 56.6, 2*sqrt(n/pi)=56.6
最长连涨: 均值 9.30, 中位数 9, 95% 分位 13, P(>=20)=0.0002  (lg 1000 = 9.97)
fisher_yates      [0.1645 0.1678 0.1638 0.1679 0.1674 0.1686]  理论均匀=0.1667
permute_with_all  [0.1473 0.1873 0.1813 0.185  0.149  0.1501]  理论均匀=0.1667
IC=0.0934, 置换检验 p 值=0.0384
200 个噪声因子中 |t|>2 的个数: 8（期望约 9.1）
k= 10: 选中最佳者的频率 0.235
k= 25: 选中最佳者的频率 0.347
k= 37: 选中最佳者的频率 0.373
k= 50: 选中最佳者的频率 0.354
k= 70: 选中最佳者的频率 0.255

白话解释：代码里几处写法可能陌生。np.maximum.accumulate(X, axis=1) 沿每一行计算"到目前为止的最大值"（即历史最高），再和原值比较是否相等，相等的那天就是创新高；(…).sum(axis=1) 按行数出创新高的天数。np.cumsum 把收益累加成价格路径。rng.integers(0, 2, 1000) 生成 1000 个 0/1，模拟涨跌各半。Counter(...) 统计每种排列出现了几次。for i in range(len(a) - 1, 0, -1) 是从后往前的 Fisher–Yates 写法：第 \(i\) 步从 a[0..i] 里随机挑一个换到位置 \(i\)，与正文"从前往后、从 \(A[i..n]\) 里挑"是镜像，同样正确。rng.permutation(factor) 是库函数版的洗牌，置换检验就靠它打乱因子与收益的对应关系。

逐条解读：

1）创新高次数：分清"收益"和"价格"。 雇用问题的 \(H_n\approx\ln n\) 只适用于各期取值可交换（如 i.i.d.）的序列。模拟中 2520 个 i.i.d. 日收益里"当日收益创历史最大"的次数均值为 8.44，与 \(H_{2520}=8.41\) 吻合。但价格是收益的累加，是随机游走，不可交换。随机游走第 \(k\) 步创新高的概率约为 \(\binom{2(k-1)}{k-1}/4^{k-1}\approx1/\sqrt{\pi k}\)（Sparre Andersen 定理的推论），累加得新高次数约 \(2\sqrt{n/\pi}\)，十年约 57 次，比 \(\ln n\) 大得多。用 \(\ln n\) 作为"价格创新高天数"的零假设，会把纯随机游走误判为强趋势。突破类策略的显著性检验要用随机游走的基准，或者直接用模拟。

2）连涨连跌。 1000 个交易日、涨跌概率各半时，最长连涨均值约 9.3 天，与 \(\lg1000\approx10\) 同量级，95% 分位 13 天；出现 20 连涨的频率约 \(0.0002\)，低于原书上界 \(1/1000\)。所以"某股票十年里出现过 10 连涨"不是任何证据，20 连涨才值得注意。真实股票的涨跌概率不一定是一半、各日也不独立，严格的检验应在符合实际的零模型下模拟。

3）洗牌算法。 \(n=3\) 时 PERMUTE-WITH-ALL 的六个排列频率约为 \(4/27=0.148\) 和 \(5/27=0.185\)，与"27 条路径分给 6 个排列"的分析完全一致。Fisher–Yates 均匀。置换检验、bootstrap、随机划分交叉验证都依赖正确的洗牌，自己手写时尤其要小心循环边界；能用库函数（numpy.random.Generator.permutation、shuffle）就用库函数。

4）置换检验。 打乱因子值与收益的对应关系，相当于构造"因子无预测力"的零假设，再看实际 IC 在零分布中的位置。这里真实 IC 约 0.09，\(p\approx0.04\)。它不依赖正态假设，但要求在零假设下样本可交换；时间序列有自相关时，要改用块置换或其他方法（见第 03 册）。

5）多重检验。 200 个与收益完全无关的噪声因子中，有 8 个的 \(|t|>2\)，期望值约 \(200\times0.0455\approx9\)。只要候选够多，"显著"几乎必然出现。这和生日悖论是同一种直觉：在 \(k\) 个候选中寻找巧合，巧合出现的机会按候选对数（\(\binom k2\)）或候选个数增长，远比直觉快。回测里遍历参数网格、因子组合时，必须做多重检验校正，或保留样本外检验。

6）秘书问题。 \(n=100\) 时 \(k=37\approx n/e\) 的成功率约 0.37，\(k\) 偏离后成功率下降，与 \(1/e\) 法则一致。执行算法里的"在一段时间内观察报价、之后接受第一个优于观察期最好价的报价"就是这一类最优停止规则；但它优化的是"选中最好的那个"的概率，而交易执行通常关心期望成交价，两者目标不同，直接套用前要想清楚。

其他对应。

• Floyd 抽样适合从大股票池中无放回地抽少量样本（例如随机抽 50 只股票做稳健性检验）。
• 集券问题告诉你：从 \(b\) 只股票中有放回地随机抽，期望约 \(b\ln b\) 次才能覆盖全部；做 bootstrap 时，一次重抽样约有 \((1-1/n)^n\approx1/e\approx36.8\%\) 的样本没被抽中（练习 5.4-6），这正是 bagging 中"袋外样本"的比例。
• 概率计数思想用于高频行情的近似计数与基数估计，节省内存。

本章小结

概率分析假设输入分布，求平均情况；随机算法在算法内部引入随机性，求期望运行时间，对任何输入都成立，没有固定的坏输入。分析的核心工具是指示器随机变量 \(E[I\{A\}]=\Pr\{A\}\) 与期望的线性性，后者不要求独立。用它们得到：随机顺序下雇用（更新最大值）期望 \(H_n=\ln n+O(1)\) 次；随机排列期望 \(n(n-1)/4\) 个逆序对；生日悖论 \(\Theta(\sqrt n)\)；集券问题 \(b\ln b\)；最长连续正面 \(\Theta(\lg n)\)；秘书问题 \(k=n/e\) 时成功概率至少 \(1/e\)。产生均匀随机排列可以用 PERMUTE-BY-SORTING（\(\Theta(n\lg n)\)）或 Fisher–Yates（\(\Theta(n)\)、原地），证明均匀性不能只看"每个元素落在每个位置的概率为 \(1/n\)"。在量化研究中，这些结论提供零假设基准，但要注意适用条件，例如 \(\ln n\) 适用于收益的创新高、不适用于价格的创新高。

练习

基础

1. 用指示器随机变量求：\(n\) 个骰子点数和的期望；\(n\) 位顾客随机拿回帽子时，期望拿到自己帽子的人数。 答案：\(3.5n\)；1。
2. 设 \(A\) 是 \(\langle1,\dots,n\rangle\) 的均匀随机排列，求期望逆序对数，并说明它对插入排序平均运行时间意味着什么。 答案：\(n(n-1)/4\)；平均仍为 \(\Theta(n^2)\)。
3. 随机顺序下，HIRE-ASSISTANT 恰好雇用 1 次、恰好 \(n\) 次、恰好 2 次的概率各是多少？ 答案：\(1/n\)；\(1/n!\)；\(H_{n-1}/n\)。
4. 说明为什么"与 A[RANDOM(1, n)] 交换"的洗牌不均匀，并用 \(n=3\) 列出每个排列出现的路径数。 答案：27 条路径，三个排列各 5 条、三个各 4 条。
5. 至少多少人才能使有人与你同生日的概率不低于 1/2？ 答案：\(1-(364/365)^k\ge1/2\)，\(k=253\)。
6. 用 RANDOM(0,1) 实现 RANDOM(a,b)，给出期望运行时间；用一个有偏硬币产生无偏比特。

进阶

7. 证明 Floyd 抽样 RANDOM-SAMPLE\((m,n)\) 产生均匀随机的 \(m\) 元子集。 提示：对 \(m\) 归纳，证明每个 \(m\) 子集出现的概率为 \(1/\binom nm\)。
8. \(n\) 个球随机投入 \(n\) 个箱子，求期望空箱数和恰有一个球的箱子数。据此解释 bootstrap 中"约 36.8% 样本不被抽中"。 答案：两者都是约 \(n/e\)。
9. 某策略在 2520 个交易日内出现了 70 次"净值创历史新高"。分别以"i.i.d. 收益"与"零漂移随机游走净值"为零假设，这个数字是否异常？应如何更严格地检验？ 提示：i.i.d. 基准约 \(H_n\approx8\)，但这不是净值的正确基准；随机游走基准约 \(2\sqrt{n/\pi}\approx57\)，70 次并不罕见。严格做法是在估计出的波动率下模拟零漂移净值，得到新高次数的经验分布。
10. 思考题 5-1：取 \(n_i=100i\)，求 \(n\) 次 INCREMENT 后代表值的期望与方差。 答案：期望 \(n\)，方差 \(99n\)。

原书推荐习题：5.2-4（帽子问题）、5.2-5（期望逆序对数），指示器变量的基本功；5.3-2、5.3-3、5.3-4（辨析错误的洗牌，实务中极易犯）；5.3-7（Floyd 抽样）；5.1-3（von Neumann 去偏）；5.4-6（\(n\) 球 \(n\) 箱的期望空箱数）；思考题 5-1（概率计数）、5-2（随机与确定性查找的期望分析）。

原书对照

章末注记（PDF p.166）推荐 Motwani 与 Raghavan 的《Randomized Algorithms》作为随机算法的系统参考；雇用问题的变体在文献中称为"秘书问题"。