Probability & Stochastic Process 面试题全集

来源：Two Sigma 面经（192条）+ Citadel 面经（244条）+ 绿皮书（Chapter 4 Probability Theory + Chapter 5 Stochastic Process and Stochastic Calculus）

（共 70 道题，11 大分类，覆盖概率论与随机过程全部核心内容。Brain Teasers 和博弈论部分见 Brain_Teasers.md。）

频率标准：

• ⭐⭐⭐⭐⭐：必考核心题，多家公司反复出现（5+ 次），面试重中之重
• ⭐⭐⭐⭐：高频题，经常出现在面试中（3-4 次）
• ⭐⭐⭐：中频题，多次出现或作为重要知识点（2-3 次）
• ⭐⭐：偶尔出现或作为追问
• ⭐：罕见但可能出现，或作为加分题

0. 刷题优先级清单（2026-04-30 整理）

排序原则：频率（⭐）+ Two Sigma 面经命中度 + 已深化情况。

已深化的 5 题（仅做周复盘，不重复深挖）：Q25 Pólya 壶 / Q28 相关系数矩阵 / Q29 间距法 / Q31 Poisson + Exp(λ) / Q35 Coupon Collector。

Tier S（必做核心 15 题，⭐⭐⭐⭐⭐ + Two Sigma 高频）

Tier A（巩固扩展 20 题，⭐⭐⭐⭐）

Tier B（中频 21 题，⭐⭐⭐）

Tier C（低频补充 9 题，⭐⭐）

执行节奏

• Tier S 优先一周内全部过完（每天 2-3 题），是 Two Sigma 面试硬通货
• Tier A 用 Phase 1B（5/7 - 5/31 回国维持期）完成
• Tier B / C 留到 Phase 2 上班后

recall 钩子（每题做完必填）

1. 这题考的”工具”是什么？（对称性 / Indicator / 状态方程 / Bayes / 鞅 OST / 反射原理 / Order stat 公式 / Cholesky …）
2. 哪一步是”看到答案才反应过来”的？这就是 recall 缺口，写 Anki 卡。
3. 30 秒内能不能口述思路？

一、基础概率与集合运算

知识点

Outcome（结果）： 一次实验的结果。掷骰子得到 3 就是一个 outcome。

Sample Space $\Omega$（样本空间）： 所有可能结果的集合。掷骰子的 $\Omega = {1,2,3,4,5,6}$。

Event（事件）： 样本空间的子集。”掷到偶数” = ${2,4,6}$。

概率公理：

• $P(\omega) \geq 0$
• $\sum_{\omega \in \Omega} P(\omega) = 1$
• $P(A) = \sum_{\omega \in A} P(\omega)$

互斥事件（Mutually Exclusive）： $A \cap B = \emptyset$，不能同时发生。 \(P(A \cup B) = P(A) + P(B)\)

独立事件（Independent）： 一个不影响另一个。 \(P(A \cap B) = P(A) \times P(B)\)

容斥原理（Inclusion-Exclusion）： \(P(A \cup B) = P(A) + P(B) - P(A \cap B)\)

三个事件： \(P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(AB) - P(AC) - P(BC) + P(ABC)\)

Indicator Variable（指示变量）： $I_A = 1$ if A occurs, $I_A = 0$ otherwise. $E[I_A] = P(A)$. 在用 Linearity of Expectation 时非常有用。

例题

题目1：Coin Toss Game（硬币对比）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.1

A 有 $n+1$ 枚公平硬币，B 有 $n$ 枚。两人同时全部抛。A 的正面数比 B 多的概率？

答案： $1/2$

解法（绿皮书）：

关键思路：把 A 的 $n+1$ 枚硬币拆成两部分——前 $n$ 枚和最后 1 枚。

前 $n$ 枚和 B 的 $n$ 枚完全对称，三种情况：

• $E_1$: A 的前 $n$ 枚正面数 > B 的 $n$ 枚（概率 $x$）
• $E_2$: A 的前 $n$ 枚正面数 = B 的 $n$ 枚（概率 $y$）
• $E_3$: A 的前 $n$ 枚正面数 < B 的 $n$ 枚（概率 $x$，和 $E_1$ 对称）

所以 $2x + y = 1$。

现在把 A 多出的那枚硬币加回来（正面概率 1/2）：

代入 $2x + y = 1$，即 $y = 1 - 2x$：

$x$ 消掉了！不管 $n$ 多大，答案都是 $1/2$。

直觉： 前 $n$ 枚硬币的对决完全公平——”领先必赢”和”落后必输”因对称性恰好抵消，只剩下”平局时靠多出的那枚硬币决定”，而那枚硬币正面概率恰好是 $1/2$。

题目2：Card Game（牌面比大小）⭐⭐ ↑ 返回 list

来源： 绿皮书 4.1

52 张牌，你和庄家各抽一张（无放回）。你的牌面更大就赢（相等或更小就输）。赢的概率？

答案： $8/17$

解法（绿皮书）：

方法一（暴力枚举）： 你的牌有 13 种面值（2 到 A），每种概率 $1/13$。

• 你抽到 2：庄家 51 张牌中 0 张比你小 → $P(\text{赢}) = 0/51$
• 你抽到 3：庄家 51 张牌中 4 张比你小 → $P(\text{赢}) = 4/51$
• 你抽到 4：$P = 8/51$
• …
• 你抽到 A：$P = 48/51$

总概率 = $\frac{1}{13} \times \frac{4}{13 \times 51} \times (0 + 4 + 8 + \cdots + 48) = \frac{4}{13 \times 51} \times \frac{12 \times 13}{2} = \frac{4 \times 78}{13 \times 51} = \frac{312}{663} = \frac{8}{17}$

方法二（对称法，更快）： 三种情况：你赢、平、你输。

• $P(\text{平}) = 3/51$（你的牌确定后，剩 51 张里 3 张和你面值相同）
• 赢和输完全对称（交换你和庄家的视角）
• 所以 $P(\text{赢}) = P(\text{输}) = (1 - 3/51)/2 = 48/102 = 8/17$

题目3：Drunk Passenger（醉汉乘客）⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.1 + Citadel 面经

100 个乘客登机，每人有指定座位。第 1 个人醉了随机选座。之后每人：自己座位空就坐，不空就随机选一个空座。第 100 个人坐到自己座位的概率？

答案： $1/2$

解法（绿皮书）：

核心观察： 在整个过程中，只有两个座位的命运是始终不确定的——座位 #1（醉汉的座位）和座位 #100（最后一人的座位）。

为什么中间座位的命运是确定的？ 任何一个中间座位（比如 #50），在它的主人（#50 号乘客）登机的那一刻就彻底定格：

• 如果 #50 空着 → 主人直接坐，座位定格为”#50 本人坐在这”
• 如果 #50 被占了 → 占座人已经确定，座位定格为”那个早登机的人坐在这”

一旦主人登机，#50 这个座位就不再空着，后面的人不可能再选中 #50。所以中间座位”暴露在风险中”的时间是有限的，主人一到就结束。

为什么 #1 和 #100 的命运始终不确定？

• #1：它的”主人”是醉汉，而醉汉是随机选座不是自愿坐回 #1，所以 #1 没有保护者。从第 2 个人到第 99 个人，任何一个被迫随机选座的人都可能选中 #1。
• #100：它的”主人”是最后一个乘客，但他最后才登机，在他到达之前的 99 轮里，#100 始终暴露在被选走的风险中。

游戏的胜负 = #1 和 #100 谁先被选中：

• 如果 #1 先被选 → 链条闭合，后面所有人坐自己的位置（#100 赢）
• 如果 #100 先被选 → #100 的座位没了（#100 输）

为什么概率是 1/2？ 每次有人被迫随机选座时，他面前的空座里一定同时包含 #1 和 #100（如果其中任何一个已经被选走，游戏早结束了）。在所有空座中，#1 和 #100 的地位完全对称——没有任何理由偏向某一个，所以每次被选中的概率始终相等。

所以最终，#1 先被选走和 #100 先被选走的概率相等 = $1/2$。

用小例子验证（2 个乘客）：

• 醉汉选到座位 #1（概率 1/2）→ #2 坐自己座位 ✅
• 醉汉选到座位 #2（概率 1/2）→ #2 坐不到 ❌

$P = 1/2$ ✓

用 3 个乘客验证：

• 醉汉选座位 #1（1/3）→ 所有人正常 → #3 坐到 ✅
• 醉汉选座位 #2（1/3）→ #2 来了发现被占，随机选 #1 或 #3
  • 选 #1（1/2）→ #3 坐到 ✅
  • 选 #3（1/2）→ #3 坐不到 ❌
• 醉汉选座位 #3（1/3）→ #2 正常坐 #2 → #3 坐不到 ❌

$P = 1/3 + 1/3 \times 1/2 = 1/3 + 1/6 = 1/2$ ✓

题目4：N Points on a Circle ⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.1 + Citadel 面经

$N$ 个点均匀随机放在圆上。全部落在同一个半圆内的概率？

答案： $N / 2^{N-1}$

解法（绿皮书）：

第一步：定义事件。 给 $N$ 个点编号 $1, 2, \ldots, N$。定义事件 $E_i$ = “以点 $i$ 为起点的顺时针半圆包含所有其他点”。

第二步：算单个事件的概率。 固定点 $i$ 的位置，其余 $N-1$ 个点各自独立均匀分布在圆上。每个点落在 $i$ 的顺时针半圆内的概率 = $1/2$。$N-1$ 个点全在里面的概率 = $(1/2)^{N-1} = 1/2^{N-1}$。

第三步：证明这些事件互斥。 为什么 $E_i$ 和 $E_j$（$i \neq j$）不能同时发生？

假设 $E_i$ 发生，即所有点在以 $i$ 为起点的半圆内。如果 $E_j$ 也发生，所有点也在以 $j$ 为起点的半圆内。两个半圆的交集比半圆小（除非 $i = j$），所以不可能同时容纳所有点。

更严格地说（绿皮书证明）：如果从点 $i$ 出发顺时针走，依次经过 $i+1, i+2, \ldots, N, 1, \ldots, i-1$，要让所有点在 $i$ 的半圆内，从 $i-1$ 到 $i$ 的弧必须 $\geq$ 半圆。这意味着从任何其他点出发的半圆都不能包含所有点。

第四步：求总概率。 $N$ 个互斥事件，每个概率 $1/2^{N-1}$： \(P = N \times \frac{1}{2^{N-1}} = \frac{N}{2^{N-1}}\)

推广（绿皮书）： 如果弧长占圆周的比例为 $x$（$x \leq 1/2$），则 $N$ 个点全在弧内的概率 = $N \times x^{N-1}$。

二、组合分析（Combinatorial Analysis）

知识点

排列（Permutation）—— “选了之后排队”

核心直觉： 一个一个选，每选一个可选的人就少一个。

10 个人选 3 个站一排（第一名、第二名、第三名）：

• 第一名：10 个人可选
• 第二名：剩 9 个
• 第三名：剩 8 个
• 总数 = $10 \times 9 \times 8$

这就是排列公式的本质： \(P(n,k) = \underbrace{n \times (n-1) \times \cdots \times (n-k+1)}_{k \text{ 个数相乘}} = \frac{n!}{(n-k)!}\)

不用记 $(n-k)!$，就记”从 $n$ 开始连乘 $k$ 个递减的数”。

有重复元素的排列： “MISSISSIPPI” 有多少种排法？

11 个字母全排列是 $11!$，但相同字母交换位置算同一种。4 个 S 互换有 $4!$ 种、4 个 I 互换有 $4!$ 种、2 个 P 互换有 $2!$ 种——全是重复计数，除掉： \(\frac{11!}{4! \cdot 4! \cdot 2! \cdot 1!}\)

直觉： 分子是”假装全不同”的排法数，分母除掉”同类互换”的重复。

组合（Combination）—— “只选不排”

核心直觉： 组合 = 排列 ÷ “选出来之后的排队方式”。

10 个人选 3 个组队（不分谁第一第二第三）：

• 排列：$10 \times 9 \times 8 = 720$（有顺序）
• 但 ABC、ACB、BAC、BCA、CAB、CBA 算同一个队 → 每队被数了 $3! = 6$ 次
• 组合 = $720 / 6 = 120$

不用记 $\frac{n!}{k!(n-k)!}$，就记”排列除以 $k!$”——排列管选和排，除以 $k!$ 去掉排的部分。

快速验算： $\binom{n}{k} = \binom{n}{n-k}$。选 3 个人 = 决定哪 7 个人不选。如果你算出 $\binom{10}{3} \neq \binom{10}{7}$，说明算错了。

什么时候用排列，什么时候用组合？

一句话判断： 交换选出来的元素，结果变了吗？

• 变了 → 排列（密码锁 123 ≠ 321，选队长+副队长）
• 没变 → 组合（选委员会、抽扑克牌）

隔板法（Stars and Bars）—— “把东西分到盒子里”

$n$ 个相同球放进 $k$ 个不同盒子（每个盒子可以为空）：

想象 $n$ 个球排成一排，中间和两边的空隙用 $k-1$ 个隔板分隔成 $k$ 段： \(\binom{n+k-1}{k-1}\)

例子： 10 块糖分给 3 个小孩 = 在 12 个位置中选 2 个放隔板 = $\binom{12}{2} = 66$。

二项式定理

直觉： $(x+y)^n$ 展开就是从 $n$ 个括号里各选一个（$x$ 或 $y$），所有可能的乘积之和。选了 $k$ 个 $x$ 和 $n-k$ 个 $y$ 的方式有 $\binom{n}{k}$ 种。

最常用的推论： 令 $x = y = 1$：$2^n = \sum \binom{n}{k}$（$n$ 个元素的子集总数是 $2^n$）。

容斥原理 —— “加回来多减的”

直觉： 先把每个事件的概率加起来（但重叠区域多算了），减去两两重叠（但三个都重叠的地方又被多减了），再加回三三重叠……交替加减直到没有遗漏。

两个事件记住就够了： $P(A \cup B) = P(A) + P(B) - P(AB)$。三个以上事件的容斥在面试中极少直接计算，但”反面计数”（$P(\text{至少一个}) = 1 - P(\text{一个都没有})$）非常常用。

例题

题目5：Poker Hands（扑克牌型概率）⭐⭐ ↑ 返回 list

来源： 绿皮书 4.2

52 张标准扑克牌（4 花色 × 13 面值），随机抽 5 张。求以下牌型的概率。

总手牌数： $\binom{52}{5} = 2,598,960$

解法（逐个牌型计数）：

Four-of-a-kind（四条）： 4 张同面值 + 1 张其他。

• 选哪个面值做四条：$13$ 种
• 第 5 张从剩余 48 张中选：$48$ 种
• 总数 = $13 \times 48 = 624$
• 概率 = $624 / 2,598,960 \approx 0.024\%$

Full House（葫芦）： 3 张同面值 + 2 张另一面值。

• 选三条的面值：$13$ 种，从 4 张中选 3 张：$\binom{4}{3} = 4$
• 选对子的面值：剩余 $12$ 种，从 4 张中选 2 张：$\binom{4}{2} = 6$
• 总数 = $13 \times 4 \times 12 \times 6 = 3,744$
• 概率 = $3,744 / 2,598,960 \approx 0.144\%$

Two Pairs（两对）： 2 张面值 A + 2 张面值 B + 1 张面值 C。

• 选哪两个面值做对子：$\binom{13}{2} = 78$（用组合不用排列，因为两对没有先后）
• 每对从 4 张中选 2 张：$\binom{4}{2} \times \binom{4}{2} = 36$
• 第 5 张从剩余 $52 - 8 = 44$ 张中选：$44$
• 总数 = $78 \times 36 \times 44 = 123,552$（但要注意这 44 张不能和两个对子同面值，$52 - 4 \times 2 = 44$ ✓）
• 概率 = $123,552 / 2,598,960 \approx 4.75\%$

Flush（同花）： 5 张同花色（不含同花顺）。

• 选花色：$4$ 种
• 从 13 张中选 5 张：$\binom{13}{5} = 1,287$
• 减去同花顺（每花色 10 个：A-5, 2-6, …, 10-A）：$-10$
• 总数 = $4 \times (1,287 - 10) = 5,108$
• 概率 $\approx 0.197\%$

Straight（顺子，不含同花顺）： 5 张连续面值。

• 起始面值 10 种（A-5, 2-6, …, 10-A）
• 每张 4 种花色选择：$4^5 = 1,024$
• 减去同花顺：$-4$（每个起始值恰好 4 个同花顺）
• 总数 = $10 \times (1,024 - 4) = 10,200$
• 概率 $\approx 0.392\%$

面试中说： “Poker hands 的关键是分步计数——先选面值再选花色。最容易出错的是 Two Pairs，要用 $\binom{13}{2}$ 而不是 $13 \times 12$，因为两个对子之间没有先后顺序。另一个易错点是 Flush 和 Straight 要减去同花顺，避免重复计数。”

题目6：Hopping Rabbit（兔子跳楼梯）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.2

兔子在 $n$ 级楼梯底部，每次跳 1 级或 2 级。有多少种方式跳到顶？

答案： $f(n) = f(n-1) + f(n-2)$，$f(1) = 1$，$f(2) = 2$。就是 Fibonacci 数列。

解法（绿皮书）：

从最简单的情况开始：

• $n = 1$：只能跳 1 级 → $f(1) = 1$
• $n = 2$：可以跳 1+1 或直接跳 2 → $f(2) = 2$

对于 $n > 2$，兔子最后一步要么跳 1 级（从 $n-1$ 级上来），要么跳 2 级（从 $n-2$ 级上来）： \(f(n) = f(n-1) + f(n-2)\)

这就是 Fibonacci 数列。这也是 coding 里”爬楼梯”那道 DP 题的原型。

解法 2（组合方法验证）：

如果兔子跳了 $a$ 次 1 级 和 $b$ 次 2 级，必须满足： \(a + 2b = n\)

给定 $(a, b)$，这 $a+b$ 次跳跃中哪几次是 2 级跳可以任意安排 → 方式数 $= \binom{a+b}{b}$。

所有可能的 $(a, b)$ 求和： \(f(n) = \sum_{b=0}^{\lfloor n/2 \rfloor} \binom{n-b}{b}\)

验证 $n=5$：

• $b=0$：$(a,b)=(5,0)$，$\binom{5}{0}=1$
• $b=1$：$(a,b)=(3,1)$，$\binom{4}{1}=4$
• $b=2$：$(a,b)=(1,2)$，$\binom{3}{2}=3$
• 合计 $= 1 + 4 + 3 = 8$ ✓

两种方法对照：

闭式解（Binet 公式）：

其中 $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$（黄金比），$\psi = \frac{1-\sqrt{5}}{2} \approx -0.618$。

面试一般不用推这个，但可以提一句”Fibonacci 有闭式解，通过特征方程 $x^2 = x + 1$ 得出”。

变种 1：每次可跳 1、2 或 3 级

最后一步的可能性多一个： \(f(n) = f(n-1) + f(n-2) + f(n-3)\)

$f(1)=1$，$f(2)=2$，$f(3)=4$。这是 Tribonacci 数列。

变种 2：最多跳 $k$ 级

变种 3（Citadel 面经，期望版）：

兔子每次以概率 $p$ 跳 1 级，$1-p$ 跳 2 级。求到达第 $n$ 级的期望跳数 $E[T_n]$。

思路（一步分析）：

边界：$E[T_0] = 0$，$E[T_1] = 1$（只能跳 1 级，花 1 步）。

Wald 式快速解法：

设兔子每跳一次的期望上升级数 $= p \cdot 1 + (1-p) \cdot 2 = 2 - p$。

由更新理论（大数律），长期看： \(E[T_n] \approx \frac{n}{2 - p}\)

（这是近似，精确值需解递推。但面试中这个估算就够了。）

验证极端情况：

• $p = 1$（只跳 1 级）：$E[T_n] = n$ ✓
• $p = 0$（只跳 2 级）：$E[T_n] = n/2$ ✓（假设 $n$ 是偶数）

题目7：Application Letters / Derangement（错位排列）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.2 + Citadel 面经

5 封信随机放入 5 个信封，全部放错的概率？

答案： $11/30 \approx 0.367$

解法（绿皮书，用容斥原理）：

直接算”全放错”很难，反过来算”至少一封放对”更容易。

定义 $E_i$ = 第 $i$ 封信放对了。我们要算 $P(\text{全错}) = 1 - P(\text{至少一封对}) = 1 - P(E_1 \cup E_2 \cup \cdots \cup E_5)$。

容斥原理说：先全加，再减两两重叠，再加三三重叠……交替加减：

逐层计算：

第一层 $\sum P(E_i)$： 固定 1 封放对，其余随便。$P(E_i) = 1/5$。共 $\binom{5}{1} = 5$ 项。 \(\sum = 5 \times \frac{1}{5} = 1\)

⚠️ 为什么是 $\frac{1}{5} \times \frac{1}{4}$ 而不是 $\frac{1}{5} \times \frac{1}{5}$？

因为这是排列（5 封信进 5 个信封，不能重复），不是独立放置。每占一个信封，剩下的选择就少一个 → “缩小的世界”。

• 独立放置（可重复）：$1/5 \times 1/5$
• 排列（不可重复）：$1/5 \times 1/4$

判断方法：占用后别人还能占吗？不能 → 排列。

从分母看： 总情况数 $= 5! = 120$。两封都对的情况 $= 3!= 6$（其余 3 封随便排）。$P = 6/120 = 1/20 = \frac{1}{5 \times 4}$ ✓

乘法规则看： $P(E_j \mid E_i) = 1/4$，因为已知第 $i$ 封占了位置，只剩 4 个信封给其他信。

第二层 $\sum P(E_iE_j)$： 固定 2 封都放对。第一封对的概率 $1/5$，条件下第二封对 $1/4$。$P = \frac{1}{5} \times \frac{1}{4} = \frac{1}{20}$。共 $\binom{5}{2} = 10$ 项。 \(\sum = 10 \times \frac{1}{20} = \frac{1}{2} = \frac{1}{2!}\)

第三层 $\sum P(E_iE_jE_k)$： 固定 3 封都对。$P = \frac{1}{5} \times \frac{1}{4} \times \frac{1}{3} = \frac{1}{60}$。共 $\binom{5}{3} = 10$ 项。 \(\sum = 10 \times \frac{1}{60} = \frac{1}{6} = \frac{1}{3!}\)

第四层： $P = \frac{1}{5!/(5-4)!} = \frac{1}{120}$。共 $\binom{5}{4} = 5$ 项。$\sum = 5 \times \frac{1}{120} = \frac{1}{24} = \frac{1}{4!}$

第五层： 5 封全对。$P = \frac{1}{5!} = \frac{1}{120}$。共 1 项。$\sum = \frac{1}{5!}$

为什么每层都恰好化简成 $\frac{1}{k!}$？详细推导：

对于 $N$ 封信，容斥公式的第 $k$ 层是：

求和范围是所有从 $N$ 封信中选出 $k$ 封的组合，共 $\binom{N}{k}$ 项。

Step 1：算单项概率。

“$k$ 封信都放对”意思是这 $k$ 封各自回到自己的信封，剩下 $N-k$ 封可以随便排。

用分子/分母的视角：

• 分母：$N$ 封信的总排列数 = $N!$
• 分子：$k$ 封固定在对的位置，剩下 $N-k$ 封随便排 = $(N-k)!$

用乘法规则验证（跟前面 $\frac{1}{5} \times \frac{1}{4}$ 同一思路）： \(P = \frac{1}{N} \times \frac{1}{N-1} \times \cdots \times \frac{1}{N-k+1} = \frac{(N-k)!}{N!} ✓\)

Step 2：乘上项数 $\binom{N}{k}$。

Step 3：展开组合数并约分。

所以：

$N!$ 和 $(N-k)!$ 都约掉了，只剩 $1/k!$。

直觉理解： $\binom{N}{k}$（项数）和单项概率 $\frac{(N-k)!}{N!}$ 是一对”互补”的量——项数越多，单项概率越小，两者乘积恰好消掉 $N$，只留下 $k!$。这也是为什么容斥结果 $1 - 1/2! + 1/3! - \cdots$ 和 $N$ 无关（除了项数）—— $N$ 全部约掉了。

所以 $N$ 再大，错排概率都趋近 $1/e$——这是一个非常漂亮的数学结果。

代入容斥（交替加减）： \(P(\text{至少一封对}) = 1 - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + \frac{1}{5!} = 1 - 0.5 + 0.167 - 0.042 + 0.008 = \frac{19}{30}\)

一般化： $N$ 封信全放错的概率 = $\sum_{k=0}^{N} \frac{(-1)^k}{k!} \approx 1/e \approx 0.368$。不管 $N$ 多大，这个概率几乎不变！

题目8：Birthday Problem（生日问题）⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.2 + Two Sigma + Citadel

房间里多少人才能使至少两人同天生日的概率 > 50%？（假设 365 天等概率，忽略闰年）

答案： 23 人

解法（反面计数 —— 算”全不同”更容易）：

直接算”至少两人相同”很复杂（可能恰好 2 人同天、3 人同天、两组同天……），反过来算”所有人生日都不同”只有一种情况。

Step 1：$P(\text{全不同})$ 怎么算？

一个一个人进房间：

• 第 1 个人：随便哪天都行 → $365/365$
• 第 2 个人：要避开第 1 个人的生日 → $364/365$
• 第 3 个人：要避开前 2 个人 → $363/365$
• ……
• 第 $n$ 个人：要避开前 $n-1$ 个人 → $(365 - n + 1)/365$

⚠️ 理解分子和分母：为什么不是 $(1/365)^n$？

回到概率的基本定义：

\[P(\text{事件}) = \frac{\text{满足事件的可能情况数}}{\text{所有可能情况数}}\]

• 分母：总共有多少种可能的结果（样本空间大小）
• 分子：其中有多少种满足我们要的事件

对于”$n$ 个人每人有一个生日”这件事，每个人有 365 种可能，$n$ 个人的总可能性 = $365^n$。分母永远是 $365^n$，这个不变。

真正会变的是分子——也就是”满足事件的情况数”。分子取决于你要算的是什么事件：

事件	分子是什么	分子的值
$n$ 个人都在 1月1日生日	每个人只有 1 种选择（必须是 1月1日）→ 1×1×…×1	$1$
$n$ 个人生日全不同	第 1 人 365 种、第 2 人 364 种、…、第 $n$ 人 $(365-n+1)$ 种	$365 \times 364 \times \cdots \times (365-n+1)$
两人生日相同（某一天）	指定一天，每人 1 种选择 → $1 \times 1 = 1$	$1$
两人生日相同（任何一天都行）	日期可以是 365 天中任意一天 → $365 \times 1 \times 1$	$365$

所以：

• $(1/365)^n = \frac{1^n}{365^n}$ —— 分子是 1，意思是”每个人必须落在某个指定好的一天”
• $\frac{365 \times 364 \times \cdots}{365^n}$ —— 分子递减，意思是”每个人只要和之前的人不同就行，不限定具体哪一天”

一句话：分子的大小 = 你允许的情况数。指定越严（只能是某天）分子越小；限制越松（任何一天都行）分子越大。

用 2 个人完整验证：

• $P(\text{都在 1月1日}) = \frac{1 \times 1}{365^2} = \frac{1}{365^2}$
• $P(\text{同天，任何一天}) = \frac{365 \times 1}{365^2} = \frac{1}{365}$（365 种可能的”那一天”）
• $P(\text{生日不同}) = \frac{365 \times 364}{365^2} = \frac{364}{365}$（第 1 人随便，第 2 人要避开）

全部加起来：$\frac{1}{365} + \frac{364}{365} = 1$ ✓（要么同天要么不同天，没有第三种）

这道题问”全不同”，所以分子是 $365 \times 364 \times \cdots$。

Step 2：逐步计算。

Step 3：为什么 23 这么小？—— 核心直觉：配对数

本质理解：生日问题 = 配对数达到 253 就够了。

要让”碰撞概率 > 50%”，只需要大约 253 对独立的”碰撞机会”。怎么凑出这 253 对不重要，关键是配对数本身。

• 23 人之间有 $\binom{23}{2} = 253$ 对 → 任意两人同天 > 50% ✓
• 253 人每人和你比较，有 253 对 → 有人和你同天 > 50% ✓

两种情况配对数都是 253，所以答案都能达到 50%。只不过前者用更少的人（23）制造了同样多的配对——因为组合数是平方级增长的，$\binom{n}{2} \approx n^2/2$。

反直觉的根源： 很多人直觉觉得应该是 183（365 的一半），但 183 是朴素的错误猜测。正确的思考不是”$n$ 个人 vs 365 天”，而是”$\binom{n}{2}$ 对 vs 365 天”。

⚠️ 三种”生日问题”的对比

问题	答案	配对数	公式
房间里任意两人同天 $> 50\%$？（原题）	23 人	$\binom{23}{2} = 253$	$1 - \frac{365 \cdot 364 \cdots}{365^n} > 0.5$
房间里有人和你（指定日期）同天 $> 50\%$？	253 人	$253$	$1 - (364/365)^n > 0.5$
朴素猜测（365 的一半）	183（错）	—	—

注意到了吗？ 两个答案的”配对数”都是 253，这不是巧合——正因为配对数相同，两个问题才在同一个临界点达到 50%。

第二个问题的推导： 若你生日是 1月1日，则 $P(\text{某人不是 1月1日}) = 364/365$。$n$ 人独立全不是 1月1日的概率 $= (364/365)^n$。要求 $1 - (364/365)^n > 0.5$，解出 $n > 365 \ln 2 \approx 253$。

为什么配对数是 253？$\ln 2$ 是怎么冒出来的？

253 不是魔术数字，来自公式 $N \ln 2$（$N = 365$ 是总天数）：

\[253 \approx 365 \times \ln 2 \approx 365 \times 0.693\]

推导： 设有 $k$ 对独立的”碰撞机会”，每对同天概率 $= 1/365$。所有对都不同天的概率：

\[P(\text{无碰撞}) = \left(1 - \frac{1}{365}\right)^k \approx e^{-k/365}\]

要让这个降到 $1/2$：

\[e^{-k/365} = 0.5 \Rightarrow k = 365 \ln 2 \approx 253\]

直觉： $\ln 2$ 出现是因为”让概率降一半”这个要求。就像放射性衰变的”半衰期”——要衰减到一半，时间常数里天然会出现 $\ln 2$。

推广公式：$n \approx 1.18\sqrt{N}$

对于任意总天数 $N$，”任意两人同天 > 50%” 需要 $n \approx \sqrt{2N \ln 2} \approx 1.18\sqrt{N}$ 人。

推导： 配对数 $\binom{n}{2} \approx n^2/2 = N \ln 2$，解出 $n \approx \sqrt{2N \ln 2}$。

根号是怎么来的？ 因为 $n$ 人的配对数是 $n^2/2$ 级别（平方增长），要让配对数达到 $N \ln 2$，$n$ 只需 $\sqrt{N}$ 级别。

总天数 $N$	需要的配对数 $N \ln 2$	需要的人数 $1.18\sqrt{N}$
100	69	12
365	253	23
1000	693	37
10000	6931	118

近似公式的严谨推导（用 $1 - x \approx e^{-x}$）：

令 $P = 0.5$：$n(n-1)/2 \approx 365 \ln 2 \approx 253$，解出 $n \approx 23$。

面试一句话总结： “核心是配对数。要让碰撞概率 > 50%，需要 $N \ln 2 \approx 253$ 对。$n$ 人之间有 $\binom{n}{2} \approx n^2/2$ 对，让它等于 253 得 $n \approx 23$。推广公式 $n \approx 1.18\sqrt{N}$。”

面试中说： “反面计数——算全不同的概率更容易。每个人的生日要避开前面所有人，所以是 $365/365 \times 364/365 \times \cdots$。23 人看起来少，但关键是任意两人配对数 $\binom{23}{2} = 253$ 很大，每一对都是一次碰撞机会。”

变种（绿皮书 Birthday Line）： 电影院排队，第一个和前面某人同天生日的人免费。你排第几最优？

答案： 第 20 个。

解法思路：

设你排第 $k$ 位。你免费的条件：

1. 前 $k-1$ 个人的生日全不同（否则别人先中奖了）
2. 你的生日和前面某人相同

第一项随 $k$ 递减（前面人越多越难全不同），第二项随 $k$ 递增（前面人越多你越容易撞上）。两者的乘积在 $k = 20$ 时取最大值（$\approx 3.23\%$）。

题目9：Chess Tournament（淘汰赛）⭐⭐ ↑ 返回 list

来源： 绿皮书 4.2

$2^n$ 个选手淘汰赛（随机分组），实力排名 $1 > 2 > \cdots > 2^n$，强者必赢。选手 1 和 2 在决赛相遇的概率？

答案： $\frac{2^{n-1}}{2^n - 1}$

解法（绿皮书）：

选手 1 是最强的，不管在哪个半区都会赢到决赛。

问题变成：选手 2 能不能也赢到决赛？选手 2 赢到决赛的条件是：他和选手 1 不在同一半区（因为同一半区会提前相遇，选手 2 会输）。

淘汰赛把 $2^n$ 个选手分成两个 $2^{n-1}$ 人的半区。选手 1 在某个半区，剩下 $2^n - 1$ 个选手中，选手 2 在另一半区的概率：

分母是 $2^n - 1$（除了选手 1 的所有人），分子是 $2^{n-1}$（另一半区的人数）。

验证 $n = 1$（2 个选手）： $P = 1/1 = 1$。只有两个人，必然在决赛相遇 ✓

验证 $n = 2$（4 个选手）： $P = 2/3$。4 个人分成两组各 2 人，选手 2 和选手 1 不同组的概率 = 2/3 ✓

题目10：100! 的尾零 ⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 2.2 + Citadel 面经

$100!$（100 的阶乘）末尾有多少个零？

答案： 24

解法（质因数分解思路）：

Step 1：尾零从哪来？

每一个尾零 = 乘积里多了一个因子 10。而 $10 = 2 \times 5$。所以每一对（因子 2 + 因子 5）贡献一个尾零。

Step 2：哪个更少？

$100!$ 里因子 2 的来源：2, 4, 6, 8, 10, 12, … 每隔一个数就有一个，非常多。 因子 5 的来源：5, 10, 15, 20, 25, 30, … 少得多。

所以 因子 5 是瓶颈——有多少个因子 5，就有多少个尾零。

Step 3：数因子 5。

• 5 的倍数：$5, 10, 15, 20, 25, 30, \ldots, 100$ → 每个贡献至少 1 个因子 5 → $\lfloor 100/5 \rfloor = 20$ 个
• 25 的倍数：$25, 50, 75, 100$ → 每个额外贡献 1 个因子 5（因为 $25 = 5^2$）→ $\lfloor 100/25 \rfloor = 4$ 个
• 125 的倍数：$125 > 100$ → 0 个

验证直觉： 25 = 5×5 贡献了 2 个因子 5，50 = 2×5×5 也贡献了 2 个。上面第一步数了它们各 1 个，第二步再补上各 1 个，所以没有遗漏。

一般化公式（$N!$ 的尾零）： \(\sum_{i=1}^{\infty} \lfloor N/5^i \rfloor = \lfloor N/5 \rfloor + \lfloor N/25 \rfloor + \lfloor N/125 \rfloor + \cdots\)

直到 $5^i > N$ 为止。

面试追问：”那 $1000!$ 呢？” → $200 + 40 + 8 + 1 = 249$（别忘了 $625 = 5^4$ 贡献 4 个因子 5）。

面试中说： “尾零来自因子 10 = 2×5，因子 2 远多于 5，所以只需要数因子 5 的个数。5 的倍数贡献 1 个，25 的倍数额外贡献 1 个，125 的倍数再额外贡献 1 个，以此类推。对 100! 来说就是 20 + 4 = 24。”

题目11：100th Digit ⭐⭐ ↑ 返回 list

来源： 绿皮书 4.2

$(1 + \sqrt{2})^{3000}$ 的小数点后第一位是几？

答案： 9

解法（绿皮书）： $(1+\sqrt{2})^n + (1-\sqrt{2})^n$ 是整数（二项式展开后 $\sqrt{2}$ 项相消）。而 $0 < (1-\sqrt{2})^{3000} < 10^{-100}$（极小正数）。所以 $(1+\sqrt{2})^{3000}$ = 整数 - 极小正数，小数部分 $\approx 0.999…$，第一位是 9。

三、条件概率与贝叶斯定理

知识点

条件概率 — “缩小世界”

直觉： 条件概率就是缩小世界。已知 B 发生了，意味着我们的”宇宙”从整个样本空间 $\Omega$ 缩小到了 B。在这个缩小的世界里，A 还能存在多少？

生活例子： 全班 40 人，12 个戴眼镜，8 个是女生，其中 5 个女生戴眼镜。

• $P(\text{戴眼镜} \mid \text{女生})$ = ？
• 世界缩小到”女生”（8人），在这 8 人里有 5 个戴眼镜 → $5/8$
• 用公式验证：$P(\text{眼镜} \cap \text{女生}) / P(\text{女生}) = (5/40) / (8/40) = 5/8$ ✓

为什么分母是 $P(B)$？ 因为 $P(A \cap B)$ 是在原始大世界里算的比例，要”换算”到 B 这个小世界里，就得除以 B 占大世界的比例。就像把分数 $5/40$ 换算成以 $8$ 为基准的 $5/8$。

• 把分母的大世界换成小世界: 5/40 -> 5/8
  • 先把原来的分母抵消掉 -> 乘以40
  • 在把8放到分母 -> 除以8

P(B)告诉你B在大世界里有多小，进入B的小世界，就相当于把视野放大1/P(B)倍

乘法规则（链式法则）：

直觉： 多件事同时发生 = 第一件事发生 × 在第一件已发生的世界里第二件发生 × 在前两件已发生的世界里第三件发生 × …

例子： 袋子里 5 红 3 蓝，不放回抽两个都是红的概率？

• $P(\text{第一个红}) = 5/8$
• $P(\text{第二个红} \mid \text{第一个红}) = 4/7$（世界缩小了：少了一个红球）
• $P(\text{两个都红}) = 5/8 \times 4/7 = 20/56 = 5/14$

⚠️ 易混淆：组合方法 vs 条件概率（乘法规则）

同一道题可以用两种完全不同的思路，结果一定相同：

	组合方法	条件概率（乘法规则）
思维	一次性看全局，不分先后	按时间线讲故事，一步一步
问的问题	“所有抽法几种？满足条件几种？”	“第一步概率？在这个前提下第二步概率？”
本题算法	$\frac{\binom{5}{2}}{\binom{8}{2}} = \frac{10}{28}$	$\frac{5}{8} \times \frac{4}{7} = \frac{20}{56}$
结果	$5/14$	$5/14$ ✓

常见错误： 用组合方法算出结果后，又试图对它做条件概率的”缩小世界”换算。不需要！ 两种方法各自独立完整，选一种用到底就行。

为什么这里没有”除以 P(B)”？ 因为条件概率公式和乘法规则解决的问题不同：

• 条件概率公式 $P(A

  B) = \frac{P(A \cap B)}{P(B)}$：已知 B 发生了，求 A 的概率 → 需要除以 P(B) 来”缩小世界”

• 乘法规则 $P(A \cap B) = P(A) \times P(B

  A)$：求 A 和 B 同时发生的概率 → 把条件概率乘进去算交集

它俩其实是同一个公式的两面，把条件概率公式左右乘以 $P(B)$ 就得到乘法规则： \(P(A|B) = \frac{P(A \cap B)}{P(B)} \quad \Longleftrightarrow \quad P(A \cap B) = P(B) \times P(A|B)\) 左边是”知道结果，除出条件概率”；右边是”用条件概率，乘出交集”。抽球题求的是交集（两个都红），所以用右边（乘），不用左边（除）。

“但第二步不就是已知第一步发生了吗？” 没错！乘法规则的第二步 $P(B|A) = 4/7$ 确实是在”缩小的世界”里算的。但它只是个中间结果，你还要乘以第一步的 $5/8$，把结果拉回大世界。而条件概率公式的结果（比如”已知抽了一个红球，第二个也是红球的概率”= $4/7$）就是最终答案，不用再乘。

• 乘法规则的 $4/7$：中间步骤，还要 $\times 5/8$ 拉回大世界 → 得到 $P(A \cap B) = 5/14$
• 条件概率的 $4/7$：最终答案，已知第一个是红，第二个是红的概率就是 $4/7$，结束

面试选哪种？ 抽球/发牌/选人 → 组合更快；有明确因果链/多步决策 → 乘法规则更自然。

全概率公式 — “分情况讨论”

前提：$F_1, F_2, \ldots, F_n$ 互斥且覆盖全部可能（也就是刚好把世界分成 n 块）。

直觉： 如果一个事件 E 的概率不好直接算，就把世界分成几个不重叠的情况，每种情况下分别算 E 的概率，然后加权平均（权重就是每种情况本身的概率）。

例子： 两个工厂生产螺丝，工厂 A 产量占 60%，次品率 2%；工厂 B 产量占 40%，次品率 5%。随机拿一个螺丝是次品的概率？

• 直接算很难，分情况：
• 来自 A 的概率 × A 的次品率 = $0.6 \times 0.02 = 0.012$
• 来自 B 的概率 × B 的次品率 = $0.4 \times 0.05 = 0.020$
• 总次品率 = $0.012 + 0.020 = 0.032 = 3.2\%$

面试记忆法： 全概率 = 正向推理，从原因推结果。”知道每个原因导致结果的概率，求结果的总概率。”

贝叶斯定理 — “反向推理”

直觉（三步走）：

全概率是”从原因推结果”，贝叶斯是反过来：看到了结果，反推是哪个原因。

沿用螺丝的例子： 拿到了一个次品，它来自工厂 A 的概率？

• 先验： $P(A) = 0.6$（60% 的螺丝来自 A）
• 似然： $P(\text{次品} \mid A) = 0.02$（A 的次品率）
• 后验： $P(A \mid \text{次品}) = \frac{0.6 \times 0.02}{0.032} = \frac{0.012}{0.032} = 37.5\%$

虽然 A 产量大（60%），但 A 质量好（次品率低），所以看到次品后，A 的嫌疑反而从 60% 降到了 37.5%。这就是贝叶斯更新的力量：证据改变信念。

面试记忆法： 贝叶斯公式的结构就是：

分母就是全概率公式！所以贝叶斯 = 全概率的反面。会全概率就会贝叶斯。

先验 vs 后验 — 用”时间线”理解

最简单的解释： 先验和后验是对同一件事的信念，区别只在”看到证据之前”还是”之后”。

时间线：

   看证据前的想法  ──→  看到证据  ──→  看证据后的想法
   ================================================
        先验             ↓                后验
                     （新信息）

• 先验 (Prior) = 看证据之前你的信念 = $P(A)$
• 后验 (Posterior) = 看证据之后你的信念 = $P(A \mid B)$

生活化例子（不涉及数学）：

核心观察： 先验和后验都在回答同一个问题，只是中间多了一个证据。

硬币例子（最经典）：

朋友口袋里两枚硬币：公平硬币（50% 正）、双面正面硬币（100% 正）。随机掏一枚，抛 1 次是正面。这枚是双面硬币的概率？

• 先验： $P(\text{双面}) = 1/2$（抛之前，两种硬币各 50%）
• 似然： $P(H \mid \text{双面}) = 1$（双面时抛正面必然）
• 后验： $P(\text{双面} \mid H) = \frac{1 \times 1/2}{3/4} = 2/3$

信念从 1/2 变成了 2/3——这个”变化”就是先验变后验。正面这个证据”支持”双面硬币假设，所以信念往那边偏。

贝叶斯更新 — “今天的后验 = 明天的先验”

核心思想： 每次获得新证据，就用贝叶斯公式更新信念。上一轮算出的后验，成为下一轮的先验。信念不是跳跃式的，而是被证据连续塑造。

用硬币例子走一遍更新链：

关键规律： 证据持续支持 → 信念持续上升但永远不到 1；出现一次”不可能”的反证 → 信念瞬间归零。

比值形式（Odds Form）— 更简洁：

硬币例子用比值：

• 初始比率：$1:1$
• 每次正面的似然比 = $1 / 0.5 = 2$
• 抛 $n$ 次正面后：比率 = $2^n : 1$
• 3 次正面 → $8:1$ → $P(\text{双面}) = 8/9 \approx 0.889$ ✓

比值形式的好处：每次证据只需乘以似然比，不用重算分母。

现实应用：

• 医学诊断： 先验（人群患病率 1%）+ 检测阳性 → 后验（实际患病率）。常常低于直觉，因为假阳性 + 先验小。再做一次阳性检测 → 用当前后验作新先验 → 概率进一步上升。
• 量化交易： 先验（某股票被高估 30%）+ 新数据（财报低于预期）→ 更新后验 → 再有新信号继续更新。
• A/B 测试（贝叶斯版）： 每天用新数据更新”B 比 A 好”的概率，达到阈值（如 95%）就停。

面试一句话： “贝叶斯不是算一次就结束的公式——它是一个持续更新的过程。今天的后验是明天的先验。证据越多，信念越接近真相，但除非遇到’不可能事件’，否则永远不会绝对确定。”

独立性 — “知不知道都一样”

直觉： 独立 = 知道 B 发生了，对 A 的概率完全没有影响。B 的信息对 A 来说是”废话”。

两个重要推论：

• A、B 独立 → A 和 $B^c$ 也独立（知道 B 没发生，对 A 也没影响）
• 独立性是对称的：A 独立于 B $\Leftrightarrow$ B 独立于 A

常见面试陷阱： 互斥 ≠ 独立！恰恰相反：

• 互斥：A 发生则 B 一定不发生 → 知道 A 对 B 有巨大影响（直接排除）
• 独立：A 发生对 B 毫无影响
• 所以如果 $P(A) > 0$ 且 $P(B) > 0$，互斥的事件绝不可能独立

面试中说： “条件概率的核心是缩小样本空间，贝叶斯的核心是用证据更新信念。全概率是正向（原因→结果），贝叶斯是反向（结果→原因），它们是一对。面试中碰到’已知结果反推原因’的题，直接上贝叶斯三步：先验、似然、后验。”

例题

题目12：Boys and Girls（两个孩子）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3 + Two Sigma + Citadel

Part A： 一个家庭有两个孩子，已知至少一个是男孩。两个都是男孩的概率？

答案： $1/3$

解法：

先列出两个孩子（老大、老二）的所有可能，各占 1/4：

“至少一个男孩”排除了（女，女），剩下 3 种等概率情况。其中两个都是男孩的只有 1 种。

Part B： 你看到同事带着一个孩子是男孩。两个孩子都是男孩的概率？

答案： $1/2$

解法：

同样的表格，但条件不同了。你看到了一个特定的孩子是男孩（比如他今天带来公司的那个）。另一个孩子你没看到。

另一个孩子是男是女和你看到的这个完全无关——是独立事件。所以：

两题看起来一样，为什么答案不同？

关键区别在于信息获取方式：

Part A：”至少一个是男孩” — 这是关于整个家庭的信息。你不知道哪个是男孩，可能是老大、可能是老二、可能都是。这个信息排除了（女，女），但保留了（男，女）和（女，男）两种情况，它们和（男，男）平分概率。

Part B：”看到的那个是男孩” — 这是关于一个特定孩子的信息。你已经锁定了一个孩子的性别，另一个孩子的性别完全独立，不受影响。

用一个极端例子帮助理解：

假设一个家庭有 10 个孩子。

• Part A 版本：”至少一个是男孩，问 10 个都是男孩的概率？” → 答案接近 $1/1023$（排除了全女的情况，剩下 1023 种中只有 1 种全男）
• Part B 版本：”你看到其中一个孩子是男孩，问 10 个都是男孩？” → 答案是 $(1/2)^9 = 1/512$（其余 9 个各自独立 1/2）

差距巨大！”至少一个”给你的信息非常弱（几乎没排除什么），”看到了某一个”给你的信息很强（锁定了一个位置）。

面试中说： “两道题的区别在于条件信息的强弱。’至少一个男孩’是关于整个家庭的弱信息，它只排除了全女的情况，剩下的可能性中全男只占 1/3。而’看到某个孩子是男孩’锁定了一个具体位置，另一个孩子完全独立，所以是 1/2。面试中遇到条件概率，第一件事就是搞清楚条件到底在约束什么——是约束整体还是约束某个具体元素。”

题目13：All-Girl World? ⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

某国规定：每个家庭一直生孩子，直到生出女孩就停止。这个国家女孩在人口中的比例是多少？

答案： 50%

直觉上的误区： 很多人觉得”每个家庭都一直生到有女孩才停”，所以女孩会更多。但答案恰恰是 50%。

解法 1：看每一个孩子，而不是每一个家庭。

不管停止规则是什么，每一个被生出来的孩子，在出生那一刻，是男是女的概率都是 50/50。停止规则决定了”还生不生下一个”，但不能改变”这一个是什么”。

把全国所有被生出来的孩子排成一排，每个人独立地有 50% 概率是男、50% 是女。所以总比例 = 50%。

解法 2：算一个家庭的期望孩子数。

每个家庭恰好 1 个女孩（因为生到女孩就停）。

每个家庭的期望男孩数： \(E[\text{男孩}] = 0 \times \frac{1}{2} + 1 \times \frac{1}{4} + 2 \times \frac{1}{8} + 3 \times \frac{1}{16} + \cdots = \sum_{k=0}^{\infty} k \cdot \frac{1}{2^{k+1}} = 1\)

所以每个家庭平均 1 个男孩 + 1 个女孩 = 50% : 50%。

解法 3：最简洁的论证。

假设全国有 $N$ 个家庭（$N$ 很大）。全国总共生了多少孩子？每个孩子出生时，独立地 50% 男 50% 女。不管用什么规则决定”停不停”，这个 50/50 不变。所以全国男女总数的期望比例就是 1:1。

停止规则只影响每个家庭生几个，不影响每个孩子是什么。这就像你扔硬币，规则是”扔到正面就停”——这不会改变每次扔出正面的概率是 1/2。

面试中说： “停止规则只决定样本量（生几个），不决定样本值（男还是女）。每一个被生出来的孩子，不管他/她排第几，是男是女的概率永远是 50/50。所以全国比例就是 50%。可以用期望验证：每个家庭恰好 1 个女孩，期望男孩数也是 1，比例 1:1。”

题目14：Unfair Coin（1000 枚硬币中的特殊币）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

1000 枚硬币中 1 枚两面都是正面，其余 999 枚公平。随机选一枚抛 10 次全是正面。这枚是特殊币的概率？

答案： $\approx 0.506$（约一半一半）

解法（贝叶斯，一步步来）：

定义事件：

• $A$ = 选到的是特殊币
• $B$ = 抛 10 次全是正面

先算各部分：

• $P(A) = 1/1000$（1000 枚里选到特殊币）
• $P(A^c) = 999/1000$（选到普通币）

• $P(B	A) = 1$（特殊币两面都是正面，所以 10 次必然全正面）

• $P(B	A^c) = (1/2)^{10} = 1/1024$（普通币 10 次全正面的概率）

算 $P(B)$（全概率公式）： \(P(B) = P(B|A) \cdot P(A) + P(B|A^c) \cdot P(A^c) = 1 \times \frac{1}{1000} + \frac{1}{1024} \times \frac{999}{1000}\)

代入贝叶斯： \(P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)} = \frac{1/1000}{2023/1024000} = \frac{1024}{2023} \approx 0.506\)

直觉： 虽然特殊币只有千分之一，但”10 次全正面”对普通币来说也极其罕见（千分之一），所以两者大约是 50/50。如果抛 20 次全正面，特殊币的概率就远大于 50% 了。

题目15：Fair Probability from Unfair Coin ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3 + Two Sigma + Citadel

不公平硬币（$p$ 未知）模拟公平 50/50？

答案： 抛两次。HT → “正”，TH → “反”，HH/TT → 重来。$P(HT) = P(TH) = p(1-p)$。

Two Sigma 追问： 如果 $p$ 接近 0.99，worst case 最少抛几次？

追问解答：

为什么 $p$ 极端时效率低？ 以 $p = 0.99$ 为例：

每轮有效概率只有 $2 \times 0.0099 = 1.98\%$，98% 的情况要重来。平均需要 $1/0.0198 \approx 50$ 轮 = 约 100 次抛掷才能得到一个结果。

期望抛掷次数公式： 每轮抛 2 次，有效概率为 $2p(1-p)$，所以期望抛掷次数 = $\frac{1}{2p(1-p)} \times 2 = \frac{1}{p(1-p)}$。当 $p \to 0$ 或 $p \to 1$ 时趋向无穷大。

如何改进？（面试加分点）

核心思路：用更长的序列，从中提取更多信息，减少浪费。

方法：Von Neumann 推广——按 bit 提取。 抛 $n$ 次得到序列，比如 HHHHT…，把连续的相同结果分成”runs”（连续段），然后对每个 run 的长度进行编码。或者更实用的方法：把 $n$ 次抛掷结果看作一个 $n$ 位二进制数，利用算术编码/entropy coding 的思想，尽可能接近信息论极限 $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$ bits per toss。

面试中简单回答： “基础 Von Neumann 方法每轮效率是 $2p(1-p)$，当 $p$ 极端时很浪费。改进方向是用更长的序列做批处理——比如抛 $n$ 次，对所有等概率的序列对进行配对，$n$ 越大利用率越高，理论极限是每次抛掷提取 $H(p)$ bits 的随机性。”

题目16：Dart Game ⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

扔飞镖瞄准靶心。第 2 次比第 1 次离靶心更远。如果继续扔第 3 次，第 3 次也比第 1 次更远的概率？

答案： $2/3$

解法（绿皮书）：

简单方法： 三次扔镖独立，每次离靶心的距离排名有 $3! = 6$ 种等概率排列。

已知第 2 次比第 1 次远（第 2 次排名更差）。在满足这个条件的排列中：

满足条件的有 3 种（1,2,3 和 1,3,2 和 2,3,1），其中第 3 次也比第 1 次远的有 2 种。$P = 2/3$。

推广（绿皮书）： 扔 $n$ 次，第 $2, 3, \ldots, n$ 次都比第 1 次远。第 $n+1$ 次也比第 1 次远的概率 = $\boxed{\dfrac{n}{n+1}}$。

详细推导（用条件概率）：

题目等价于：已知”第 1 次是前 $n$ 次中最好的”，问”第 1 次是前 $n+1$ 次中最好的”的概率。

由对称性（i.i.d. 的核心性质）：

• $P(\text{第1次是前 } n \text{ 次中最好}) = 1/n$
• $P(\text{第1次是前 } n+1 \text{ 次中最好}) = 1/(n+1)$

条件概率： \(P(\text{第 } n+1 \text{ 次比第 1 次远} \mid \text{前 } n \text{ 次第 1 最好}) = \frac{P(\text{第1次是前 } n+1 \text{ 次中最好})}{P(\text{第1次是前 } n \text{ 次中最好})} = \frac{1/(n+1)}{1/n} = \frac{n}{n+1}\)

注意： “第 $n+1$ 次比第 1 次远” ⟺ “第 1 次仍然是前 $n+1$ 次中最好的”（因为前 $n$ 次已经确定第 1 最好）。

对称性的直觉（为什么”第1次最好”概率等于 $1/n$）：

$n$ 次 i.i.d. 扔镖，每次排第 1 的概率相同（因为对称，没有哪一次特殊）。这 $n$ 个概率加起来 = 1（必有一次排第1），所以每次 = $1/n$。

这是 i.i.d. 对称性的万能技巧： 遇到”哪次是最好/最差”的问题，直接用 $1/n$。

Records 问题（同源拓展）：

这类题本质是”记录问题”——扔 $n$ 次，哪些次数打破了之前所有记录？

核心公式： 第 $k$ 次扔是”新纪录”（到目前为止最好）的概率 = $\dfrac{1}{k}$。

原因： 前 $k$ 次中，每一次排第 1 的概率都是 $1/k$（对称性）。所以”第 $k$ 次恰好是前 $k$ 次最好”= $1/k$。

期望总纪录数（扔 $n$ 次，期望有多少次新纪录）：

（$\gamma \approx 0.577$ 是欧拉常数。）

直觉： $n$ 越大，新纪录越稀疏——扔 1000 次，期望只有约 $\ln(1000) \approx 6.9$ 次新纪录。

常见变种：

变种 1：扔 $n$ 次，第 $n$ 次是最好的概率？

由对称性 = $1/n$。

变种 2：扔 $n$ 次，出现恰好 $k$ 次新纪录的概率？

令 $X_i = \mathbb{1}[\text{第 } i \text{ 次是新纪录}]$。可以证明 $X_1, X_2, \ldots, X_n$ 相互独立（这是记录问题的神奇性质），且 $P(X_i = 1) = 1/i$。

所以”恰好 $k$ 次新纪录”的概率由 $X_i$ 的独立分布的联合分布给出（无简洁闭式，但对 $n$ 小时可枚举）。

变种 3：第一次新纪录（除第 1 次外）出现在第几次？

第 1 次必是纪录。设 $T$ = 第二次新纪录的发生时刻。 \(P(T > k) = P(\text{第 2, 3, ..., k 次都不是纪录}) = \prod_{i=2}^{k} \left(1 - \frac{1}{i}\right) = \prod_{i=2}^{k} \frac{i-1}{i} = \frac{1}{k}\)

（望远镜求积）

所以 $E[T] = \sum_{k=1}^{\infty} P(T > k) = \sum_{k=1}^{\infty} \frac{1}{k} = \infty$——期望无穷大！这是个反直觉的结果：平均来说要等”无穷久”才出现第二次新纪录。

题目17：Dice Order（骰子递增）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3 + Citadel 面经

掷 3 个骰子，严格递增的概率？

答案： $5/54$

解法（拆成两步，用乘法规则）：

思路： 严格递增意味着三个值必须全不同，且恰好是 6 种排列中的那一种升序。

第一步：三个骰子全不同的概率

用乘法规则讲故事：

• 第 1 个骰子：随便扔，什么都行 → $6/6 = 1$
• 第 2 个骰子：不能和第 1 个相同 → $5/6$
• 第 3 个骰子：不能和前两个相同 → $4/6$

第二步：在全不同的条件下，恰好递增的概率

3 个不同的数有 $3! = 6$ 种排列方式（升序、降序、以及其他 4 种），每种等概率（因为骰子独立）。严格递增只是其中 1 种：

合并：

另一种理解（纯组合方法）：

从 1~6 中选 3 个不同的数，选法有 $\binom{6}{3} = 20$ 种。每种选法对应唯一一个递增排列。总共有 $6^3 = 216$ 种掷骰子结果。

这里用组合 $\binom{6}{3}$ 而不是排列 $P(6,3)$，是因为选出 3 个数后，递增顺序是唯一确定的，不需要考虑排列。

Two Sigma 变种： 从 52 张牌中抽 3 张（无重复点数），恰好递增的概率？

分析： 52 张牌有 13 个不同点数（A~K），每个点数 4 张。

方法一（条件概率思路）：

第一步：3 张牌点数全不同的概率

• 第 1 张：随便抽 → $52/52$
• 第 2 张：不能和第 1 张同点数，剩 48 张可选（去掉 4 张同点数）→ $48/51$
• 第 3 张：不能和前两张同点数，剩 44 张可选 → $44/50$

第二步：全不同的条件下，恰好递增

3 个不同点数有 $3! = 6$ 种排列，等概率（因为每个点数都有 4 张牌，对称性成立），递增只占 1 种：

合并： \(P = \frac{2112}{2550} \times \frac{1}{6} = \frac{2112}{15300} = \frac{352}{2550} \approx 13.8\%\)

方法二（纯组合，注意有序/无序）：

选 3 个不同点数 $\binom{13}{3}$，每个点数选一张花色 $4^3$，递增顺序唯一确定：

这里要注意：抽牌顺序影响“递增”这个事件，所以总样本空间要用有序抽法 $52\times 51\times 50$，不能直接用无序的 $\binom{52}{3}$。

面试中说： “这类排序概率题的核心套路是两步：先算值全不同的概率，再除以 $n!$（因为全不同时每种排列等概率）。骰子和纸牌的区别只在第一步——骰子每面等概率所以直接算，纸牌因为每个点数有多张所以要考虑去重。但第二步永远是除以 $n!$。”

题目18：Monty Hall（三门问题）⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3 + Citadel 面经

三扇门：一扇后面是车（大奖），两扇后面是羊（没奖）。你选了门 1，然后主持人（他知道车在哪）打开了门 3，里面是羊。现在你可以选择：坚持门 1，或者换到门 2。问：换门拿到车的概率是多少？

答案： $2/3$（换门）

为什么这道题反直觉？ 大多数人觉得”剩两扇门，50/50”。错在忽略了主持人知道车在哪——他的开门行为带有信息，不是随机的。

解法一：穷举法（最直觉）

你选了门 1，车等概率在三扇门之一。列出所有情况：

结论一目了然：不换门赢 = $1/3$，换门赢 = $2/3$。

解法二：一句话理解（面试推荐）

换门赢 ⟺ 最初选的是羊 ⟺ 概率 $2/3$

因为如果你最初选了羊（$2/3$），主持人被迫打开另一扇羊门，剩下的就是车。换门必赢。

如果你最初选了车（$1/3$），换门必输。

所以换门赢的概率就是最初选错的概率 = $2/3$。

解法三：贝叶斯法（严谨推导）

设 $C_i$ = 车在门 $i$，你选了门 1，主持人开了门 3。

分子：如果车在门 2，主持人只能开门 3 → $P(\text{开门3} \mid C_2) = 1$，$P(C_2) = 1/3$

分母（全概率）：

• $P(\text{开门3} \mid C_1) = 1/2$（车在门 1，主持人可以开门 2 或 3，随机选）
• $P(\text{开门3} \mid C_2) = 1$（车在门 2，只能开门 3）
• $P(\text{开门3} \mid C_3) = 0$（车在门 3，不可能开门 3）

关键理解： 主持人开门 3 这个动作，把门 2 的概率从 $1/3$ 更新到了 $2/3$——这就是贝叶斯更新。信息（主持人被迫的选择）改变了信念。

面试常见追问与推广：

追问 1：如果主持人是随机开的（不知道车在哪），开了门 3 碰巧是羊，换不换？

答：这时候换不换都一样，各 $1/2$。因为主持人随机开门没有信息量。用贝叶斯算：$P(\text{开门3} \mid C_1) = 1/2$，$P(\text{开门3} \mid C_2) = 1/2$（随机选，不管车在哪），所以后验不变。

追问 2：如果有 $n$ 扇门，主持人打开 $n-2$ 扇羊门，换不换？

答：换。换门赢的概率 = $\frac{n-1}{n}$。因为换门赢 ⟺ 最初选错 ⟺ 概率 $(n-1)/n$。$n$ 越大越应该换——100 扇门的版本（换门赢 99%）更容易理解直觉。

面试中说： “Monty Hall 的核心是主持人知道答案，他的行为不是随机的而是被迫的——这个行为包含了信息，导致贝叶斯更新。如果主持人是随机开门（碰巧开到羊），那就没有信息量，换不换无所谓。面试中遇到这题，用穷举三种情况的表格最快，两扇门赢一扇门输，一目了然。”

题目19：Amoeba Population（变形虫灭绝）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

一只变形虫，每分钟等概率发生以下四种变化之一（各 $1/4$）：

• 死亡（变 0 只）
• 不变（保持 1 只）
• 分裂成 2 只
• 分裂成 3 只

每只变形虫独立同分布地重复这个过程，子代也按同样规则继续。问：从这 1 只变形虫开始，种群最终完全灭绝的概率？

答案： $P = \sqrt{2} - 1 \approx 0.414$

背景：Galton-Watson 分支过程

这是分支过程 (Branching Process) 最经典的问题。每个个体独立产生随机数量后代，直到要么种群爆炸（趋于无穷），要么全部灭绝。这个模型广泛用于人口遗传、核反应、流行病传播。

核心问题：从 1 个体出发，最终灭绝的概率 $P$ 是多少？

第一步：设立方程（用第一步分析）

设 $P$ = 从 1 只变形虫出发，最终灭绝的概率。

关键观察： 这只变形虫第一步变成什么，决定了后续的”初始条件”。

• 以概率 $1/4$ 死亡（变 0 只）：种群立刻灭绝，后续灭绝概率 = $1$
• 以概率 $1/4$ 不变（还是 1 只）：问题退化回原题，灭绝概率 = $P$
• 以概率 $1/4$ 分裂为 2 只：每只独立，各自灭绝概率 $P$。两只都灭绝 = $P^2$（独立相乘）
• 以概率 $1/4$ 分裂为 3 只：三只独立，全部灭绝 = $P^3$

为什么分裂后是 $P^2$ 和 $P^3$？

分裂后产生的每只变形虫都是独立的新种群起点（分支过程的核心假设）。整个种群灭绝 ⟺ 每个子种群都灭绝 ⟺ 概率相乘。

合并所有情况：

第二步：解方程

两边乘以 4： \(4P = 1 + P + P^2 + P^3\)

整理： \(P^3 + P^2 - 3P + 1 = 0\)

一个明显的根是 $P = 1$（代入验证：$1 + 1 - 3 + 1 = 0$ ✓）。

为什么 $P = 1$ 总是一个根？因为 $P = 1$ 意味着”必灭绝”，这永远是方程的平凡解。但真正的灭绝概率是方程在 $[0, 1]$ 的最小非负解（分支过程的经典定理）。

因式分解 $(P - 1)$： \(P^3 + P^2 - 3P + 1 = (P - 1)(P^2 + 2P - 1) = 0\)

解 $P^2 + 2P - 1 = 0$： \(P = \frac{-2 \pm \sqrt{4 + 4}}{2} = -1 \pm \sqrt{2}\)

两个根：$P = \sqrt{2} - 1 \approx 0.414$（在 $[0,1]$ 内）或 $P = -\sqrt{2} - 1$（负数，舍去）。

答案：$P = \sqrt{2} - 1 \approx 0.414$ ✓

第三步：为什么选 $\sqrt{2} - 1$ 而不是 1？

方程有两个 $[0,1]$ 解（$\sqrt{2} - 1$ 和 $1$），到底哪个是真正的灭绝概率？

分支过程经典定理（Galton-Watson 理论）：

真正的灭绝概率 = 方程 $P = f(P)$ 的最小非负解，其中 $f$ 是后代个数的生成函数。

所以这里选 $\sqrt{2} - 1 \approx 0.414 < 1$。

直觉解释： 只有当种群的平均后代数 $\mu \leq 1$ 时，灭绝才是”必然”（$P = 1$）。本题中：

$\mu = 1.5 > 1$，种群期望增长 → 灭绝是可能的但不必然。所以 $P < 1$，取 $\sqrt{2} - 1$。

Galton-Watson 的关键定理（必须记住）：

设平均后代数 $\mu = E[\text{后代数}]$。

反直觉点： 即使平均后代数恰好是 1（每代平均保持不变），种群仍然必然灭绝！这是因为方差的存在：即使平均不变，波动会让种群最终有限步内归零。

验证与对比：

变种 1：每分钟死亡或分裂为 3，各 $1/2$

$\mu = 0 \times 1/2 + 3 \times 1/2 = 1.5$（和原题同均值，但结构不同）。

方程：$P = \frac{1}{2} + \frac{1}{2}P^3$

$2P = 1 + P^3$，即 $P^3 - 2P + 1 = 0$。

$P = 1$ 是根，因式分解：$(P-1)(P^2 + P - 1) = 0$。

$P = \frac{-1 + \sqrt{5}}{2} \approx 0.618$（黄金比减 1！）。

注意：均值同样是 1.5，但灭绝概率不同（0.414 vs 0.618）——说明方差/分布形状也重要，不只是均值。

变种 2：每分钟死亡或分裂为 2，各 $1/2$

$\mu = 1$（临界情形）。

方程：$P = \frac{1}{2} + \frac{1}{2}P^2$

$P^2 - 2P + 1 = (P-1)^2 = 0$，只有 $P = 1$（重根）。

临界情形必灭绝，印证定理 ✓

一句话总结：

变形虫灭绝 = Galton-Watson 分支过程。每只独立 → 灭绝概率满足 $P = f(P)$（$f$ 是后代分布的生成函数）。取最小非负解。$\mu > 1$ 时才有非平凡解（有幸存可能），$\mu \leq 1$ 时必灭绝。

面试加分点：

• 能说出”分支过程”这个名字 → 加分
• 能画出生成函数 $f(P) = \frac{1}{4}(1 + P + P^2 + P^3)$ 和 $y = P$ 的交点图 → 大加分
• 能区分 subcritical / critical / supercritical → 大加分
• 能举”核裂变”、”姓氏灭绝”、”疫情传播 $R_0$”这类现实类比 → 大加分

题目20：Candies in a Jar ⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

罐子里 10 红、20 蓝、30 绿糖果，共 60 颗。一个个随机取出。取完所有红色时，至少还有 1 蓝和 1 绿的概率？

答案： $7/12$

解法（绿皮书）：

关键转换： “取完所有红色时至少 1 蓝 1 绿” = “最后一颗红色在最后一颗蓝色之前被取出，且在最后一颗绿色之前被取出”。

设 $T_r$ = 最后一颗红色被取出的位置，$T_b$ = 最后一颗蓝色，$T_g$ = 最后一颗绿色。

需要 $T_r < T_b$ 且 $T_r < T_g$，即 $T_r$ 是三者中最小的。

$T_r, T_b, T_g$ 的排列有 $3! = 6$ 种，但不等概率。 绿皮书用条件概率计算：

事件 $T_r < T_b < T_g$：

• 最后被取出的是绿色（$T_g = 60$）的概率 = $30/60 = 1/2$（60 颗中最后一颗是绿色的概率就是绿色占比）
• 在此条件下，剩下 30 颗（10 红 + 20 蓝）中最后被取出的是蓝色的概率 = $20/30 = 2/3$
• $P(T_r < T_b < T_g) = 1/2 \times 2/3 = 1/3$

事件 $T_r < T_g < T_b$：

• 最后被取出的是蓝色的概率 = $20/60 = 1/3$
• 在此条件下，剩下 40 颗（10 红 + 30 绿）中最后是绿色的概率 = $30/40 = 3/4$
• $P(T_r < T_g < T_b) = 1/3 \times 3/4 = 1/4$

题目21：Coin Toss Game（HT 序列）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

A 和 B 轮流抛硬币（A 先抛，然后 B，然后 A…）。记录所有结果的序列。如果出现 HT 子序列（某次是 H 紧接着下一次是 T），抛出那个 T 的人赢。A 赢的概率？

答案： $4/9$

解法（状态方程法）：

关键是：是否已经有一个挂起的 H，以及轮到谁抛。

定义：

• $a_0$：轮到 A，且上一抛不是 H（没有挂起 H）时，A 最终赢的概率。
• $b_0$：轮到 B，且没有挂起 H 时，A 最终赢的概率。
• $a_H$：轮到 A，且上一抛是 H 时，A 最终赢的概率。
• $b_H$：轮到 B，且上一抛是 H 时，A 最终赢的概率。

注意：这里的 $a_0,b_0,a_H,b_H$ 是最终赢的概率，不是期望步数。所以方程右边没有额外的 +1。只有在问“还需要多少期望步”时，才会有 1 + ...。

状态含义更具体地说：

• 下标 0：当前没有挂起的 H。下一次如果抛 T，不会立刻形成 HT。
• 下标 H：上一抛是 H。下一次谁抛出 T，谁就完成 HT 并获胜。
• 字母 $a/b$：表示现在轮到谁抛。

初始状态是 $a_0$，因为一开始轮到 A，且还没有任何挂起的 H。我们最终要求的就是 $a_0$。

先看有挂起 H 的状态：

逐项解释：

• 左边 $a_H$：轮到 A，且上一抛是 H 时，A 最终赢的概率。
• $\frac12\cdot1$：A 抛 T，立即形成 HT，且这个 T 是 A 抛的，所以 A 赢，概率贡献是 1。
• $\frac12 b_H$：A 抛 H，仍然有挂起 H，但轮到 B，所以进入状态 $b_H$。

逐项解释：

• 左边 $b_H$：轮到 B，且上一抛是 H 时，A 最终赢的概率。
• $\frac12\cdot0$：B 抛 T，立即形成 HT，且这个 T 是 B 抛的，所以 B 赢，A 输，A 赢概率是 0。
• $\frac12a_H$：B 抛 H，仍然有挂起 H，但轮到 A，所以进入状态 $a_H$。

解得：

再看没有挂起 H 的状态：

逐项解释：

• 左边 $a_0$：轮到 A，且没有挂起 H 时，A 最终赢的概率。
• $\frac12b_H$：A 抛 H，产生挂起 H，轮到 B，所以进入 $b_H$。
• $\frac12b_0$：A 抛 T，没有形成 HT，也没有挂起 H，轮到 B，所以进入 $b_0$。

逐项解释：

• B 抛 H，产生挂起 H，轮到 A，所以进入 $a_H$。
• B 抛 T，没有形成 HT，也没有挂起 H，轮到 A，所以进入 $a_0$。

代入 $a_H=2/3,b_H=1/3$：

代入消元：

直觉： A 先手有劣势（$4/9 < 1/2$），因为 A 抛 H 后 B 有机会立刻抛 T 赢。B 作为后手反而有 $5/9$ 的赢率。

题目22：Russian Roulette ⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3 + Citadel 面经

Version 1： 6 发左轮枪 1 颗子弹。两人轮流扣扳机，每次重新转。你选先手还是后手？

答案： 选后手。先手死的概率 = $6/11$。

解法（递推方程）：

每次扣扳机前都重新转轮盘，所以每次中弹概率都是 $1/6$，独立的。

按时间线走：

• 第 1 轮先手扣：中弹概率 $1/6$，游戏结束；没中（$5/6$）→ 后手扣
• 第 1 轮后手扣：中弹概率 $1/6$，游戏结束；没中（$5/6$）→ 回到先手
• 第 2 轮先手扣：又回到了一模一样的局面…

关键观察： 如果两人第一轮都没死（概率 $5/6 \times 5/6 = 25/36$），局面跟开始完全一样。这就是递推！

设先手最终死的概率为 $p$： \(p = \underbrace{\frac{1}{6}}_{\text{第一轮就死}} + \underbrace{\frac{5}{6} \times \frac{5}{6}}_{\text{两人都没死}} \times \underbrace{p}_{\text{回到起点}}\)

这里的 $p$ 不是“每次扣扳机中弹概率”。每次中弹概率已经是 $1/6$。

$p$ 的定义是：

从“轮到先手扣扳机”这个完整局面开始，先手最终死亡的概率。

方程逐项解释：

• $\frac16$：先手第一枪直接中弹，先手死亡。
• $\frac56\times\frac56$：先手没中，后手也没中，游戏回到和最开始完全一样的局面。
• 乘上 $p$：既然回到同一个局面，后续先手最终死亡的概率还是 $p$。

解方程： \(p = \frac{1}{6} + \frac{25}{36}p\) \(p - \frac{25}{36}p = \frac{1}{6}\) \(\frac{11}{36}p = \frac{1}{6}\) \(p = \frac{6}{11} \approx 54.5\%\)

先手死的概率 $6/11 > 1/2$，后手死的概率 $= 1 - 6/11 = 5/11 \approx 45.5\%$。所以选后手。

直觉理解： 为什么先手吃亏？因为每一轮先手都先暴露在风险中。虽然每次只多承担一点点风险，但无限轮累积下来，先手承受的总风险更大。

验证（用几何级数展开）：

先手死 = 第 1 轮死 + 第 2 轮死 + 第 3 轮死 + …

Version 2： 6 发左轮枪 1 颗子弹。子弹位置固定，不重新转，轮流扣。先手还是后手？

答案： 两者都是 $1/2$，无所谓。

解法： 子弹在 6 个位置中的某一个，等概率。列出所有情况：

先手死：位置 1、3、5 → 概率 $3/6 = 1/2$ 后手死：位置 2、4、6 → 概率 $3/6 = 1/2$

完全对等。

为什么 Version 1 和 Version 2 结论不同？

核心：不重新转时，”前面没中”这个信息会让后面的条件概率升高，这个升高效果恰好抵消了后手后行动的优势，使得两者持平。

Version 3（Citadel 高频）： 6 发左轮枪 2 颗连续子弹。你的对手先扣了一次没死。轮到你了，你要重新转还是直接扣？

答案： 不要重新转，直接扣更安全。

解法： 2 颗子弹在连续位置。不失一般性设子弹在位置 5 和 6（其实在哪两个连续位置都一样，分析是对称的）。

位置：[1:空] [2:空] [3:空] [4:空] [5:弹] [6:弹]

对手先扣没死 → 他不在子弹位置 → 他在位置 1、2、3 或 4（等概率各 $1/4$）

选择 A：不转（直接扣下一发）

选择 B：重新转

重新随机，6 个位置等概率，2 个有子弹：

$25\% < 33.3\%$，不转更安全。

直觉理解： 对手活着告诉你一个信息——当前位置不是子弹。而且因为子弹是连续的，当前位置不是子弹意味着下一个位置更可能不是子弹（子弹”抱团”在一起，远离了安全区的下一个位置）。重新转则放弃了这个信息。

面试追问：如果 2 颗子弹不连续（随机放置），答案变吗？

不连续的话，对手活着只告诉你当前位置是空的，但下一个位置是否有子弹跟这个信息关系较弱。具体算：对手在 4 个空位之一，下一个位置有子弹的概率取决于子弹的分布。平均来看 $P(\text{死} \mid \text{不转}) = 2/5 = 40\% > 1/3$，这时候应该重新转。

面试中说： “俄罗斯轮盘三个版本考的知识点不同：V1 是递推方程（先手每轮先暴露，累积劣势）；V2 是对称性（不重新转 → 奇偶位置等分）；V3 是条件概率（对手存活提供信息，连续子弹时信息有利于下一发，不连续时信息不利）。V3 的核心是：信息是否对你有利，取决于子弹的分布结构。”

题目23：Aces（4 人各得 1 张 A）⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

52 张牌分给 4 个人各 13 张。每人都恰好有一张 A 的概率？

答案： $\frac{52}{52} \times \frac{39}{51} \times \frac{26}{50} \times \frac{13}{49} \approx 0.105$

解法（绿皮书条件概率法，最直觉的方式）：

一张张看 4 张 A 的去向：

第 1 张 A： 它在 52 张牌中的某个位置，必然属于 4 个人中的某一个。概率 = $52/52 = 1$。

第 2 张 A： 它不能和第 1 张 A 在同一个人手里。第 1 张 A 占了某人 13 张中的 1 张，剩余 51 张牌中有 $51 - 12 = 39$ 张属于另外 3 个人。$P = 39/51$。

第 3 张 A： 前 2 张 A 已经在 2 个人手里了。剩余 50 张牌中，属于另外 2 个人的有 $50 - 24 = 26$ 张。$P = 26/50$。

第 4 张 A： 前 3 张 A 在 3 个人手里。剩余 49 张中，属于最后一个人的有 $49 - 36 = 13$ 张。$P = 13/49$。

直觉： 约 10.5% 的概率，不算低。

题目24：Gambler’s Ruin ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3 + Two Sigma + Citadel

初始财富 $i$，每局赢 $1（概率 $p$）或输 $1（概率 $q = 1-p$）。到 $N$ 就赢，到 0 就破产。赢的概率？

答案：

推导（绿皮书）：

变量定义（关键！不要混淆）：

• $i$ = 当前财富（初始为 $i$，随每一局上下波动）
• $p$ = 赢的概率（赢了财富 $+1$）
• $q = 1-p$ = 输的概率（输了财富 $-1$）
• $P_i$ = 从财富 $i$ 出发，最终到达 $N$（赢钱）的概率
• $N$ = 胜利线（到达就赢），$0$ = 破产线（到达就输）

⚠️ 容易混淆的点：

1. $p$ 对应”财富上升”，所以递推式中 $p$ 和 $P_{i+1}$ 绑定
2. $P_i$ 定义的是”赢的概率”，不是”破产的概率”（若改成破产概率，答案互补 $1 - P_i$）

第一步：列递推方程。 在状态 $i$ 时（$0 < i < N$），一步分析：

• 以概率 $p$ 赢一局 → 财富变为 $i+1$ → 之后赢的概率 = $P_{i+1}$
• 以概率 $q$ 输一局 → 财富变为 $i-1$ → 之后赢的概率 = $P_{i-1}$

全概率合并： \(P_i = p \cdot P_{i+1} + q \cdot P_{i-1}\)

记忆法： “$p$ 乘以赢了之后会去的状态” → $p \cdot P_{i+1}$。

边界条件：$P_0 = 0$（已破产，不可能赢），$P_N = 1$（已到达胜利线）。

第二步：化简。 移项：$P_{i+1} - P_i = \frac{q}{p}(P_i - P_{i-1})$

设 $d_i = P_i - P_{i-1}$，则 $d_{i+1} = (q/p) \cdot d_i$。这是等比数列：

第三步：求和。 $P_i = P_0 + d_1 + d_2 + \cdots + d_i = 0 + d_1(1 + q/p + (q/p)^2 + \cdots + (q/p)^{i-1})$

如果 $q/p \neq 1$：$P_i = d_1 \cdot \frac{1 - (q/p)^i}{1 - q/p}$

用 $P_N = 1$ 解出 $d_1$，代入得：

第四步：公平情况 $p = q = 1/2$。 此时 $q/p = 1$，上面的公式分母为 0。用 L’Hôpital 或直接从 $d_i = d_1$（常数）得 $P_i = i \cdot d_1$，$P_N = N \cdot d_1 = 1$，$d_1 = 1/N$，$P_i = i/N$。

例子： 你有 $50，每局 50/50 赢或输 $1。赢到 $100 就走，输到 $0 破产。$P = 50/100 = 50\%$。

Two Sigma 变种： 非对称随机游走，起点为 $i$，每步 +1（概率 $p$）或 -1（概率 $q = 1-p$），0 处有吸收壁（到 0 就停）。没有上界 $N$。 求：(a) 被吸收（最终回到 0）的概率？(b) 被吸收时走过步数的期望？

变种解答：

(a) 被吸收的概率

这是单边 Gambler’s Ruin：去掉上界，相当于让 $N \to \infty$。

关键观察：$P_i(\text{到 } N)$ 的含义随极限变化。 在有界情形 $P_i$ 是”到 $N$”的概率，但当 $N \to \infty$ 时，”到 $N$” 就变成了”逃到无穷远而不破产“。剩下的结局只有破产，所以：

从公式 $P_i = \frac{1 - (q/p)^i}{1 - (q/p)^N}$ 分三种情形分析 $(q/p)^N$ 的极限行为：

情形 1：$p < 1/2$（向左漂移）

$q/p > 1$，所以 $(q/p)^N \to \infty$（大于1的数自乘无限次指数爆炸）。分母趋于 $-\infty$，整个分式 $\to 0$。

→ $P_i(\text{破产}) = 1 - 0 = \mathbf{1}$，必然破产。每一步期望是负的，长期只会越跌越低。

情形 2：$p = 1/2$（完全公平）

原公式崩（$q/p = 1$ 让分母变 0），改用 $P_i(\text{到 } N) = i/N \to 0$。

→ $P_i(\text{破产}) = \mathbf{1}$，仍然必然破产！

这是反直觉的核心点：即使公平赌博，只要下有底（0 这堵墙）、赌场资金无限，随机游走的波动迟早会把你拖到 0。这就是”赌徒必输”的数学本质——即使无抽水的公平赌博，有限资金对无限资金仍是必输。

情形 3：$p > 1/2$（向右漂移）

$q/p < 1$，所以 $(q/p)^N \to 0$（小于1的数自乘无限次指数衰减）。分母趋于 1，公式收敛到 $1 - (q/p)^i$。

→ $P_i(\text{破产}) = 1 - [1 - (q/p)^i] = \mathbf{(q/p)^i}$，起点越远越安全。

总结公式：

分水岭：$p = 1/2$。 跨过这个临界点，破产从”必然”变成”可能但指数衰减”。

数值直觉（$p = 0.6, q = 0.4, q/p = 2/3$）：

微小优势 + 起点 20 块 → 破产概率仅 0.03%——”资本厚度 + 正期望”对抗破产的保护作用。

几何衰减的直觉： $(q/p)^i$ 可以理解为”连续 $i$ 次被往下推”的概率——每从 $i$ 降到 $i-1$ 需要一次不利波动，累积 $i$ 次就 $(q/p)^i$。

量化应用（Kelly Criterion 的基础）： 策略无正期望 → 不管下多少长期必破产；有正期望 → 起始资金越大生存概率越高，但下注太重仍可能破产。这是”赌资管理 (bankroll management)” 的数学基础。

(b) 被吸收时走过步数的期望

这里必须区分“无条件期望”和“条件在最终被吸收时的期望”。

设 $T$ = hit 0 的时间。

情况 1：$p < 1/2$（向左漂移）

此时 $P(T<\infty)=1$，所以无条件期望就是普通吸收时间期望。

这里：

• $E_i$ 表示“当前财富/位置是 $i$ 时，到 hit 0 还需要的期望步数”。
• 下标 $i$ 是状态，不是时间。
• 右边的 $1$ 是当前先走一步。
• $pE_{i+1}$ 是赢一局后到 $i+1$ 的后续期望。
• $qE_{i-1}$ 是输一局后到 $i-1$ 的后续期望。
• $E_0=0$ 是吸收边界：已经到 0，不需要再走。

试线性解 $E_i=ai+b$。由 $E_0=0$ 得 $b=0$。代入：

所以 $0 = 1 + a(p-q)$，即 $a = \frac{1}{q-p}$。

验证： $p = 1/3, q = 2/3$，从状态 1 出发：$E_1 = \frac{1}{2/3 - 1/3} = 3$。直觉上合理：每步平均向左走 $1/3$，从位置 1 回到 0 大约需要 3 步。

情况 2：$p = 1/2$

此时 $q - p = 0$，期望是无穷大。虽然一定会被吸收（概率 1），但期望步数无限。这是随机游走的经典结论：对称随机游走一定会回到原点，但期望回归时间是无穷。

情况 3：$p > 1/2$

被吸收的概率 $(q/p)^i < 1$，不一定被吸收。

如果把 $T=\infty$ 也算进随机变量，那么无条件 $E[T]=\infty$，因为有正概率永远不 hit 0。

但如果问的是条件在最终被吸收的情况下，平均走多少步，则：

直观解释：条件在“最终会 hit 0”后，路径等价于一个向左漂移的随机游走，左右概率交换，平均每步向左移动 $p-q$。从 $i$ 降到 0，期望时间就是 $i/(p-q)$。

面试中说： “Gambler’s Ruin 是随机游走最核心的模型。基本版用递推方程 + 等比数列求解。Two Sigma 变种去掉上界后，关键分水岭是 $p$ 和 $1/2$：$p<1/2$ 时一定被吸收且 $E[T]=i/(q-p)$；$p=1/2$ 时一定被吸收但期望时间无穷；$p>1/2$ 时被吸收概率是 $(q/p)^i$，无条件期望时间无穷，但条件在被吸收时的期望是 $i/(p-q)$。”

题目25：Basketball Scores ⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

篮球运动员罚球 100 次。第一次命中，第二次未中。之后每次的命中率 = 之前的命中率（即 $k/n$，$k$ 是已进球数，$n$ 是已罚球次数）。恰好进 50 个的概率？

答案： $\boxed{1/99}$

令人震惊的事实： 最终进球数可以是 $1, 2, \ldots, 99$ 中任何值，而且每个值概率相等（都是 $1/99$）！这叫 Pólya 壶模型 (Pólya’s Urn Scheme)，是概率论最经典反直觉结论之一。

概念澄清：$P_{n,k}$ 到底是什么

⚠️ 新手最易混淆点：$P_{n,k}$ 是联合概率，不是命中率！

三件不同的事。 只有在极端情况 $k=1$ 时，$P_{n, 1} = 1/(n-1)$ 和”命中率 $1/(n-1)$”数值相等——是巧合，不是规律。$k=50$ 时，$P_{100, 50} = 1/99$ 但”命中率”是 $50/99$，完全不同。

等价的 Pólya 壶模型表述：

壶里有 1 红球（代表”进”）和 1 白球（代表”没进”）。重复以下步骤 98 次：

• 随机抽一个球，记下颜色
• 把这个球连同一个相同颜色的球一起放回壶（所以壶里球数每次 +1）

抽到红球的概率 = 壶里红球比例 = 目前为止”进”的比例——完全等价于篮球问题。

这是概率论里最著名的”富者愈富“模型（preferential attachment）。

解法（绿皮书归纳法）：

从小情况开始找规律：

$n = 3$（第 3 次罚球）：前 2 次 1 进 1 不进，命中率 = $1/2$。

• 进了（概率 1/2）→ 3 次进 2 个
• 没进（概率 1/2）→ 3 次进 1 个

$P_{3,1} = 1/2$，$P_{3,2} = 1/2$。都等于 $1/(3-1) = 1/2$ ✓

$n = 4$：

• 如果 3 次时 1 进（概率 1/2），第 4 次命中率 = $1/3$
  • 进了 → 4 次 2 进。概率 = $1/2 \times 1/3 = 1/6$
  • 没进 → 4 次 1 进。概率 = $1/2 \times 2/3 = 2/6$
• 如果 3 次时 2 进（概率 1/2），第 4 次命中率 = $2/3$
  • 进了 → 4 次 3 进。概率 = $1/2 \times 2/3 = 2/6$
  • 没进 → 4 次 2 进。概率 = $1/2 \times 1/3 = 1/6$

$P_{4,1} = 2/6 = 1/3$，$P_{4,2} = 1/6 + 1/6 = 2/6 = 1/3$，$P_{4,3} = 2/6 = 1/3$

全都等于 $1/(4-1) = 1/3$ ✓

规律： $P_{n,k} = 1/(n-1)$ 对所有 $k = 1, \ldots, n-1$ 成立。

直觉（表面）： 因为命中率会自我调节（进太多就降低，进太少就提高），所以最终进球数在 1 到 99 之间的每个值都等概率。

严格归纳证明

待证命题： 对所有 $n \geq 2$，$P(k_n = k) = \frac{1}{n-1}$，$k \in {1, 2, \ldots, n-1}$。

基础情况 $n=2$： $P(k_2 = 1) = 1$（给定第 1 球进、第 2 球没进）= $1/(2-1)$ ✓

归纳步骤： 假设 $P(k_{n-1} = j) = \frac{1}{n-2}$ 对 $j = 1, \ldots, n-2$ 成立，证 $P(k_n = k) = \frac{1}{n-1}$。

按第 $n$ 球”中/没中”分解：

关键抵消： $(k-1) + (n-1-k) = n-2$，正好和分母的 $n-2$ 约掉，$k$ 消失。这是整道题的”数学魔法时刻“。∎

所以 $P_{100, 50} = 1/99$。

关键洞察：两股力量精确抵消

本题最反直觉的地方：

(1) 边缘分布：均匀 — $P(k_{100} = k) = \frac{1}{99}$ 对每个 $k$ 都一样。 (2) 条件命中率：非均匀 — $P(\text{下一球中} \mid k_n = k) = \frac{k}{n}$，强烈依赖 $k$。

按常理会预测什么？

🗣️ 白话版： 最终中 99 球（或中 1 球）的概率，应该远大于中 50 球的概率——因为这里有正反馈，一旦开局往某个方向偏，就会一路滚下去。

对概率有直觉的人，看到”富者愈富”机制会预测 $k$ 呈 U 形分布（两极化），具体推理：

• 早期球数少，命中率波动剧烈——一两球的运气决定”初始方向”
• 正反馈机制把偏差放大——命中率一旦高了，后面倾向于留在高位；低了，倾向于留在低位
• 中间值（如 $k \approx 50$）是”不稳定平衡点”——任何扰动都会被推向两端
• 预期结果： $k$ 集中在 1 附近和 99 附近，中间稀疏

按常理预测 (U 形)：
 概率
  |████                          ████
  |████                          ████
  |██████                      ██████
  |________________________________________
  1          25       50      75          99

但实际结果是完全均匀：

实际 (均匀)：
 概率
  |████████████████████████████████████████
  |████████████████████████████████████████
  |________________________________________
  1          25       50      75          99

两股力量精确抵消：

• 力量 A（正反馈）：
  • 中得多 -> 下一球更容易中 -> 中得更多 -> 下一球更更容易中 -> 中球数量(k)接近100
  • 中得少 -> 下一球更不容易中 -> 中得更少 -> 下一球更更不容易中 -> 中球数量(k)接近0
• 力量 B（稀少开局 + 自我平均）：分母不断变大，后期波动越来越小；稀少的开局（仅 1 中 1 没中）让初期”引力”很弱——早期还没把轨迹锁定到极端，后期已经拉不动了（钟形方向）

这两股力量精确互相抵消——结果既不是 U 形，也不是钟形，而是均匀。

Pólya 壶就是”刚刚好”的临界点：

• 正反馈再强一点（比如每次放回 2 个同色球）→ 变成真正的 U 形（arcsine 分布）
• 正反馈消失（独立伯努利）→ 变成钟形（二项分布）
• 临界状态 → 完全均匀

过程不均，但结果均。 这是概率论里最美丽的现象之一。

进阶 1：鞅性质（Martingale）

定义 $M_n = k_n / n$ = “截至第 $n$ 球的命中率”。验证：

即 $E[\text{下一步命中率} \mid \text{当前}] = \text{当前命中率}$ —— 这是鞅 (martingale)。

由鞅收敛定理，$M_n \xrightarrow{a.s.} M_\infty$，可以证明 $M_\infty \sim \text{Uniform}[0,1]$。

进阶 2：贝叶斯视角（de Finetti 定理）

Pólya 壶模型有一个惊人的等价表述：

先从 $U[0,1]$ 抽出一个”真实命中率” $p$，再做 $n$ 次独立伯努利$(p)$ 试验。

两种模型在分布上完全等价！用 Beta-Binomial 验证：

对所有 $k = 0, 1, \ldots, n$ 都一样！

这就是 de Finetti 定理的实例： 可交换序列 ⟺ 先抽一个隐藏参数，再做 i.i.d.

换句话说——篮球问题看起来”路径依赖、自我强化”，但它其实等价于“一开始就抽定了一个水平 $p$，然后按 $p$ 独立投篮”。这就是为什么最终 $k_{100}/100$ 服从均匀分布。

进阶 3：与二项分布的对比

面试官可能追问：这和”命中率固定为 $1/2$ 的二项分布”有什么区别？

本质区别： 二项分布假设每次 $p$ 固定；Pólya 壶模型隐含地”学习” $p$ —— 每一步都在更新 $p$ 的估计。

面试加分点

1. “这是 Pólya 壶模型 (Pólya’s Urn Scheme)” — 说得出名字直接高几个级别。
2. “答案揭示了反直觉事实：富者愈富的动力学，最终分布却是均匀的。” — 面试官希望听到这句。
3. “$k_n/n$ 是鞅，极限服从 $U[0,1]$。” — 展示随机过程基础。
4. “这等价于先抽 $p \sim U[0,1]$ 再做伯努利试验——de Finetti 定理的实例。” — 贝叶斯功底。
5. “对比 Binomial(100, 0.5)，$P(k_{100}=50) \approx 8\%$，而这里只有 1%——因为 Pólya 的方差大得多。” — 数字直觉。

变种 1：Beta(α, β) 初始壶 ⭐⭐⭐⭐

壶里初始有 $\alpha$ 红球和 $\beta$ 白球（原题是 $\alpha = \beta = 1$）。$n$ 次抽取后进 $k$ 个的概率？

答案： Beta-Binomial 分布

当 $\alpha = \beta = 1$（Beta(1,1) = U[0,1]），退化为均匀分布。

变种 2：双倍增长 Pólya 壶 ⭐⭐⭐⭐

每次抽到球后，放回 2 个同色球（不是 1 个）。极限分布还是均匀吗？

答案： 不再是 $U[0,1]$。一般地，放回 $c$ 个同色球时，$M_n \to M_\infty \sim \text{Beta}(\alpha/c, \beta/c)$。

• $c = 1$：$\text{Beta}(1, 1) = U[0, 1]$（原题）
• $c = 2$：$\text{Beta}(1/2, 1/2) = \text{arcsine}$ 分布（U 形，两端更密）
• $c \to \infty$：退化到 0 和 1 两点（初始颜色主导）

直觉： $c$ 越大，”富者愈富”效应越强，极限越两极化。

变种 3：Ehrenfest 壶模型（对立模型） ⭐⭐⭐⭐

每次抽一个球，换成相反颜色再放回（而不是复制）。问极限行为？

答案： 这是与 Pólya 壶截然相反的”平衡态模型“，源于统计力学。最终分布不再均匀，而是集中在 $k \approx n/2$ 附近（类似二项分布），描述”系统趋于平衡”。

对比：

• Pólya Urn：正反馈（富者愈富）→ 均匀分布
• Ehrenfest Urn：负反馈（偏离平衡就被拉回）→ 钟形分布

这两个模型合起来，是随机过程课最经典的一对。

面试中说： “这是 Pólya 壶模型。$P_{n,k} = 1/(n-1)$ 通过归纳法可证——关键在条件分解时 $(k-1) + (n-1-k) = n-2$ 恰好抵消。反直觉的地方是：虽然动力学是’富者愈富’，但边缘分布却完全均匀——两股力量精确抵消。$k_n/n$ 是鞅，极限服从 $U[0,1]$；等价地，可以看作’先抽 $p \sim U[0,1]$ 再做伯努利试验’，这是 de Finetti 定理的实例。”

题目26：Cars on Road ⭐⭐ ↑ 返回 list

来源： 绿皮书 4.3

高速公路上，20 分钟内观测到至少一辆车的概率是 $609/625$。假设任何时刻看到车的概率恒定。5 分钟内观测到至少一辆车的概率？

答案： $3/5$

解法（绿皮书）：

设 $p$ = 5 分钟内观测到至少一辆车的概率。

“20 分钟没有车” = “4 个连续 5 分钟都没车”（独立）：

已知 $P(\text{20 分钟至少一辆}) = 609/625$，所以：

验证： $(2/5)^4 = 16/625$ ✓

题目27：贝叶斯经典 — 硬币选择 ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经

硬币 1：$P(H) = 2/3$，硬币 2：$P(H) = 1/3$。随机选一枚抛 3 次全正面。下一次正面的概率？

答案： $17/27$

解法（两步走）：

第一步：用贝叶斯算”选的是哪枚硬币”

• 先验：$P(\text{coin 1}) = P(\text{coin 2}) = 1/2$

• 似然：$P(\text{3H}

  \text{coin 1}) = (2/3)^3 = 8/27$

• 似然：$P(\text{3H}

  \text{coin 2}) = (1/3)^3 = 1/27$

直觉： 3 次全正面后，我们几乎确定选的是 coin 1（概率 8/9），因为 coin 1 出正面的概率更高。

第二步：用全概率公式算下一次正面

直觉验证： 如果没看到 3 次正面，下一次正面的概率 = $1/2 \times 2/3 + 1/2 \times 1/3 = 1/2$。看到 3 次正面后，概率从 $1/2$ 升到了 $17/27$，因为我们更相信是 coin 1（正面概率高的那枚）。

📦 知识点速通：特征值与特征向量

后面的题（28 题及相关协方差矩阵题）频繁用到特征值。这一节从零把它讲透，以后忘了可以回来查。

1. 定义

对方阵 $A$（$N \times N$），如果存在非零向量 $v$ 和标量 $\lambda$ 使得：

那么：

• $\lambda$ 叫 $A$ 的特征值（eigenvalue）
• $v$ 叫对应的特征向量（eigenvector）

用人话说： 矩阵 $A$ 作用在大多数向量上，都会把它转向新的方向。但有一些”幸运的”向量，$A$ 只是把它们沿着原来的方向拉长（或缩短）——这些就是特征向量。拉长的倍数就是特征值。

  一般向量:           特征向量:
  v ↗                 v →
  ↓ (乘A)             ↓ (乘A)
  Av ↘               λv → (同方向，只是拉长)
  (方向改变)         (方向不变)

2. 矩阵作为”空间变换”的几何理解

核心观点： 一个 $2 \times 2$ 矩阵就是一个”改造平面”的工具。它把每个向量 $(x, y)$ 送到一个新向量。

看矩阵做了什么：追踪基向量

记住这个技巧：想知道一个矩阵干什么，看它如何变换 $e_1 = (1,0)$ 和 $e_2 = (0, 1)$。

所以矩阵的两列就是变换后的两个基向量。

例子 1：对角矩阵 = 纯缩放

• $e_1 = (1, 0) \to (2, 0)$：$x$ 轴方向拉长 2 倍
• $e_2 = (0, 1) \to (0, 3)$：$y$ 轴方向拉长 3 倍

变换前:                 变换后:
y                       y
│  □(1,1)              │      □(2,3)
│                       │        
│                       │        
└──→x                  │        
                        │        
                        └─────────→x
(单位方格)              (2×3 长方形)

几何意义： 整个平面沿 $x$ 拉长 2 倍、沿 $y$ 拉长 3 倍。方格变成长方形，但还是”正”的——没有倾斜。

例子 2：加入剪切（shear）

• $e_1 = (1, 0) \to (2, 0)$：$x$ 轴不变方向，拉长 2 倍
• $e_2 = (0, 1) \to (5, 3)$：$y$ 轴被倾斜了！ 原本指向正上方，现在指向右上方（5, 3）

变换前:                 变换后:
y                       y             □(7, 3)
│  □(1,1)              │           /
│  │                    │         / 
│  │                    │       / □(5,3)
└──→x                  │     / /   
                        │   / /     
                        │ / /       
                        └─────────□(2,0)→x
(单位方格)              (倾斜的平行四边形)

那个 5 做了什么？ 它告诉你：“$y$ 轴被拉向右边 5 格”。

这叫剪切（shear）变换——平面被”推”得倾斜了。方格变成平行四边形。

直观类比：想象一叠扑克牌竖着摞着（这是 $y$ 轴）。你把最上面一张牌推向右边，其他牌按比例跟着推——最后整叠牌从竖着的变成倾斜的。这就是 5 的作用。

一般 $2 \times 2$ 矩阵的分解

• $a$：$x$ 轴在 $x$ 方向上的拉伸
• $b$：$y$ 轴被”推”到 $x$ 方向的量（剪切 1）
• $c$：$x$ 轴被”推”到 $y$ 方向的量（剪切 2）
• $d$：$y$ 轴在 $y$ 方向上的拉伸

任何 $2 \times 2$ 变换都可以分解成”旋转 + 缩放 + 旋转”（SVD 分解）的组合。剪切、旋转、缩放都是它的特殊情况。

3. 怎么找特征值：特征方程

从 $A v = \lambda v$ 出发，移项：

要让非零 $v$ 满足，需要 $A - \lambda I$ 不可逆（否则只有零解）。不可逆等价于行列式为 0：

这叫特征方程。解这个关于 $\lambda$ 的多项式方程就得到所有特征值。

例子：$A = \begin{bmatrix} 3 & 1 \ 1 & 3 \end{bmatrix}$

$(3-\lambda)^2 = 1 \Rightarrow 3 - \lambda = \pm 1 \Rightarrow \lambda = 2$ 或 $\lambda = 4$

4. 怎么找特征向量：回代解齐次方程

有了特征值 $\lambda$ 之后，求特征向量的步骤：

步骤 1： 把 $\lambda$ 代入 $(A - \lambda I) v = 0$

步骤 2： 解这个齐次线性方程组（会有无穷多解，成一条过原点的直线——整条直线的非零向量都是特征向量）

步骤 3： 随便取一个非零解作为特征向量（通常归一化或选简洁的）

继续上面的例子：$A = \begin{bmatrix} 3 & 1 \ 1 & 3 \end{bmatrix}$，$\lambda_1 = 2$

解 $(A - 2I) v = 0$：$v_1 + v_2 = 0$，即 $v_2 = -v_1$。

特征向量（取 $v_1 = 1$）：$v = (1, -1)^T$。

验证： $A v = (3 \cdot 1 + 1 \cdot (-1), 1 \cdot 1 + 3 \cdot (-1))^T = (2, -2)^T = 2 v$ ✓

对 $\lambda_2 = 4$：

解 $-v_1 + v_2 = 0$，即 $v_2 = v_1$。

特征向量：$v = (1, 1)^T$。

验证： $A v = (4, 4)^T = 4 v$ ✓

5. 对剪切矩阵 $\begin{bmatrix} 2 & 5 \ 0 & 3 \end{bmatrix}$ 求特征值和特征向量

求特征值：

$\lambda = 2$ 或 $\lambda = 3$

有用的事实： 上三角（或下三角）矩阵的特征值就是它的对角线元素。这里对角线是 2 和 3。

求特征向量（$\lambda = 2$）：

方程组：$5 v_2 = 0$ 且 $v_2 = 0$。所以 $v_2 = 0$，$v_1$ 任意。

特征向量：$(1, 0)^T$（就是 $x$ 轴方向！）

求特征向量（$\lambda = 3$）：

方程组：$-v_1 + 5 v_2 = 0$，即 $v_1 = 5 v_2$。

特征向量（取 $v_2 = 1$）：$(5, 1)^T$

验证： $A (5, 1)^T = (2 \cdot 5 + 5 \cdot 1, 0 + 3)^T = (15, 3)^T = 3 (5, 1)^T$ ✓

几何解读：特征向量就是”剪切后还是同方向的线”

剪切矩阵 $A = \begin{bmatrix} 2 & 5 \ 0 & 3 \end{bmatrix}$ 的两个特征方向：

• $v_1 = (1, 0)$：沿 $x$ 轴方向——这条线上的点没有被剪切（因为 $A$ 的第一列就是 $(2, 0)$，沿 $x$ 方向）。
• $v_2 = (5, 1)$：沿 “倾斜” 方向——这条线正好是剪切后 $y$ 轴去的方向（$e_2 \to (5, 3)$，方向就是 $(5, 1)$）。

直觉： 虽然整体被剪切了，但这两条”特殊直线”上的点，作用后还在自己这条直线上。它们就是这个变换的”骨架”。

6. 本题：全 1 矩阵 $J$ 的特征值

先看 $J$ 作用在向量上

$J v$ 永远是一个”所有分量相等的向量”，那个相等的值 = $v$ 的分量之和。

特征值 $\lambda = N$（重数 1）

取 $v = \mathbf{1} = (1, 1, \ldots, 1)^T$：

所以 $\lambda_1 = N$，特征向量 $\mathbf{1}$。

特征值 $\lambda = 0$（重数 $N-1$）

任何”分量之和为 0”的向量 $v$：

所以是特征值 0 的特征向量。

这样的向量构成一个 $(N-1)$ 维子空间（$\mathbf{1}$ 的正交补），所以特征值 0 的重数是 $N-1$。

为什么 $J$ 这么”特殊”？

因为 $J$ 的秩（rank）只有 1——所有行都一样，实质上只有”一个维度的信息”。

• 1 个有意义的方向 → 1 个非零特征值 ($N$)
• 剩下的 $N-1$ 个维度 $J$ “看不见” → $N-1$ 个 0 特征值

所有秩为 1 的矩阵都是这个结构：一个非零特征值 + 一堆 0。

7. 关键定理：$aI + bM$ 的特征值

定理： 如果 $M v = \lambda v$，那么 $(aI + bM) v = (a + b\lambda) v$。

证明（一行）：

意思： $aI + bM$ 的特征向量和 $M$ 完全一样，特征值是 $a + b \lambda$。

8. 回到相关矩阵

令 $a = 1-\rho$，$b = \rho$，$M = J$。用上面的定理：

• $J$ 的特征值 $N$ → $\Sigma$ 的特征值 $(1-\rho) + \rho N = 1 + (N-1)\rho$（重数 1）
• $J$ 的特征值 0 → $\Sigma$ 的特征值 $(1-\rho) + 0 = 1 - \rho$（重数 $N-1$）

特征向量和 $J$ 一样：

• $\mathbf{1}$ 方向（所有 $X_i$ 同升同降）→ 特征值 $1 + (N-1)\rho$
• 分量之和为 0 的方向（变量间对冲）→ 特征值 $1 - \rho$

9. 特征值速通小结（记这个就够了）

1. $A v = \lambda v$：矩阵 $A$ 的”特殊方向” $v$，经过 $A$ 只被拉伸不转向
2. 矩阵的两列 = 变换后的两个基向量；剪切就是”$y$ 轴被推向 $x$”之类
3. 求特征值：解 $\det(A - \lambda I) = 0$（多项式方程）
4. 求特征向量：把 $\lambda$ 代回 $(A - \lambda I) v = 0$ 解
5. 上三角/下三角矩阵的特征值 = 对角线元素
6. 全 1 矩阵 $J$ 的特征值：$N$（1 次）+ 0（$N-1$ 次）
7. $aI + bM$ 的特征值 = $a + b\lambda$（$\lambda$ 是 $M$ 的特征值），特征向量不变

题目28：Correlation Range ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经（出现 5+ 次）+ Citadel 面经

$\text{corr}(X,Y) = a$，$\text{corr}(Y,Z) = b$。$\text{corr}(X,Z)$ 的范围？

答案： $ab \pm \sqrt{(1-a^2)(1-b^2)}$

解法（绿皮书 3.6 + 面经）：

为什么有范围限制？ 如果 $X$ 和 $Y$ 高度正相关，$Y$ 和 $Z$ 也高度正相关，$X$ 和 $Z$ 不可能是负相关。就像”身高和体重正相关，体重和腰围正相关，那身高和腰围不可能是负相关”。

推导： 相关系数矩阵必须是半正定的（PSD），即行列式 $\geq 0$：

把这个看成关于 $c$ 的一元二次不等式：

用求根公式：$c = ab \pm \sqrt{a^2b^2 - a^2 - b^2 + 1} = ab \pm \sqrt{(1-a^2)(1-b^2)}$

所以 $c \in [ab - \sqrt{(1-a^2)(1-b^2)}, \quad ab + \sqrt{(1-a^2)(1-b^2)}]$

例子： $a = 0.8$，$b = 0.6$：

• $ab = 0.48$
• $\sqrt{(1-0.64)(1-0.36)} = \sqrt{0.36 \times 0.64} = \sqrt{0.2304} = 0.48$
• 范围 = $[0, 0.96]$

Two Sigma 高频追问 1：$N$ 个变量两两相关系数都相同为 $\rho$，$\rho$ 的范围？

答案： $\boxed{-\frac{1}{N-1} \leq \rho \leq 1}$

第一步：写出相关系数矩阵

$N$ 个标准化变量 $X_1, \ldots, X_N$，两两相关系数都是 $\rho$。相关系数矩阵：

可以写成 $\Sigma = (1-\rho) I + \rho J$，其中 $J$ 是全 1 矩阵（所有元素都是 1）。

第二步：求 $\Sigma$ 的特征值

全 1 矩阵 $J$ 的特征值：

• $\lambda_1 = N$（对应特征向量 $\mathbf{1} = (1, 1, \ldots, 1)^T$，因为 $J \mathbf{1} = N \mathbf{1}$）
• $\lambda_2 = \cdots = \lambda_N = 0$（对应 $\mathbf{1}$ 的正交补空间，维度 $N-1$）

所以 $\Sigma = (1-\rho)I + \rho J$ 的特征值为：

• $\lambda_1 = (1-\rho) + \rho \cdot N = \boxed{1 + (N-1)\rho}$（重数 1，对应 $\mathbf{1}$ 方向）
• $\lambda_2 = \cdots = \lambda_N = (1-\rho) + \rho \cdot 0 = \boxed{1 - \rho}$（重数 $N-1$）

第三步：用 PSD 条件约束 $\rho$

相关系数矩阵必须是半正定（PSD）—— 所有特征值 $\geq 0$：

$N$ 越大，$\rho$ 下限越接近 0。比如 $N=100$ 时，$\rho \geq -1/99 \approx -0.01$。

为什么 $\rho$ 下限是 $-\frac{1}{N-1}$？几何/方差直觉：

考虑 $S = X_1 + X_2 + \cdots + X_N$ 的方差：

方差必须 $\geq 0$，所以：

临界情况 $\rho = -\frac{1}{N-1}$： 此时 $\text{Var}(S) = 0$，即 $X_1 + \cdots + X_N = $ 常数（恒等于均值）。

直觉： 如果 $N$ 个变量”两两都在反着来”，它们的和必须恒定。$N$ 越多，这种”互相抵消”对每对的反相关程度要求就越松——因为”分担反相关”的对数变多了。

经典例子： 投 $N$ 面骰子的结果如果已经约束为”和为 $S$ 固定”，则每对的相关系数恰好为 $-\frac{1}{N-1}$。

一句话总结： $N$ 个变量不可能”所有对都高度负相关”——因为总方差必须非负，$N$ 越多，这个约束对每一对的反相关上限就越紧。

Two Sigma 高频追问 2：如何构造满足给定协方差矩阵 $\Sigma$ 的 $N$ 个变量？

短答： Cholesky 分解 + 线性组合独立标准正态

具体步骤：

① 用 Cholesky 分解把 $\Sigma$ 写成 $\Sigma = L L^T$，其中 $L$ 是下三角矩阵。

② 生成 $N$ 个独立的标准正态 $Z = (Z_1, \ldots, Z_N)^T$，$Z_i \overset{iid}{\sim} N(0, 1)$。

③ 构造 $X = LZ$，则 $X \sim N(0, \Sigma)$。

④ 验证： 协方差计算

为什么能这么做？

• $\Sigma$ 是半正定矩阵 → 一定存在 $L$ 使得 $\Sigma = LL^T$（线性代数定理）。
• 独立标准正态的线性组合还是正态，且协方差由线性变换决定。

具体例子：$N=3$，$\rho = 0.5$

目标协方差：

找下三角 $L$：

构造 $X = LZ$：

验证：

• $\text{Var}(X_2) = 0.25 + 0.75 = 1$ ✓
• $\text{Cov}(X_1, X_2) = 0.5 \cdot \text{Var}(Z_1) = 0.5$ ✓
• $\text{Cov}(X_2, X_3) = 0.5 \cdot 0.5 + 0.866 \cdot 0.289 \approx 0.25 + 0.25 = 0.5$ ✓

替代方法 1：Spectral Decomposition（特征值分解）

令 $X = UD^{1/2} Z$。则：

对比：

• Cholesky 数值上更稳定、更快（$O(N^3/3)$ 操作）——实际使用最多。
• Spectral 更有几何直观，但计算更慢。

替代方法 2：单因子模型（等相关情形的简洁构造）

对于”两两都相关系数为 $\rho \geq 0$”的情形，有一个更简洁的构造：

其中 $Z_0, Z_1, \ldots, Z_N$ 是 $N+1$ 个独立标准正态。

验证：

• $\text{Var}(X_i) = \rho + (1-\rho) = 1$ ✓
• $\text{Cov}(X_i, X_j) = \rho \cdot \text{Var}(Z_0) + 0 = \rho$（$i \ne j$） ✓

解读：

• $Z_0$ 是所有 $X_i$ 共享的”共同因子”（比如市场波动）
• $Z_i$ 是 $X_i$ 的独立特异冲击（idiosyncratic shock）
• $\rho$ 越大，共同因子权重越大——这是金融中的单因子模型的雏形

这个构造对于 $\rho < 0$ 不适用（$\sqrt{\rho}$ 不是实数），但对于”等相关正数”的简单构造特别漂亮。

面试中说： “相关系数矩阵必须半正定。对等相关矩阵 $(1-\rho)I + \rho J$，特征值是 $1+(N-1)\rho$（1 个）和 $1-\rho$（$N-1$ 个）。PSD 要求 $\rho \geq -\frac{1}{N-1}$——直觉上，这确保了 $\text{Var}(X_1 + \cdots + X_N) = N[1+(N-1)\rho] \geq 0$。构造时用 Cholesky 分解 $\Sigma = LL^T$，对独立正态做线性变换 $X = LZ$。对于等相关的 $\rho > 0$，还可以写成 $X_i = \sqrt{\rho} Z_0 + \sqrt{1-\rho} Z_i$——这就是单因子模型。”

四、离散和连续分布 + 几何概率

知识点

离散分布总表（绿皮书 Table 4.2）

连续分布总表（绿皮书 Table 4.3）

指数分布的无记忆性（Memoryless Property）

已经等了 $s$ 时间没有事件发生，再等 $t$ 时间没有事件的概率和从头等 $t$ 时间一样。”过去等的时间白等了”。

Poisson 过程

事件以恒定速率 $\lambda$ 独立发生。时间 $t$ 内发生 $x$ 次的概率： \(P(N(t) = x) = \frac{e^{-\lambda t}(\lambda t)^x}{x!}\)

期望 = $\lambda t$，方差 = $\lambda t$。

正态分布的矩（Moments）

$X \sim N(0,1)$：$E[X] = 0$，$E[X^2] = 1$，$E[X^3] = 0$，$E[X^4] = 3$

规律：奇数矩 = 0（对称性），$E[X^{2n}] = (2n-1)!! = 1 \times 3 \times 5 \times \cdots \times (2n-1)$

例题

题目29：Meeting Probability（约会问题）⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.4 + Two Sigma + Citadel

两个银行家约在 5:00-6:00 之间见面，各自随机到达（均匀分布），各等 5 分钟就走。见面的概率？

答案： $23/144$

解法（绿皮书，几何概率法）：

设 A 到达时间为 $X$，B 到达时间为 $Y$，都在 $[0, 60]$ 均匀分布。

不满足条件的区域 = 两个直角三角形，每个底 = 高 = 55。

变种（Two Sigma 面经）：N 个人约在 9:00–10:00 见面，各等 15 分钟

问题： $N$ 个人各自在 $[0, 60]$ 分钟内随机均匀到达，每人到达后等 15 分钟就走。至少有两人相遇的概率？

结论（总公式）：

其中 $L = 60$ 分钟（总时长），$d = 15$ 分钟（等待时长）。

思路：补集 + 间距法（Spacings Method）

为什么用补集： 直接算”至少有一对相遇”需要容斥很多项（$\binom{N}{2}$ 对），非常繁琐。取反——”没有任何两人相遇” 更简洁。

关键观察： “没有任何两人相遇” ⟺ 把 $N$ 个到达时间排序后，相邻的两人间隔都 > 15 分钟（如果相邻的都超过 15 分钟，那非相邻的肯定更远）。

推导

设 $N$ 个到达时间 $X_1, \ldots, X_N \overset{iid}{\sim} U[0, L]$。

目标： 求 $P(\text{排序后所有相邻间距 } > d)$。

巧妙换元： 设 $Y_i = X_{(i)} - (i-1)d$，其中 $X_{(i)}$ 是排好序的第 $i$ 个。

检验约束：

• “相邻间距 $> d$”：$X_{(i+1)} - X_{(i)} > d$ ⟺ $Y_{i+1} > Y_i$ ✓
• “$X_{(1)} \geq 0$”：$Y_1 \geq 0$ ✓
• “$X_{(N)} \leq L$”：$Y_N \leq L - (N-1)d$ ✓

所以经过换元： $0 \leq Y_1 < Y_2 < \cdots < Y_N \leq L - (N-1)d$。

这等价于 “$N$ 个 $[0, L-(N-1)d]$ 上均匀随机点（排序后）”。

换元后怎么算概率？（详细推导）

很多人看到这一步就蒙了：凭什么换完元之后，概率就变成 $\left(\frac{L - (N-1)d}{L}\right)^N$？ 下面一步步推。

Step 1：写下 order statistics 的联合密度

$N$ 个 iid $U[0, L]$ 的点排序之后，联合密度是：

（$N!$ 来自”原本 $N!$ 种排列都对应同一组排序”，每个 iid 点的密度是 $1/L$，所以整体是 $N!/L^N$。）

Step 2：事件概率 = 密度 × 区域体积

设事件区域为：

因为密度是常数 $N!/L^N$，所以：

难点转移到：怎么算这个奇形怪状的 $\text{Vol}(S)$？——直接积分要处理 $x_{i+1} - x_i > d$ 的约束，很烦。换元就是为了化简这个体积。

Step 3：换元，把奇形怪状变成标准单形

令 $y_i = x_i - (i-1)d$。这是纯平移（每个 $x_i$ 减掉一个常数），所以：

• Jacobian $= \left

  \det \frac{\partial(y_1,\ldots,y_N)}{\partial(x_1,\ldots,x_N)}\right

  = 1$（对角线全是 1 的单位阵）

• 体积不变：$\text{Vol}(S) = \text{Vol}(S’)$

其中 $S’$ 是换元后的区域：

这就是一个标准的”排序单形”！ 约束只剩”排好序 + 在区间内”，间距约束 $> d$ 已经被消掉了。

Step 4：标准排序单形的体积公式

在区间 $[0, L’]^N$ 中，”已排序”的点占比是 $\frac{1}{N!}$（因为 $N!$ 种排列中只有一种升序）：

Step 5：代回去，$N!$ 正好抵消

更直观的”收缩身体”解释

如果上面推导觉得抽象，用这个物理图像：

1. $N$ 个 iid $U[0,L]$ 的点，想象成 $N$ 个小人随机到达 $[0, L]$
2. 每个小人”占据” $d$ 分钟（等待窗口）——除了最后一个，等于 $N-1$ 个宽度 $d$ 的”身体”
3. “没人相遇” ⟺ “身体不重叠”
4. 把每个身体收缩成点，相当于把总空间从 $L$ 缩成 $L - (N-1)d$
5. 每个小人独立落在”缩短后的区间”里的概率是 $\frac{L-(N-1)d}{L}$
6. $N$ 个独立 → 概率乘起来：$\left(\frac{L-(N-1)d}{L}\right)^N$

换元 $Y_i = X_{(i)} - (i-1)d$ 就是在数学上执行这个”收缩身体”的操作。

代入 $N=3$ 验证

$L = 60, d = 15, N = 3$：

与下表一致 ✓

当 $(N-1)d \geq L$ 时，分母已经塞不下 $N$ 个”相互独立”的时间槽，所以必然有人相遇，概率 = 1。

具体数字（$L = 60$，$d = 15$）

为什么 $N \geq 5$ 时必然相遇？

“$N$ 个人两两都分隔 > 15 分钟”需要总时间至少 $(N-1) \times 15$ 分钟（相邻间距）。

• $N = 5$：需要 $4 \times 15 = 60$ 分钟——刚好塞不下（必须有严格的 > 15，但总共只有 60）
• $N = 6$：需要 $75$ 分钟——不可能

直觉——鸽笼原理： 把 60 分钟按 15 分钟切成 4 段”时间桶”。5 个人丢进 4 个桶，必有至少两人在同一桶或相邻桶（严格来说 $N \geq 5$ 时必有两人在同一个 15 分钟窗口内）。

验证：$N = 2$ 回到原题逻辑

原题问的是”恰好两个人在 5 分钟内相遇”： \(P(\text{meet}) = 1 - \left(\frac{60-5}{60}\right)^2 = 1 - \frac{55^2}{60^2} = \frac{575}{3600} = \frac{23}{144} \ \checkmark\)

$N=2$ 的通式就是原题的几何概率法（对角线条带法）。

变种的变种：至少 $k$ 个人同时相遇

更难版本：至少有 $k$ 个人能在同一时刻都在场（即存在某个时刻 $k$ 个等待窗口同时覆盖它）。

这题需要按时间做扫描线 + 最大重叠计数，一般用 inclusion-exclusion 或 order statistics 积分。面试中很少直接问 $k \geq 3$ 的情况，但作为”你能不能拓展”的信号很有用。

面试中说： “直接算’至少两人相遇’需要容斥 $\binom{N}{2}$ 项，太繁琐。取反用间距法（spacings method）：’没人相遇’等价于’排序后相邻间距都 $> 15$’。换元 $Y_i = X_{(i)} - (i-1) \cdot 15$ 消去 $d$，问题变成 $N$ 个点在 $[0, 60 - 15(N-1)]$ 上均匀分布。最终 $P(\text{相遇}) = 1 - \left(\frac{60-15(N-1)}{60}\right)^N$。$N \geq 5$ 时必然相遇——鸽笼原理。”

题目30：Probability of Triangle（折棍子成三角形）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.4 + Citadel 面经

一根棍子在两个随机点折断成 3 段。三段能组成三角形的概率？

答案： $1/4$

解法（绿皮书，几何概率法）：

设棍子长度为 1，两个切割点为 $x$ 和 $y$（$x, y \sim U(0,1)$）。

假设 $x < y$： 三段长度为 $x$，$y - x$，$1 - y$。

三角不等式要求每段 < 总长的 1/2：

在单位正方形上，$x < y$ 的区域是左上三角形（面积 1/2）。满足三个条件的区域是一个小三角形，面积 = $1/8$。

由对称性（$x > y$ 的情况面积也是 $1/8$），总面积 = $2 \times 1/8 = 1/4$。

直觉： 只有当三个段都不超过总长一半时才能组成三角形。切割点的位置需要”刚刚好”在中间区域。

题目31：Poisson Process / Bus Waiting ⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.4 + Two Sigma 面经

公交车按 Poisson 过程到达，平均 10 分钟一班（$\lambda = 0.1$/分钟）。你随机到达车站，期望等多久？上一班车平均多久前开走的？

答案： 等待时间期望 = $1/\lambda = 10$ 分钟。上一班车也是平均 10 分钟前开走的。

这不是矛盾吗？ 上一班 10 分钟前 + 下一班 10 分钟后 = 两班之间间隔 20 分钟？但平均间隔是 10 分钟啊？

绿皮书解释： 这不矛盾。你更可能到达在长的间隔里而不是短的间隔里。如果一个间隔是 30 分钟，另一个是 5 分钟，你到达在 30 分钟间隔里的概率更大（因为它更长）。这叫 inspection paradox / length-biased sampling。

实际上，如果间隔时间分布的方差 > 0，你到达时的等待时间 > 间隔时间/2。数学上：

对指数分布：$E[X^2] = 2/\lambda^2$，$E[X] = 1/\lambda$，所以 $E[\text{等待}] = 1/\lambda$（等于平均间隔，不是一半）。

Two Sigma 面经变种：两个 officer 的指数分布

题目设定： 两个 officer 各自独立按 Poisson 过程处理请求，到达率分别为 $\lambda_1$ 和 $\lambda_2$（即 officer $i$ 的处理间隔时间 $\sim \text{Exp}(\lambda_i)$）。

下面是 6 个高频追问，按难度递增：

追问 1：下一个请求由 officer 1 处理的概率？

答： $\dfrac{\lambda_1}{\lambda_1 + \lambda_2}$

推导： 设 $T_1 \sim \text{Exp}(\lambda_1)$ 是 officer 1 下一次处理的时间，$T_2 \sim \text{Exp}(\lambda_2)$ 是 officer 2 下一次处理的时间，$T_1 \perp T_2$。

直觉： “比赛”谁更快。率高的那个赢的概率与率成正比。$\lambda_1 = 2\lambda_2$ 意味着 officer 1 快一倍，赢的概率是 $2/3$。

追问 2：第一个请求完成时间的分布？

答： $\min(T_1, T_2) \sim \text{Exp}(\lambda_1 + \lambda_2)$

推导： 两个独立指数的最小值仍是指数：

所以 $\min(T_1, T_2) \sim \text{Exp}(\lambda_1 + \lambda_2)$，期望 $= \dfrac{1}{\lambda_1 + \lambda_2}$。

核心性质：两个独立 Poisson 过程的叠加仍是 Poisson 过程，率为 $\lambda_1 + \lambda_2$。

追问 3：第一个请求完成时间的期望 vs 两个都完成的期望？

第一个完成： $E[\min(T_1, T_2)] = \dfrac{1}{\lambda_1 + \lambda_2}$

两个都完成： $E[\max(T_1, T_2)] = \dfrac{1}{\lambda_1} + \dfrac{1}{\lambda_2} - \dfrac{1}{\lambda_1 + \lambda_2}$

推导 $E[\max]$： 用恒等式 $\max + \min = T_1 + T_2$：

数值例：$\lambda_1 = \lambda_2 = 1$

• $E[\min] = 1/2$
• $E[\max] = 1 + 1 - 1/2 = 3/2$
• 验证：$E[T_1] + E[T_2] = 2 = E[\min] + E[\max] = 1/2 + 3/2$ ✓

追问 4：前 $n$ 个请求中 officer 1 处理几个？

答： $K \sim \text{Binomial}\left(n, \dfrac{\lambda_1}{\lambda_1 + \lambda_2}\right)$

关键定理（Thinning / Decomposition）： 在叠加的 Poisson 过程中，每个事件独立地以概率 $p = \lambda_1/(\lambda_1+\lambda_2)$ 来自 officer 1，与其他事件的来源独立。

神奇的独立性：给定总事件数 $n$，每个事件来自哪个 officer 独立——即使原始过程是按时间顺序发生的。

追问 5：时间 $[0, t]$ 内 officer 1 处理了 $n_1$ 个、officer 2 处理了 $n_2$ 个的概率？

答： 两个独立 Poisson：

关键：$N_1(t)$ 和 $N_2(t)$ 独立。这是 Poisson 过程的”分解性”。

追问 6：officer 1 先处理 $n$ 个请求比 officer 2 先处理 1 个请求的概率？

（即：officer 1 比 officer 2 快得多的场景——”officer 1 连赢 $n$ 局”）

答： 用追问 1 的结果 + 无记忆性：

推导思路： 每当任何一个 officer 处理完一个请求时（由无记忆性，之后”重新开始”），下一个是 officer 1 的概率独立地为 $\lambda_1/(\lambda_1+\lambda_2)$。officer 1 先处理 $n$ 个 = 连续 $n$ 次”officer 1 赢”，概率相乘。

数值例：$\lambda_1 = \lambda_2$，$n = 3$：$P = (1/2)^3 = 1/8$（每次公平，连赢 3 次）。

核心思想总结（Poisson 过程三大性质）

Two Sigma 爱问这种题的原因：它们测试你对 Poisson 过程的结构性理解——不是死记公式，而是能熟练运用”指数 = 无记忆”、”Poisson 可叠加/分解”、”最小值仍指数”等骨架性质。

面试中说： “两个独立 Poisson 叠加仍是 Poisson，率为 $\lambda_1 + \lambda_2$。第一个事件到达时间 $\sim \text{Exp}(\lambda_1+\lambda_2)$。这个事件来自 officer 1 的概率是 $\lambda_1/(\lambda_1+\lambda_2)$，且与到达时间独立。由无记忆性，之后重复此逻辑。所以前 $n$ 个事件中 officer 1 处理的次数 $\sim \text{Bin}(n, \lambda_1/(\lambda_1+\lambda_2))$。”

题目32：Moments of Normal（正态分布的矩）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.4 + Two Sigma 面经

$X \sim N(0,1)$，求 $E[X^n]$，$n = 1, 2, 3, 4$。

答案： $E[X] = 0$，$E[X^2] = 1$，$E[X^3] = 0$，$E[X^4] = 3$

解法（把 MGF 当成“矩的目录”）：

先把符号说清楚：

• “矩”就是 $E[X^n]$。一阶矩是 $E[X]$，二阶矩是 $E[X^2]$，四阶矩是 $E[X^4]$。
• $X \sim N(0,1)$ 的意思是：均值 $0$，方差 $1$。这里的 $1$ 是方差，不是“11”。
• Moment Generating Function（矩母函数）定义为：

为什么它能“生成”矩？因为指数函数可以展开：

把 $k = tX$ 代进去：

两边取期望：

所以，$M(t)$ 里 $t^n$ 前面的系数，等于 $E[X^n]/n!$。这就是为什么可以用 MGF 求矩。

对标准正态分布：

一般正态 $N(\mu,\sigma^2)$ 的 MGF 是：

所以标准正态 $N(0,1)$ 就是 $e^{t^2/2}$。如果想知道它怎么来的，可以把积分配方：

现在展开 $e^{t^2/2}$：

再和“矩的目录”对比：

逐项比较：

• 没有 $t$ 项，所以 $E[X] = 0$；
• $t^2$ 的系数是 $1/2$，所以 $E[X^2]/2! = 1/2$，得到 $E[X^2] = 1$；
• 没有 $t^3$ 项，所以 $E[X^3] = 0$；
• $t^4$ 的系数是 $1/8$，所以：

因此：

容易卡住的点：

1. 这里的 $t$ 不是随机变量，只是一个“辅助变量 / 记账变量”。它帮我们把 $E[X]$、$E[X^2]$、$E[X^3]$、$E[X^4]$ 放在同一个函数里。
2. 我们令 $t = 1$ 或 $t = 2$ 没有用，因为那是在算 $M(1)=E[e^X]$ 或 $M(2)=E[e^{2X}]$。求矩要么对 $M(t)$ 求导后代 $t=0$，要么直接比较 $t^n$ 的系数。
3. $e^{t^2/2}$ 里的 $t^4$ 项来自

不是来自

后者是 $t^8$ 项，不是 $t^4$ 项。

1. 奇数矩为 $0$ 也可以直接用对称性理解：标准正态关于 $0$ 对称，正负两边的 $X$ 和 $X^3$ 会互相抵消。

面试中记住： 标准正态的奇数矩 = 0，$E[X^2] = 1$，$E[X^4] = 3$（kurtosis of normal = 3）。

Two Sigma 面经题： $X, Y$ iid $N(0,1)$，求 $E[\max(X, 3Y)]$。需要用到 $E[\max(X,Y)]$ 的公式和正态分布的性质。

五、期望值、方差和协方差

知识点

Linearity of Expectation（最强工具）

即使 $X_i$ 之间不独立也成立。 这是解题最常用的工具。

Law of Total Expectation

协方差和方差的公式

如果独立：$\text{Cov} = 0$，方差可加。

Correlation

$\rho = 0$ 不代表独立（只是线性无关）。

例题

题目33：Connecting Noodles（接面条）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.5

碗里 100 根面条（200 个端头）。蒙眼随机选两个端头绑在一起，重复直到没有自由端。期望形成多少个圈？

答案： $E = 1 + 1/3 + 1/5 + \cdots + 1/199$

解法（绿皮书，从小情况推导）：

$n = 1$（1 根面条，2 个端头）： 只有 1 种选法（把两端绑一起），形成 1 个圈。$E[f(1)] = 1$。

$n = 2$（2 根面条，4 个端头）： 选一个端头后，有 $\binom{4}{2} = 3$ 种方式选另一个端头（实际上选定一个端头后剩 3 个可选）。

• 选到同一根面条的另一端（1/3 概率）→ 形成 1 个圈 + 还剩 1 根面条 → 总共 $1 + E[f(1)] = 2$ 个圈
• 选到另一根面条的端头（2/3 概率）→ 两根连在一起变成 1 根长面条 → 总共 $E[f(1)] = 1$ 个圈

一般化： $n$ 根面条有 $2n$ 个端头。选定一个端头后，有 $2n - 1$ 个可选。选到同一根面条另一端的概率 = $1/(2n-1)$。

递推：$E[f(n)] = E[f(n-1)] + \frac{1}{2n-1}$

对 $n = 100$：$E \approx 3.28$（100 根面条平均只形成约 3 个圈！）

题目34：Dice Game（骰子重掷游戏）⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.5 + Two Sigma + Citadel

掷骰子，掷到 4、5、6 就拿到点数的钱；掷到 1、2、3 可以重掷（必须接受新值）。期望收益？

答案：

按这个题面（最多重掷一次；如果选择重掷，第二次必须接受），最优期望收益是：

如果题目是“最多掷 3 次，每次可以选择保留或重掷”，答案才是 $14/3$，见 Q49e。

解法（绿皮书，Law of Total Expectation）：

设 $X$ 为最终收益，$Y$ 为第一次掷的结果。

这里“可以重掷”表示玩家有选择权。第一次掷到 $Y=y$ 时：

• 如果不重掷，收益就是 $y$；

• 如果重掷，第二次必须接受，期望收益是普通骰子的平均值：

  \[\frac{1+2+3+4+5+6}{6}=3.5\]

所以最优策略是比较 $y$ 和 $3.5$：

• 掷到 $1,2,3$：因为 $y<3.5$，选择重掷；
• 掷到 $4,5,6$：因为 $y>3.5$，选择保留。

因此题目虽然说“可以”重掷，但在最大化期望收益时，掷到 $1,2,3$ 一定会重掷，掷到 $4,5,6$ 一定会保留。

• $P(Y \in {4,5,6}) = 1/2$：保留，收益 = $Y$。$E[Y

  Y \in {4,5,6}] = 5$

• $P(Y \in {1,2,3}) = 1/2$：重掷一次，第二次收益 = $E[Y] = 3.5$

常见变种 1：无限重掷直到掷出 4、5、6

如果规则是“掷到 1、2、3 就继续重掷，直到掷出 4、5、6 才停止”，那么最后接受的值在 ${4,5,6}$ 上均匀，期望是：

常见变种 2：掷到 4、5、6 累加并继续，掷到 1、2、3 停止

如果规则是“掷到 4、5、6 拿到点数并继续掷；掷到 1、2、3 停止，并拿最后一次的点数”，设总收益期望为 $E$：

• 掷到 1,2,3：停止，收益 = $E[Y

  Y \in {1,2,3}] = 2$

• 掷到 4,5,6：拿到钱（期望 5）并继续掷，总收益 = $5 + E[X]$

注意： 不同版本的骰子游戏答案不同：

• 最多重掷一次：$4.25$
• 无限重掷直到 4/5/6：$5$
• 4/5/6 累加继续、1/2/3 停：$7$
• 最多 3 次且可选择保留：$14/3$

面试中一定要先确认规则。

题目35：Coupon Collector（集齐优惠券）⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.5 + Two Sigma + Citadel

$N$ 种优惠券，每次随机得一张。期望收集多少张集齐？

答案： $E = N \times H_N = N(1 + 1/2 + 1/3 + \cdots + 1/N)$

解法（绿皮书，Geometric 分布叠加）：

把过程分成 $N$ 个阶段：

• 阶段 1： 集到第 1 种。任何一张都是新的，概率 $p_1 = N/N = 1$，期望 $1/p_1 = 1$ 张
• 阶段 2： 集到第 2 种。新的概率 $p_2 = (N-1)/N$，期望 $1/p_2 = N/(N-1)$ 张
• 阶段 $k$： 已有 $k-1$ 种，新的概率 $p_k = (N-k+1)/N$，期望 $N/(N-k+1)$ 张

每个阶段是 Geometric 分布，期望 = $1/p$。

具体数值示例（生活场景）

按 $N$ 逐个看直观感受：

$N = 1$：只有 1 种优惠券（平凡情况）

$E = 1 \times H_1 = 1 \times 1 = \mathbf{1}$ 张

生活场景：只卖 1 款盲盒。买 1 个就集齐了（废话 😅）。

$N = 2$：硬币两面（$N = 2$）

$E = 2 \times H_2 = 2 \times (1 + 1/2) = \mathbf{3}$ 次

生活场景：抛硬币直到两面都见过。平均 3 次。

• 第 1 次：必然新的（无论正反）→ 1 次
• 第 2 阶段：期望 $1/(1/2) = 2$ 次等到另一面
• 合计：$1 + 2 = 3$ ✓

$N = 3$：石头剪刀布 / 三色

$E = 3 \times H_3 = 3 \times (1 + 1/2 + 1/3) = 3 \times \frac{11}{6} = \mathbf{5.5}$ 次

生活场景：买三色糖直到集齐三种颜色。

阶段拆解：

• 第 1 种：$3/3 = 1$ 次
• 第 2 种：$3/2 = 1.5$ 次
• 第 3 种（最难）：$3/1 = 3$ 次
• 合计：$1 + 1.5 + 3 = 5.5$

注意：最后一种单独就要 3 次——比前面两种之和还多！

$N = 4$：四色牌 / 麻将四花色

$E = 4 \times H_4 = 4 \times (1 + 1/2 + 1/3 + 1/4) = 4 \times \frac{25}{12} = \frac{25}{3} \approx \mathbf{8.33}$ 次

生活场景：抽扑克牌（只看花色）直到集齐 ♠♥♦♣ 四种。

• 第 1 张：1 次
• 第 2 张：$4/3 \approx 1.33$
• 第 3 张：$4/2 = 2$
• 第 4 张：$4/1 = 4$（单独一张就占近一半时间！）

$N = 6$：六面骰子

$E = 6 \times H_6 = 6 \times (1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) = 6 \times 2.45 = \mathbf{14.7}$ 次

生活场景：投骰子直到 1-6 六面都出现过。

阶段拆解（感受”越到后面越慢”）： | 阶段 | 需要投几次（期望） | 累计 | |—|—|—| | 见到第 1 面 | $6/6 = 1$ | 1 | | 见到第 2 面 | $6/5 = 1.2$ | 2.2 | | 见到第 3 面 | $6/4 = 1.5$ | 3.7 | | 见到第 4 面 | $6/3 = 2$ | 5.7 | | 见到第 5 面 | $6/2 = 3$ | 8.7 | | 见到第 6 面（最后一个）| $6/1 = 6$ | 14.7 |

“最后一面就要 6 次，占总时间的 40%。” 这是集邮类问题的核心洞察：最后一张最难集。

$N = 10$：十位数字 / 手机号每位都出现

$E = 10 \times H_{10} = 10 \times 2.929 \approx \mathbf{29.3}$ 次

生活场景：随机按数字键直到 0-9 都按过。

$N = 52$：一副扑克牌（不看花色，只看 52 张各不相同）

$E = 52 \times H_{52} \approx 52 \times 4.538 \approx \mathbf{236}$ 次抽牌

生活场景：无限有放回地抽扑克牌，直到每一张都抽到过。

$N = 151$：原版 151 只宝可梦

$E = 151 \times H_{151} \approx 151 \times 5.59 \approx \mathbf{844}$ 包卡

生活场景：集齐 151 只宝可梦卡要开将近 850 包（注意现实中还有稀有度权重，数字更大）。

$N = 365$：每天看见一位生日不同的人

$E = 365 \times H_{365} \approx 365 \times 6.53 \approx \mathbf{2384}$ 天 ≈ 6.5 年

生活场景：每天随机遇到一个陌生人，平均 6.5 年才能遇见”每一天生日的人”都见一遍。

对比表

$E/N$ 增长很慢（对数级别 $\ln N$），这就是为什么 “集齐” 永远比”买一张”贵不了太多倍。

渐近公式（$N$ 大时）

$H_N \approx \ln N + \gamma$，其中 $\gamma \approx 0.5772$（Euler-Mascheroni 常数）。

所以：

重要尺度：$E$ 以 $N \ln N$ 增长——比线性 $N$ 快一点，但比 $N^2$ 慢得多。

关键直觉总结

1. 最后一张最难：阶段 $k$ 期望 $N/(N-k+1)$ 张——$k$ 越大越难，最后一张平均要 $N$ 张！
2. 最后一张贡献 $\approx 1/\ln N$ 比例：$N=6$ 时最后一张占 40%，$N=100$ 时约占 19%，但始终是单项最大贡献。
3. $E \approx N \ln N$：不是 $N$，也不是 $N^2$，而是中间的”对数慢涨”。

Two Sigma/Citadel 追问： 掷 6 次骰子，期望看到几种不同的面？

用 Linearity of Expectation：$E = \sum_{i=1}^{6} P(\text{面}i\text{出现至少一次}) = 6 \times (1 - (5/6)^6) = 6 \times 0.665 = 3.99$

直觉对照：要”见完所有 6 面”需要 14.7 次，而”只投 6 次”平均见 4 面——缺 2 面就是那”最后最难的”两面。

题目36：Optimal Hedge Ratio ⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.5

你买了 1 股 A，想用 B 对冲。卖空多少股 B 使组合方差最小？A 的方差 $\sigma_A^2$，B 的方差 $\sigma_B^2$，相关系数 $\rho$。

答案： $h = \rho \frac{\sigma_A}{\sigma_B}$

解法（绿皮书）：

组合收益 = $r_A - h \cdot r_B$

对 $h$ 求导令其为零：

直觉： $\rho > 0$（正相关）时卖空 B（$h > 0$）。$\rho$ 越大或 $\sigma_A/\sigma_B$ 越大，需要卖空越多。$\rho = 0$ 时 $h = 0$（不相关，对冲无用）。

题目37：Two Sigma 面经 — 掷 6 个骰子中不同面数的期望 ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经

掷 6 个骰子，结果中不同 number 的期望数量？

答案： $6 \times (1 - (5/6)^6) \approx 3.99$

解法（Linearity of Expectation + Indicator Variable）：

定义 0/1 指示变量：

不同面数 = $I_1 + I_2 + \cdots + I_6$

关键技巧： 不要试图枚举所有可能的组合。用 Indicator Variable 把”数不同的个数”转化为”每种出现没出现”的和，然后用 Linearity of Expectation。

举一反三：

这类题的模板是：问“出现过多少种 / 非空多少类 / 满足条件的种类数”的期望，就给每一种类设一个 0/1 indicator。

然后：

注意：indicator 的值仍然只有 0 或 1；变化的是它代表的事件。

1. 掷 $n$ 次骰子，期望出现多少种点数

   设：

   \[I_k=\mathbf{1}_{\{\text{点数 }k\text{ 至少出现一次}\}},\qquad k=1,\ldots,6\]

   固定点数 $k$，它一次都没出现的概率是：

   \[\left(\frac{5}{6}\right)^n\]

   所以：

   \[P(I_k=1)=1-\left(\frac{5}{6}\right)^n\]

   因此：

   \[E=6\left(1-\left(\frac{5}{6}\right)^n\right)\]

   原题就是 $n=6$。

2. 从 $m$ 种 coupon 中抽 $n$ 次，期望收集到多少种

   设：

   \[I_k=\mathbf{1}_{\{\text{第 }k\text{ 种 coupon 至少出现一次}\}},\qquad k=1,\ldots,m\]

   固定一种 coupon，它一次都没出现的概率是：

   \[\left(1-\frac{1}{m}\right)^n\]

   所以：

   \[E=m\left(1-\left(1-\frac{1}{m}\right)^n\right)\]

3. 扔 $n$ 个球进 $m$ 个盒子，期望非空盒子数

   设：

   \[I_k=\mathbf{1}_{\{\text{第 }k\text{ 个盒子非空}\}},\qquad k=1,\ldots,m\]

   第 $k$ 个盒子空的概率是：

   \[\left(1-\frac{1}{m}\right)^n\]

   所以：

   \[E[\text{非空盒子数}] =m\left(1-\left(1-\frac{1}{m}\right)^n\right)\]

4. 掷 6 个骰子，期望有多少个点数恰好出现一次

   这时 indicator 的事件变了：

   \[J_k=\mathbf{1}_{\{\text{点数 }k\text{ 恰好出现一次}\}},\qquad k=1,\ldots,6\]

   固定点数 $k$，恰好出现一次的概率是：

   \[\binom{6}{1}\left(\frac{1}{6}\right)\left(\frac{5}{6}\right)^5\]

   所以：

   \[E=6\cdot \binom{6}{1}\left(\frac{1}{6}\right)\left(\frac{5}{6}\right)^5\]

一句话记： indicator 不一定表示“是否出现过”；它表示“这个种类是否满足题目要数的条件”。

题目38：Two Sigma 面经 — Gold/Silver Coins ⭐⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经

扔 1000 枚公平硬币，500 金 500 银。金币正面得 3 元，银币正面得 1 元。已知总共得了 1100 元，金币正面朝上的期望数量？

答案：

精确条件期望约为：

面试中用正态/LMMSE 近似可以快速得到：

解法 1（正态近似 / LMMSE，面试推荐）：

设：

• $G$ = 500 枚金币中正面数，$G\sim \text{Bin}(500,1/2)$
• $S$ = 500 枚银币中正面数，$S\sim \text{Bin}(500,1/2)$
• $W=3G+S$ = 总得分

先验：

所以：

方差：

因为 $G,S$ 独立：

协方差：

用联合正态条件期望公式：

解法 2（精确表达式）：

已知：

所以：

合法范围要求 $0\leq S\leq 500$，因此 $G=200,\ldots,366$。

条件概率权重为：

所以精确条件期望是：

$$E[G\mid 3G+S=1100]

\frac{\sum_{g=200}^{366}g\binom{500}{g}\binom{500}{1100-3g}} {\sum_{g=200}^{366}\binom{500}{g}\binom{500}{1100-3g}} $$

数值计算约为：

六、Order Statistics（顺序统计量）

知识点

$n$ 个独立 $U(0,1)$ 随机变量排序后：

• 第 $k$ 小的期望 = $k/(n+1)$
• 最大值期望 = $n/(n+1)$，最小值期望 = $1/(n+1)$

直觉： $n$ 个点把 $[0,1]$ 均匀分成 $n+1$ 段。

最大值的 CDF： $P(\max \leq x) = x^n$ 最大值的 PDF： $f(x) = nx^{n-1}$ 最大值的期望： $E[\max] = \int_0^1 x \cdot nx^{n-1}dx = n/(n+1)$

第 $k$ 小的分布是 Beta$(k, n-k+1)$。

例题

题目39：E[max] and E[min] ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.6 + Two Sigma + Citadel

$X, Y$ iid $U(0,1)$。$E[\max(X,Y)]$ = ?

答案： $2/3$

解法： $n = 2$，$E[\max] = n/(n+1) = 2/3$。

也可以直接算： $E[\max] = E[X] + E[Y] - E[\min] = 0.5 + 0.5 - 1/3 = 2/3$。

或者用 $E[\max(X,Y)] = \int_0^1 x \cdot 2x \, dx = 2 \int_0^1 x^2 dx = 2/3$。

题目40：Cov(min, max) ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.6 + Two Sigma 面经（出现多次）

$X, Y$ iid $U(0,1)$。$\text{Cov}(\min(X,Y), \max(X,Y))$ = ?

答案： $1/36$

解法（绿皮书）：

$\text{Cov}(\min, \max) = E[\min \cdot \max] - E[\min] \cdot E[\max]$

算 $E[\min \cdot \max]$： $\min(X,Y) \cdot \max(X,Y) = X \cdot Y$（因为 $\min \times \max = X \times Y$，不管谁大谁小）。

Two Sigma 面经追问 1： $N$ 个 iid $U(0,1)$ 的 $\min$ 和 $\max$ 的协方差？

设：

先记住两个 order statistic 的期望：

所以：

关键是算 $E[UV]$。

最小值在 $u$ 附近、最大值在 $v$ 附近（$0<u<v<1$）的 joint density 是：

解释：

• 选哪个样本当最小值：$N$ 种；
• 选哪个样本当最大值：$N-1$ 种；
• 剩下 $N-2$ 个样本都要落在 $(u,v)$ 中，概率密度贡献 $(v-u)^{N-2}$。

因此：

这个积分结果是：

于是：

回到本题 $N=2$：

和前面答案一致。

Two Sigma 面经追问 2： 第 $k$ 小值 $X_{(k)}$ 的 PDF？

令：

第 $k$ 小值 $X_{(k)}$ 落在 $x$ 附近，意思是：

• 有 $k-1$ 个样本小于 $x$；
• 有 1 个样本落在 $x$ 附近；
• 有 $N-k$ 个样本大于 $x$。

所以：

这就是 Beta 分布：

检查两个端点：

• 最小值 $X_{(1)}$：

  \[f_{X_{(1)}}(x)=N(1-x)^{N-1}\]

• 最大值 $X_{(N)}$：

  \[f_{X_{(N)}}(x)=Nx^{N-1}\]

一句话记： $N$ 个 uniform 的第 $k$ 小值服从 Beta$(k,N+1-k)$；$\min$ 和 $\max$ 的协方差是 $\frac{1}{(N+1)^2(N+2)}$。

题目41：Random Ants（蚂蚁碰撞）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 4.6 + Citadel 面经

500 只蚂蚁在 1 米棍上随机位置，各自随机方向以 1m/min 移动。碰撞就反向。多久全部掉落？

答案： 最多 1 分钟

解法（绿皮书，关键洞察）：

碰撞反向等价于穿过彼此。 想象蚂蚁是不可区分的小球。两个球碰撞后反向，和两个球穿过彼此的最终位置完全相同。

如果蚂蚁穿过彼此不反向，每只蚂蚁只管往一个方向走到底。最慢的蚂蚁（从最靠近中间的位置出发）也只要走 1 米，时间 = 1 分钟。

所以最多 1 分钟全部掉落。

直觉验证： 如果棍子只有 2 只蚂蚁面对面走，碰撞反向后各自走到边缘。这和两只蚂蚁穿过彼此各走到对面一样。

七、Markov Chain 和状态方程

知识点

Markov 性质

下一步只取决于当前状态，和过去无关。

解题方法：状态方程

1. 定义状态： 把问题的进度分成有限个状态
2. 每个状态只看一步： 列出从当前状态出发，各种转移的概率
3. 列方程： 每个状态的期望 = 1（当前步的消耗）+ 各种转移的期望
4. 解方程

状态方程里的 $E_0,E_1,E_2$ 到底是什么？

这是这类题最容易混的地方：

$E_0,E_1,E_2$ 通常不是“第 0 步、第 1 步、第 2 步”的期望，而是“当前处在某个状态时，从现在开始到完成还需要的期望步数”。

例如目标是第一次出现 HH：

• $S_0$：当前没有任何有用进度。历史末尾不是 H，例如空序列、T、HTT。
• $S_1$：当前已有 1 个有用的 H。历史末尾是 H，例如 H、TH、TTH。
• 完成状态：已经出现 HH。

对应：

• $E_0$：现在处于 $S_0$，从现在开始到第一次出现 HH 还需要的期望抛掷次数。
• $E_1$：现在处于 $S_1$，从现在开始到第一次出现 HH 还需要的期望抛掷次数。
• 完成状态的期望是 0，因为已经完成，不需要再抛。

标准方程模板：

这里的 1 是“当前必须先做一步”的成本：

• 抛硬币题：先抛 1 次。
• 随机游走题：先走 1 步。
• 骰子题：先掷 1 次。
• 如果每步成本不是 1，就把这个 1 换成对应成本。

为什么右边会出现自己？

因为下一步可能回到同一个状态。例如 HH 题里，从 $S_0$ 抛出 T 后仍然没有进度，还是 $S_0$，所以方程里会出现：

这不是循环定义错误，而是递归方程。含义是“有一半概率白抛一次，回到起点”，然后通过代数把 $E_0$ 解出来。

状态怎么选？

对“直到出现某个序列”的题，状态通常是：

当前历史的末尾，和目标序列的前缀匹配了多长。

目标 HH：

• $S_0$：末尾没有匹配任何前缀
• $S_1$：末尾匹配 H

目标 HHH：

• $S_0$：末尾没有连续 H
• $S_1$：末尾匹配 H
• $S_2$：末尾匹配 HH

目标 THH：

• $S_0$：末尾没有匹配 THH 的任何非空前缀
• $S_1$：末尾匹配 T
• $S_2$：末尾匹配 TH

两类常见题

例题

题目42：连续 HH 的期望 ⭐⭐⭐（详见题目 14，此处补充 Markov Chain 视角） ↑ 返回 list

反复抛公平硬币，第一次出现连续两个正面 HH 的期望抛掷次数是多少？如果目标是 HT 或 HHH 呢？

答案：

HH 的状态方程：

定义：

• $S_0$：当前没有任何对 HH 有用的进度。也就是说，当前历史末尾不是 H。例如空序列、T、HTT 都属于 $S_0$。
• $S_1$：当前历史末尾已经有 1 个 H，可以作为 HH 的第一个 H。例如 H、TH、TTH 都属于 $S_1$。
• 完成：已经出现 HH。

对应的期望变量：

• $E_0$：处于 $S_0$ 时，从现在开始到第一次出现 HH 还需要的期望抛掷次数。
• $E_1$：处于 $S_1$ 时，从现在开始到第一次出现 HH 还需要的期望抛掷次数。
• 完成状态的期望是 0。

注意：$E_0$ 不是“第 0 次抛掷的期望”，而是“没有进度这个状态的期望剩余步数”。

从 $S_0$ 出发：

逐项解释：

• 左边 $E_0$：从没有进度的状态出发，还需要多少期望步。
• 右边的 $1$：无论如何，下一步都要先抛 1 次硬币。
• $\frac12E_1$：如果抛出 H，概率 $1/2$，历史末尾变成 H，进入 $S_1$，后续还需要 $E_1$ 步。
• $\frac12E_0$：如果抛出 T，概率 $1/2$，仍然没有任何 HH 前缀进度，回到 $S_0$，后续还需要 $E_0$ 步。

所以这句话完整读作：

从 $S_0$ 开始，先花 1 次抛掷；之后一半概率进入 $S_1$，一半概率回到 $S_0$。

从 $S_1$ 出发：

逐项解释：

• 左边 $E_1$：从“已经有一个 H”的状态出发，还需要多少期望步。
• 右边的 $1$：下一步仍然要先抛 1 次。
• $\frac12\cdot0$：如果抛出 H，形成 HH，已经完成，后续期望是 0。
• $\frac12E_0$：如果抛出 T，原来的 H 被打断，末尾不是 H，回到 $S_0$。

解方程：

代入：

HT 的状态方程：

定义：

• $S_0$：当前历史末尾没有 H，不能作为 HT 的开头。
• $S_1$：当前历史末尾是 H，已经匹配目标 HT 的第一个字符，等待 T。
• $E_0$：处于 $S_0$ 时，到第一次出现 HT 还需要的期望抛掷次数。
• $E_1$：处于 $S_1$ 时，到第一次出现 HT 还需要的期望抛掷次数。

解释：从 $S_0$ 出发，先抛 1 次；抛 H 进入 $S_1$，抛 T 仍在 $S_0$。

解释第二式：

• 从 $S_1$ 出发，先抛 1 次。
• 如果抛 T，形成 HT，完成，后续是 0。
• 如果抛 H，没有完成 HT，但最后一个字符仍然是 H，所以仍停留在 $S_1$，不是回到 $S_0$。

这就是 HH 和 HT 的差别：

• HH 在状态 H 下抛出 T，会回到 $S_0$。
• HT 在状态 H 下抛出 H，仍然保留一个 H，留在 $S_1$。

由第二式得 $E_1 = 2$，代入第一式得：

HHH 的状态方程：

定义：

• $S_0$：当前末尾没有连续 H 的进度。
• $S_1$：当前末尾是 H，已经匹配 HHH 的第一个 H。
• $S_2$：当前末尾是 HH，已经匹配 HHH 的前两个 H。
• $E_0$：处于 $S_0$ 时，到第一次出现 HHH 还需要的期望抛掷次数。
• $E_1$：处于 $S_1$ 时，到第一次出现 HHH 还需要的期望抛掷次数。
• $E_2$：处于 $S_2$ 时，到第一次出现 HHH 还需要的期望抛掷次数。

解释：从无进度开始，抛 H 进入 $S_1$，抛 T 留在 $S_0$。

解释：已有 H 时，抛 H 进入 HH 状态 $S_2$；抛 T 打断连续 H，回到 $S_0$。

解释：已有 HH 时，抛 H 完成 HHH；抛 T 打断连续 H，回到 $S_0$。

解得：

面试关键： HH 比 HT 更久，是因为 HH 有“自我重叠”的问题：在状态 H 下抛出 T 会把进度清零；而 HT 在状态 H 下抛出 H 仍然保留一个 H 的进度。

题目43：Two Sigma 面经 — 交替序列 ⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经（出现 2 次）

从 $[0,1]$ 中依次随机取 $x_1, x_2, x_3, \ldots$，要求交替：$x_1 > x_2 < x_3 > x_4 < x_5 \ldots$。模式被打破时停止。平均能取几个数？

答案：

若第一个比较方向固定为 $x_1 > x_2 < x_3 > \cdots$，则

这里 $N$ 表示停止前成功取到的数字个数。

解法：

第 1 步：先定义 $N$ 和 $N \geq n$

$N$ 是停止前成功取到的数字个数。

• $N \geq 1$：至少取到第 1 个数，这一定成立。
• $N \geq 2$：前 2 个数满足 $x_1 > x_2$。
• $N \geq 3$：前 3 个数满足 $x_1 > x_2 < x_3$。
• $N \geq n$：前 $n$ 个数都还没有打破交替模式。

所以：

第 2 步：用尾和公式把期望拆开

这个公式的直觉是：如果某次实验里 $N=4$，那么它会给下面四层各贡献一次：

所以尾概率一层一层加起来，平均就是成功个数的期望。

第 3 步：计算 $P(N \geq n)$

因为 $x_1,\ldots,x_n$ 是 iid 连续分布，所以它们几乎不会相等；真正重要的不是具体数值，而是相对排名。

前 $n$ 个数的相对排名一共有 $n!$ 种，并且等可能。

令：

也就是说，$A_n$ 数的是：在全部 $n!$ 种相对排名里，有多少种长得像“高低高低”的交替形状。

因此：

注意：$A_n$ 不是随机变量，也不是概率；它只是一个计数。

前几项：

例如 $n=3$ 时，要求：

三个数一共有 $3!=6$ 种相对排名。满足 $x_2$ 比左右两边都小的有 2 种，所以：

第 4 步：为什么会出现 $\sec$ 和 $\tan$

$A_n$ 是标准数列，叫 Euler zigzag number / up-down number。它通常没有像 $2^n$、$n!$ 那样简单的初等通项，但有标准 exponential generating function。

为了避免和题目里的随机数 $x_1,x_2,\ldots$ 混淆，把生成函数变量写成 $t$：

这里的 $t$ 不是随机变量，只是一个占位符，用来标记第 $n$ 项。

展开看就是：

我们已经推到：

这个式子里没有额外权重，只是把每一项 $\frac{A_n}{n!}$ 原样相加。因此令 $t=1$，因为 $1^n=1$：

如果令 $t=2$，得到的是：

这会把第 $n$ 项额外乘上 $2^n$，不是本题的期望。

第 5 步：为什么最后要减 $1$

生成函数从 $n=0$ 开始：

但尾和公式从 $n=1$ 开始：

多出来的是 $n=0$ 项：

这里 $A_0=1$ 的意思是：0 个元素的空排列有 1 种；因为没有任何相邻比较需要违反，所以从逻辑上算作满足交替关系。

这个 $1$ 对应的是尾和里的 $P(N\geq 0)=1$，不是“长度 0 对期望贡献 1”。普通期望公式里长度 0 的贡献确实是 $0\cdot P(N=0)=0$；但这里用的是尾和公式，所以要去掉多出来的第 0 层事件。

因此：

常见疑惑：

• $A_n$ 到底是什么？
  $A_n$ 是一个计数：$n!$ 种相对排名里，有多少种满足 $x_1>x_2x_4<\cdots$。它不是概率，概率是 $A_n/n!$。

• $A_n$ 有通项公式吗？
  它是标准数列 Euler zigzag number，常用递推或生成函数表示；面试里通常记住生成函数即可：

  \[\sum_{n=0}^{\infty}A_n\frac{t^n}{n!}=\sec t+\tan t\]

• 生成函数里的 $t$ 是什么？
  $t$ 只是占位变量，不是题目里的 $x_i$。它用来把所有 $A_n$ 打包进一个函数。

• 为什么代入 $t=1$？为什么不代入 $t=2$？
  因为题目需要 $\sum A_n/n!$，也就是每项原样相加。代入 $t=1$ 后 $t^n=1$；代入 $t=2$ 会把第 $n$ 项额外乘 $2^n$，变成另一个量。

• 为什么减 $1$？
  因为生成函数包含 $n=0$ 项 $\frac{A_0}{0!}=1$，而尾和公式从 $n=1$ 开始。减掉的是多出来的 $P(N\geq 0)=1$，不是长度 0 的期望贡献。

举一反三：

这类题的核心模板是：

然后把：

翻译成“前 $n$ 个数满足某种大小关系的概率”。由于 iid 连续，所以只需要数相对排名：

1. 连续递减

   若要求：

   \[x_1>x_2>x_3>\cdots\]

   则 $N\geq n$ 意味着前 $n$ 个数严格递减。在 $n!$ 种排序里，只有 1 种满足：

   \[P(N\geq n)=\frac{1}{n!}\]

   所以：

   \[E[N]=\sum_{n\geq 1}\frac{1}{n!}=e-1\]

2. 交替方向不固定

   如果题目说只要交替即可，既可以：

   \[x_1>x_2<x_3>x_4<\cdots\]

   也可以：

   \[x_1<x_2>x_3<x_4>\cdots\]

   那么对 $n\geq 2$，两种方向都要数：

   \[P(N\geq n)=\frac{2A_n}{n!}\]

   但 $n=1$ 时不能乘 2，因为只有一个数时没有方向，仍然是 $P(N\geq 1)=1$。

3. 任意指定形状

   如果题目要求：

   \[x_1<x_2<x_3>x_4\]

   就不用先想积分，而是数 4 个数的相对排名。总共有 $4!=24$ 种，只要数出有多少种满足 $x_1<x_2<x_3$ 且 $x_3>x_4$，再除以 24。

一句话记： 这类题不是先做积分，而是先把事件翻译成“相对排名计数”。尾和公式负责把“能撑到第 $n$ 个”的概率加成期望。

易错点： $e$ 常出现在“连续递减/递增直到失败”的题里，因为 $P(N \geq n)=1/n!$，所以期望是 $\sum 1/n!$。本题是交替排列，不是单调排列，因此答案不是 $e$。

题目44：天气预报 Markov Chain ⭐⭐⭐ ↑ 返回 list

晴天 → 80% 晴 20% 雨。雨天 → 40% 晴 60% 雨。

问题 1： 今天晴，后天晴的概率是多少？

问题 2： 长期来看，晴天比例是多少？

答案：

• 后天晴概率：$0.72$
• 长期晴天比例：$2/3$

解法：

转移矩阵写成：

其中第一行/列代表晴，第二行/列代表雨。

两步概率：

今天晴，后天晴有两条路径：

• 晴 $\to$ 晴 $\to$ 晴：概率 $0.8 \times 0.8$
• 晴 $\to$ 雨 $\to$ 晴：概率 $0.2 \times 0.4$

所以：

稳态：

设 $p$ = 长期晴天概率，则长期雨天概率是 $1-p$。稳态要求“明天晴的概率仍然是 $p$”：

面试关键： 两步概率用路径枚举或矩阵平方；长期概率用 stationary distribution，即 $\pi P = \pi$。

举一反三：

先固定状态顺序，比如 $[\text{晴}, \text{雨}]$。本题采用“行是今天状态，列是明天状态”的约定：

所以行列表示状态，时间体现在矩阵乘了几次。

1. 今天状态确定，问 $n$ 天后状态

   如果今天是状态 $i$，问 $n$ 天后是状态 $j$：

   \[P(n\text{ 天后是 }j \mid \text{今天是 }i)=(P^n)_{ij}\]

   例如今天晴，问 3 天后晴：

   \[P(\text{3 天后晴}\mid \text{今天晴})=(P^3)_{\text{晴},\text{晴}}\]

2. 今天不是确定状态，而是一个概率分布

   如果今天有 $70\%$ 晴、$30\%$ 雨，则初始分布是：

   \[\pi_0=(0.7,0.3)\]

   明天分布：

   \[\pi_1=\pi_0P\]

   后天分布：

   \[\pi_2=\pi_0P^2\]

   一般地：

   \[\pi_n=\pi_0P^n\]

   这种题不要只取矩阵某一行，而是用“初始分布向量 $\times$ 转移矩阵”。

3. 长期比例

   长期比例不是看某一天，而是找稳定分布：

   \[\pi=\pi P,\qquad \sum_i \pi_i=1\]

   在两状态题里，可以设长期晴天概率为 $p$，长期雨天概率为 $1-p$，然后列：

   \[p=0.8p+0.4(1-p)\]

4. 如果转移概率随时间变化

   本题默认每天规则一样，所以两天后可以用 $P^2$，$n$ 天后可以用 $P^n$。

   但如果题目说“工作日一套概率，周末一套概率”，或者“第一天、第二天的转移概率不同”，就不能用 $P^n$，而要按时间顺序相乘：

   \[P_{\text{今天到明天}}P_{\text{明天到后天}}\cdots P_{\text{第 }n-1\text{ 天到第 }n\text{ 天}}\]

   也就是：

   • 转移规则不变：用 $P^n$
   • 转移规则每天变：用 $P_1P_2\cdots P_n$

一句话记： 状态是行列，时间是矩阵乘法推进。

题目45：Two Sigma 面经 — 两箱球 ⭐⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经

A、B 两箱各 $n$ 个球。每次随机选一箱取一个球。如果选到的箱子是空的就停止。另一箱期望剩多少球？

答案：

按题面文字理解：选到“已经空了”的箱子时才停止。设 $R$ 为停止时另一箱剩余球数，则：

精确表达式可以写成：

当 $n$ 很大时：

其中 $R$ 是停止时另一箱剩余球数。

解法：

第 1 步：把过程翻译成 A/B 序列

把“选 A 箱”看成一次 A，把“选 B 箱”看成一次 B。每一步独立，A/B 各概率 $1/2$。

注意题目说的是“选到空箱才停止”，所以某箱被取完的那一步还不是停止；之后如果一直选另一箱，还可以继续取，直到下一次选到这个空箱才停止。

第 2 步：固定一种停止方式

先假设最后是因为选到空的 A 箱而停止，并且此时 B 箱还剩 $r$ 个球。

停止前，也就是最后一次选到空 A 之前，已经发生了：

• A 箱被成功选了 $n$ 次，所以 A 已经空了；
• B 箱被成功选了 $n-r$ 次，所以 B 还剩 $r$ 个球；
• 最后一步又选到 A，发现 A 已经空了，于是停止。

所以最后一步之前，一共有：

次成功选择。

这 $2n-r$ 次成功选择中，需要有：

• $n$ 次 A；
• $n-r$ 次 B。

这一步用的是组合数：在 $2n-r$ 个位置里选出哪 $n$ 个位置是 A。A 的位置一旦选定，剩下的位置自动都是 B，所以这也等价于数合法的 A/B 序列条数。

合法 A/B 序列数为：

每一种具体 A/B 序列的概率是：

这里指数是 $2n-r+1$，因为还有最后那一次“选到空 A”的停止步骤。

因此，“指定 A 箱为空箱并触发停止，且 B 箱剩 $r$ 个”的概率是：

第 3 步：A 或 B 都可能是空箱

A、B 对称。最后可能是选到空 A 停止，也可能是选到空 B 停止，所以乘以 2：

其中 $r=0$ 表示两箱都已经取空后，下一次无论选 A 还是 B 都会停止。它有概率，但对 $E[R]$ 没有贡献。

于是：

第 4 步：用 $n=2$ 检查公式

每箱 2 个球。

• $R=2$：连续选同一个箱 3 次，例如 AAA 或 BBB。概率 $=2/8=1/4$。
• $R=1$：比如 A 箱触发停止，停止前的成功序列有 2 个 A、1 个 B，可以是 AAB、ABA、BAA，然后最后再选 A 停止。A 触发有 3 条，B 触发也有 3 条，所以概率 $=6/16=3/8$。
• $R=0$：前 4 次刚好把 A、B 都取空，然后下一次停止。概率 $=\binom{4}{2}/16=3/8$。

所以：

代入公式也得到：

第 5 步：大 $n$ 时为什么是 $\sqrt{n}$ 量级

两箱被选次数的差距像对称随机游走。走了大约 $2n$ 步后，典型偏差是 $\sqrt{n}$ 量级，所以另一箱剩余数也应该是 $\sqrt{n}$ 量级。

更精确地，用局部中心极限定理近似：

于是：

易错点： 不要把“某箱刚好被取空”误当成停止。题目是“选到空箱才停止”，所以某箱被取空之后，还可能继续选另一箱若干次，直到再次选到空箱才停。比如 $n=2$ 时，路径 AABA 是合法的：AA 后 A 已空，接着选 B 还能继续，最后再选 A 才停止。

题目46：Two Sigma 面经 — 非对称随机游走吸收步数 ⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经

起点为 1 的非对称随机游走（$P(\text{右}) = p > 1/2$），0 处有吸收壁。被吸收时期望走了多少步？

答案：

这里要区分两个量：

• 无条件吸收时间期望：当 $p \geq 1/2$ 时是无穷大，因为有正概率永远不 hit 0；当 $p<1/2$ 时为 $1/(1-2p)$。
• 条件在最终会 hit 0 的情况下，吸收时间期望：当 $p>1/2$ 时为

解法（条件版本）：

令 $q=1-p$。从 1 出发，向右漂移时，hit 0 的概率不是 1，而是：

在条件事件“最终 hit 0”下，路径等价于一个向左漂移的随机游走：向左概率变成 $p$，向右概率变成 $q$。这是 Doob h-transform 的直观版本。

于是每一步的平均位移是：

从 1 走到 0，需要平均下降 1 个单位。用 Wald intuition：

所以：

如果 $p<1/2$：

这时向左漂移，最终一定 hit 0。

定义：

这里的下标 $i$ 是当前位置，不是第 $i$ 步。例如 $E_3$ 表示“现在在位置 3，还要多少期望步到 0”。

从位置 $i$ 出发，下一步一定先走 1 步：

逐项解释：

• 左边 $E_i$：从位置 $i$ 到 0 的期望剩余步数。
• 右边的 $1$：下一步行走本身消耗 1 步。
• $pE_{i+1}$：以概率 $p$ 向右走到 $i+1$，之后还需要 $E_{i+1}$ 步。
• $qE_{i-1}$：以概率 $q$ 向左走到 $i-1$，之后还需要 $E_{i-1}$ 步。
• 边界是 $E_0=0$，因为已经 hit 0。

由于每步平均向左漂移 $q-p>0$，解会是线性的。猜线性解 $E_i = ci$：

代入 $E_i=ci$：

所以：

面试关键： 如果题目说 $p>1/2$ 且问“被吸收时期望”，需要主动澄清是无条件还是条件期望。无条件期望是无穷大；$1/(2p-1)$ 是“给定最终被吸收”的条件期望。

题目47：Two Sigma 面经 — 掷骰子和超过 63 ⭐⭐ ↑ 返回 list

来源： Two Sigma 面经

反复掷骰子直到总和超过 63。最后一次不超过 63 的数（即 58-63 中的某个值）的分布是什么？

答案：

不是均匀分布。对阈值 63 来说，它已经非常接近下面这个线性分布：

精确值和这些数只差很小。

解法：

第 1 步：先定义过程和停止时间

设：

• $S_t$ = 掷完第 $t$ 次后的总和，且 $S_0=0$；
• $T$ = 第一次让总和超过 63 的掷骰次数；
• $L=S_{T-1}$ = 最后一次不超过 63 的总和。

题目问的是 $L$ 的分布。

因为骰子最大只能加 6，所以 $L$ 只能是：

原因是：如果最后一次不超过 63 的总和还小于等于 57，那么下一次最多加 6，只能到 63，不能超过 63。

第 2 步：定义 $u_j$，它不是最终答案，只是中间工具

设：

注意：$u_j$ 不是“最后停在 $j$ 的概率”。它只是“有没有经过 $j$”的概率。

因为总和只会增加，所以要恰好到达 $j$，最后一次掷出的点数只能是 $1,\ldots,6$ 中的某个 $d$，并且上一步必须在 $j-d$。

因此：

其中 $u_k=0$ for $k<0$。

例如：

表示只有第一下掷出 1 才能到达 1。

表示到达 2 有两类方式：直接掷出 2，或者先到 1 再掷出 1。

第 3 步：把“最后停在 $j$”拆成两件事

如果 $L=j$，也就是最后一次不超过 63 的数是 $j$，那么必须同时满足：

1. 过程先曾经到达 $j$；
2. 下一次掷骰子直接让总和超过 63。

第一件事的概率是 $u_j$。

第二件事看 $j$ 离 63 有多近：

所以：

这就是精确公式。真正难的是 $u_j$ 不太好直接心算。

第 4 步：为什么 $u_j\approx 2/7$

对很大的 $j$，$u_j$ 会趋近一个常数：

骰子一次的平均点数是：

所以：

直觉：总和平均每次向前跳 $3.5$ 格，所以在很远的地方，大约每 $3.5$ 个整数点会命中 1 个；因此命中某个指定整数点的概率约是 $1/3.5=2/7$。

对本题的 $j=58,\ldots,63$，这个近似已经非常准。

也就是说，对普通骰子而言：

更一般地，当 $k$ 比较大时：

这里的“出现过”就是“曾经恰好命中”，不是“最后停在”。

补充例子：为什么是平均步长的倒数

先看一个更小的例子：每次只加 $1$ 或 $2$，各概率 $1/2$。

平均步长是：

所以远处某个整数点被命中的概率趋近：

对应递推是：

前几项：

这些数会震荡，但长期会靠近 $2/3$。

再看一个容易混淆的例子：每次只加 $0$ 或 $1$，各概率 $1/2$。

平均步长是：

于是：

但这不能表示“命中某个点的概率是 2”，因为概率不能超过 1。这里的意思变成：每个整数点平均会被访问约 2 次。

原因是有可能原地不动：

所以同一个点可以被重复访问。只要时间一直进行，最终会到达每个整数点：

因此要区分：

• 如果每次步长都至少是 1，累计和严格增加，同一个整数点最多被访问一次；这时 $\frac{1}{\mu}$ 就是远处单点的命中概率。
• 如果步长允许 0，累计和可能原地停留，同一个整数点可以被访问多次；这时 $\frac{1}{\mu}$ 是平均访问次数，不是命中概率。

第 5 步：代回去得到近似分布

因为：

并且：

所以：

于是：

注意这六项加起来刚好是：

第 6 步：精确值确实很接近

用递推精确算到 $u_{63}$，得到：

所以面试里通常说“近似为 $1:2:3:4:5:6$ 的线性分布”，已经足够。

直觉： 越靠近 63，越容易下一掷就超过 63。站在 63 时，任何点数都会超过；站在 58 时，只有掷出 6 才会超过。所以 63 的概率约是 58 的 6 倍。

面试易错点：

• 不要把 $u_j$ 当成最终答案。$u_j$ 只是“曾经到达 $j$”的概率，最后还要乘上“下一步超过 63”的概率。
• “总和 mod 6 近似均匀”不等于“最后停在 58-63 均匀”。停止事件还要乘上“下一步跨过阈值”的概率，这个概率从 $1/6$ 到 $1$ 递增。

题目48：Two Sigma 面经 — 9 cats 8 dogs ⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经

9 只猫和 8 只狗随机排成一排（17 个位置）。相邻不同物种的对数的期望？

答案：

解法： 用 Linearity of Expectation。

第 1 步：定义指标变量

定义 $I_k$ = 位置 $k$ 和位置 $k+1$ 是不同物种（$k = 1, \ldots, 16$）。

总共有 16 对相邻位置：

所以：

这不是近似，也不是概率技巧，而是逐项数数。每一对相邻位置：

• 如果不同物种，对应的 $I_k=1$，给总数贡献 1；
• 如果相同物种，对应的 $I_k=0$，给总数贡献 0。

例如某一段排列是：

三对相邻位置分别是：

对应指标是：

所以这段里相邻不同物种的对数就是：

17 个位置时也是同理，只是有 16 对相邻位置。

由期望线性性：

这里不要求 16 个 $I_k$ 独立。期望线性性永远成立：

而 $I_k$ 是 0/1 指标变量，所以：

因为每一对相邻位置的概率都一样，所以只需要算一对，例如位置 $k,k+1$。

第 2 步：算一对相邻位置不同的概率

位置 $k,k+1$ 不同，有两种有序情况：

1. 第一个位置是猫，第二个位置是狗；
2. 第一个位置是狗，第二个位置是猫。

这两种情况不可能同时发生，所以它们是互斥事件。因此：

先算猫狗：

解释：

• 第一个位置是猫：17 只动物里有 9 只猫，所以概率 $9/17$；
• 第一个位置已经放了一只猫后，还剩 16 只动物，其中狗仍有 8 只，所以第二个位置是狗的概率 $8/16$。

再算狗猫：

所以：

第 3 步：乘上 16 对相邻位置

组合数校验：

也可以固定位置 $k,k+1$，用“选狗的位置”来算。

总排列等价于在 17 个位置里选 8 个位置放狗：

如果位置 $k$ 是猫、位置 $k+1$ 是狗，那么剩下 15 个位置里还要放 7 只狗：

所以：

狗猫同理，所以不同物种概率仍然是：

Indicator 设法模板：

遇到“某种东西的个数/次数/对数的期望”，优先想：

关键是先找清楚“基本单位”是什么。

本题问的是“有几对相邻位置不同”，所以基本单位是相邻对：

因此设：

不是设 $k-1,k,k+1$，因为那是三个连续位置的窗口；只有当题目问“三个连续位置满足某种形状的个数”时，才应该用三元组窗口。

另外，$I_k$ 和 $I_{k+1}$ 会共用第 $k+1$ 个位置，所以它们确实不独立。但这不影响：

因为期望线性性不要求独立。

举一反三：

1. 10 个红球、10 个蓝球，问相邻颜色不同的对数期望

   基本单位仍然是相邻对。20 个位置有 19 对相邻位置。

   固定一对，颜色不同的概率是：

   \[P(\text{不同})=\frac{10}{20}\cdot\frac{10}{19}+\frac{10}{20}\cdot\frac{10}{19}=\frac{10}{19}\]

   所以：

   \[E=19\cdot\frac{10}{19}=10\]

   注意不是 20；前面括号里的概率已经是 $10/19$。

2. 9 猫 8 狗，问有多少个三连窗口是 猫-狗-猫

   这时基本单位变成三个连续位置的窗口：

   \[J_k=\mathbf{1}_{\{\text{第 }k-1,k,k+1\text{ 个位置是 猫-狗-猫}\}},\qquad k=2,\ldots,16\]

   一共有 15 个三连窗口。固定一个窗口：

   \[P(\text{猫-狗-猫})=\frac{9}{17}\cdot\frac{8}{16}\cdot\frac{8}{15}\]

   所以：

   \[E=15\cdot\frac{9}{17}\cdot\frac{8}{16}\cdot\frac{8}{15}=\frac{36}{17}\]

   如果题目问“两边同物种、中间不同物种”，那还要加上“狗-猫-狗”这一种形状。

易错点：

• 这里的 $\frac{9}{17}\cdot\frac{8}{16}$ 只算了“猫狗”，还要加上“狗猫”。
• 不能把 16 对相邻位置当成独立事件；但求期望不需要独立性，只需要期望线性性。
• Indicator 的下标范围由“基本单位”决定：相邻对是 $k,k+1$；三连窗口才是 $k-1,k,k+1$。

扩展知识点：转移矩阵与状态分类

转移矩阵形式定义

设 Markov Chain 的状态空间为 ${1, 2, \ldots, n}$，转移概率矩阵为：

其中 $p_{ij} = P(\text{从状态}i\text{转移到状态}j\text{在一步内})$，且 $\sum_j p_{ij} = 1$。

状态分类

• 可达（Accessible）： 从状态 $i$ 可达到状态 $j$（记作 $i \to j$）意味着存在 $n \geq 0$ 使得 $P^n_{ij} > 0$。
• 通信（Communicating）： 两个状态互相可达（$i \leftrightarrow j$ 当 $i \to j$ 且 $j \to i$）。

• 常返（Recurrent）： 状态 $i$ 常返当 $P(\text{有限时间内回到}i

  \text{从}i\text{开始}) = 1$。

• 瞬时（Transient）： 状态 $i$ 瞬时当从 $i$ 出发，最终以概率 1 永远不再返回。

吸收 Markov Chain（Absorbing Markov Chains）

一个状态是吸收状态如果 $p_{ii} = 1$（进去就出不来）。含有吸收状态的链叫吸收链。

吸收概率方程：

设 $a_i$ = 从状态 $i$ 出发，最终被某个特定吸收状态吸收的概率。则：

• 如果 $i$ 是该吸收状态：$a_i = 1$
• 如果 $i$ 是其他吸收状态或已吸收：$a_i = 0$
• 如果 $i$ 是瞬时状态：$a_i = \sum_j p_{ij} \cdot a_j$（基于一步转移加权平均）

吸收期望时间：

设 $\mu_i$ = 从状态 $i$ 出发，被吸收的期望步数。则：

• 如果 $i$ 是吸收状态：$\mu_i = 0$
• 如果 $i$ 是瞬时状态：$\mu_i = 1 + \sum_j p_{ij} \cdot \mu_j$

这是因为每一步花 1 个时间单位，然后随机转移到下一个状态。

题目48a：骰子 12 vs 连续 7-7（Dice Battle）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.1

两个玩家轮流掷两个骰子：

• 玩家 A 赌两个骰子之和为 12 先出现。
• 玩家 B 赌两个连续 7 先出现（一次 7，然后下一次又是 7）。

$P(\text{A 赢}) = 7/13$。求解及策略分析。

答案： $P(\text{A 赢}) = 7/13 \approx 0.538$

解法（绿皮书，吸收 Markov Chain）：

定义状态：

• $S$：开始，或上一次掷出既不是 12 也不是 7 的结果
• $7$：上一次恰好掷出一个 7
• $A$：A 赢（掷出 12）
• $B$：B 赢（掷出连续两个 7）

定义概率变量：

• $a_S$：当前处于状态 $S$ 时，A 最终赢的概率。
• $a_7$：当前处于状态 $7$ 时，A 最终赢的概率。

注意：$a_S,a_7$ 是吸收概率，不是期望步数。所以方程没有 1 + ...。如果问“还要多少期望次掷骰子才结束”，才会写成 $\mu_i=1+\sum p_{ij}\mu_j$。

转移概率（每次掷两个骰子）：

• $P(\text{和} = 12) = 1/36$（只有 6+6）
• $P(\text{和} = 7) = 6/36 = 1/6$（(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)）
• $P(\text{其他}) = 29/36$

从状态 $S$ 出发： \(a_S = \frac{1}{36} \cdot 1 + \frac{6}{36} \cdot a_7 + \frac{29}{36} \cdot a_S\)

逐项解释：

• 左边 $a_S$：没有挂起的 7 时，A 最终赢的概率。
• $\frac{1}{36}\cdot1$：下一次掷出 12，A 立刻赢，A 赢概率为 1。
• $\frac{6}{36}a_7$：下一次掷出 7，进入“已有一个 7”的状态，后续 A 赢概率是 $a_7$。
• $\frac{29}{36}a_S$：下一次既不是 12 也不是 7，仍然没有挂起进度，回到 $S$。

整理：$a_S - \frac{29}{36}a_S = \frac{1}{36} + \frac{6}{36}a_7$

从状态 $7$ 出发（已有一个 7）： \(a_7 = \frac{1}{36} \cdot 1 + \frac{6}{36} \cdot 0 + \frac{29}{36} \cdot a_S\)

解释：

• 左边 $a_7$：当前已经有一个挂起的 7 时，A 最终赢的概率。
• $\frac{1}{36}\cdot1$：下一次掷出 12，A 赢。
• $\frac{6}{36}\cdot0$：下一次掷出 7，B 完成连续两个 7，A 输。
• $\frac{29}{36}a_S$：下一次掷出其他点数，挂起的 7 被打断，回到状态 $S$。

求解：

由 $(*)$：

由 $(**)$：

把 $a_7 = (1+29a_S)/36$ 代入第一式：

两边乘 6：

所以：

面试中说： “我把问题转换成吸收 Markov Chain，只需要追踪上一次是不是 7。状态 $S$ 表示没有挂起的 7，状态 $7$ 表示已经有一个 7。然后对 A 赢概率列方程。关键是从状态 $7$ 出发时，下一次 7 是 B 赢，下一次 12 才是 A 赢。”

题目48b：硬币三连（HHH vs THH）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.1

反复掷硬币，一直掷到出现 HHH（三个连续正面）或 THH（一个反面接两个正面）。

Part A： 每个序列出现的期望步数？$E[\text{HHH}] = ?$，$E[\text{THH}] = ?$

Part B： $P(\text{HHH 先出现}) = ?$

Part C： 哪个序列更容易先出现？是否存在非传递性？

答案：

• Part A：$E[\text{HHH}] = 14$，$E[\text{THH}] = 8$
• Part B：$P(\text{HHH 先出现}) = 1/8 = 0.125$
• Part C：THH 总是赢（非对称，THH 优于 HHH）

解法（Part A，期望步数用状态方程）：

对 HHH，定义状态：

• $S_0$：当前历史末尾没有连续 H 的进度。例如空序列、T、HT。
• $S_1$：当前历史末尾是 H，已经匹配 HHH 的第一个 H。
• $S_2$：当前历史末尾是 HH，已经匹配 HHH 的前两个 H。
• $HHH$：完成

对应期望：

• $E_0$：处于 $S_0$ 时，到第一次出现 HHH 还需要的期望抛掷次数。
• $E_1$：处于 $S_1$ 时，到第一次出现 HHH 还需要的期望抛掷次数。
• $E_2$：处于 $S_2$ 时，到第一次出现 HHH 还需要的期望抛掷次数。
• 完成状态的期望是 0。

方程： \(E_0 = 1 + \frac{1}{2}E_1 + \frac{1}{2}E_0\) \(E_1 = 1 + \frac{1}{2}E_2 + \frac{1}{2}E_0\) \(E_2 = 1 + \frac{1}{2} \times 0 + \frac{1}{2}E_0\)

逐项解释：

• $E_0$ 方程：从无进度开始，先抛 1 次；抛 H 进入 $S_1$，抛 T 仍是 $S_0$。
• $E_1$ 方程：已有 H，先抛 1 次；抛 H 进入 $S_2$，抛 T 打断连续 H，回到 $S_0$。
• $E_2$ 方程：已有 HH，先抛 1 次；抛 H 完成 HHH，后续是 0；抛 T 打断连续 H，回到 $S_0$。

从第三个方程：$E_2 = 1 + \frac{1}{2}E_0$

代入第二个：$E_1 = 1 + \frac{1}{2}(1 + \frac{1}{2}E_0) + \frac{1}{2}E_0 = 1.5 + \frac{3}{4}E_0$

代入第一个：$E_0 = 1 + \frac{1}{2}(1.5 + \frac{3}{4}E_0) + \frac{1}{2}E_0 = 1.75 + \frac{7}{8}E_0$

对 THH，定义状态：

• $S_0$：当前历史末尾没有匹配 THH 的任何非空前缀。例如空序列、H、HH。
• $S_1$：当前历史末尾是 T，已经匹配 THH 的第一个字符。
• $S_2$：当前历史末尾是 TH，已经匹配 THH 的前两个字符。
• $THH$：完成

对应期望：

• $E_0$：处于 $S_0$ 时，到第一次出现 THH 还需要的期望抛掷次数。
• $E_1$：处于 $S_1$ 时，到第一次出现 THH 还需要的期望抛掷次数。
• $E_2$：处于 $S_2$ 时，到第一次出现 THH 还需要的期望抛掷次数。

方程： \(E_0 = 1 + \frac{1}{2}E_1 + \frac{1}{2}E_0\) \(E_1 = 1 + \frac{1}{2}E_2 + \frac{1}{2}E_1\) \(E_2 = 1 + \frac{1}{2}\cdot 0 + \frac{1}{2}E_1\)

解释：

• $E_0$ 方程：从无进度开始，先抛 1 次；抛 T 进入 $S_1$，抛 H 仍然不是 THH 的前缀，留在 $S_0$。
• $E_1$ 方程：已有 T，先抛 1 次；抛 H 进入 $S_2$；抛 T 后最后一个字符仍是 T，仍然匹配 THH 的第一个字符，所以留在 $S_1$。
• $E_2$ 方程：已有 TH，先抛 1 次；抛 H 完成 THH；抛 T 后当前末尾是 T，仍可作为下一轮 THH 的开头，所以回到 $S_1$，不是 $S_0$。

这一步最容易错：从 $S_2=TH$ 抛出 T，历史末尾是 T，所以状态是 $S_1$。状态只看“当前末尾和目标前缀能匹配多长”，不是看刚才失败了就一律回到 $S_0$。

解方程：

由第二式：

由第三式：

代入：

再由第一式：

所以：

Part B：吸收概率（HHH 先出现）

这里有一个很强的简化观察：

一旦在 HHH 出现之前出现过 T，那么 THH 一定会在 HHH 之前出现。

原因是：T 出现之后，如果未来第一次连续出现两个 H，那么这两个 H 前面最近的相关前缀就是 T，于是 THH 已经完成；而 HHH 需要三个连续 H，会比这晚一步。

因此 HHH 想先赢，唯一可能是开头前三次就是：

所以：

面试关键说法： “这是序列竞争问题。单独等待 HHH 的期望是 14，单独等待 THH 的期望是 8。竞争时更极端：HHH 只有在前三抛就是 HHH 时才先赢，所以概率是 $1/8$。关键是识别 T 对两个目标的不同影响：T 破坏 HHH 的进度，但它正好是 THH 的起点。”

题目48c：全同色期望步数（Color Balls）⭐⭐ ↑ 返回 list

来源： 绿皮书 5.1

$n$ 只球，初始每只球一种不同颜色（共 $n$ 种）。每一步：随机选两只球，把第一只球的颜色改成第二只球的颜色，然后放回。问直到所有球同一种颜色需要期望多少步？

答案： $E[\text{步数}] = (n-1)^2$

解法（反向追踪祖先 / coalescent）：

这题直接按“当前颜色数”做 Markov chain 会很麻烦，因为只知道颜色数不够，还需要知道每种颜色有多少只球。

更干净的方法是反向看“每只球当前颜色来自哪一个初始祖先”。

每一步操作是：

随机选两只不同的球，把第一只球的颜色改成第二只球的颜色。

从反向时间看，这等价于“第一只球的祖先线路并入第二只球的祖先线路”。也就是说，祖先线路数量会从 $k$ 减少到 $k-1$。

当当前还有 $k$ 条不同祖先线路时，每一步随机选一个有序球对。总共有：

个有序不同球对。

能让祖先线路合并的，是选中的两个球分别属于两条不同祖先线路。反向看，$k$ 条祖先线路之间有：

个有序线路对。

所以从 $k$ 条祖先线路减少到 $k-1$ 条的概率是：

等待这次合并的期望步数是：

从初始 $n$ 条祖先线路到最后 1 条，需要依次经历 $k=n,n-1,\ldots,2$：

利用：

得到：

小例子验证：

• $n=2$：一步就能全同色，$(2-1)^2=1$。
• $n=3$：期望是 $4$。

面试中说： “正向看颜色分布很复杂，反向看祖先线路会简单很多。初始有 $n$ 条祖先线，最终全同色等价于所有线路 coalesce 成 1 条。当有 $k$ 条线路时，下一步合并概率是 $k(k-1)/[n(n-1)]$，所以等待时间求和后 telescopes，得到 $(n-1)^2$。”

八、鞅与随机游走（Martingale & Random Walk）

知识点

Random Walk（随机游走）定义与性质

简单随机游走： $S_n = X_1 + X_2 + \cdots + X_n$，其中 $X_i$ 是 iid 随机变量，每个 $X_i = +1$（概率 $p$）或 $-1$（概率 $q = 1-p$）。

对称随机游走： 当 $p = q = 1/2$ 时，称为对称随机游走。

关键性质：

• $E[S_n] = n \cdot E[X_1] = n(p - q)$
• 对称游走：$E[S_n] = 0$
• $\text{Var}(S_n) = n \cdot \text{Var}(X_1) = 4npq$
• 对称游走：$\text{Var}(S_n) = n$

Martingale（鞅）定义

直觉： “公平游戏”。已知目前的值和历史，未来期望值就是现在的值。

Wald’s Equality（瓦尔德等式）

其中 $S_N = X_1 + \cdots + X_N$。

Optional Stopping Theorem（可选停止定理）

如果 ${Z_n}$ 是鞅，$N$ 是停止时间，在某些条件下（例如有界停止时间或衰减条件），有：

对于对称随机游走，这意味着 $E[S_N] = E[S_0] = 0$。

Reflection Principle（反射原理）

在二维平面上，从点 $(0, a)$ 出发到 $(n, b)$ 且触及 $x$ 轴的路径数，等于从 $(0, -a)$ 到 $(n, b)$ 的路径数。

用于计算首达概率和吸收时间。

例题

题目49a：Drunk Man on Bridge（酒鬼在桥上）⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.2 + Two Sigma + Citadel

一个酒鬼站在 100 米长的桥上，距离起点（$x=0$）17 米处。他每一步随机向前走 1 米（概率 50%）或向后走 1 米（概率 50%）。走到 100 米处他跌出桥外（正面结局），走到 0 米处也跌出桥外（不幸）。

问题 1： 他在位置 17 处，走到起点（$x=0$）之前到达终点（$x=100$）的概率是多少？

问题 2： 期望走多少步才能到达桥的某一端？

答案：

• 问题 1：$P(\text{到 0 前先到 100}) = \frac{17}{100} = 0.17$
• 问题 2：$E[\text{步数}] = 17 \times 83 = 1411$

解法（问题 1，鞅方法）：

第 1 步：先定义随机过程

令：

所以：

每一步要么向右走 1 米，要么向左走 1 米：

其中：

停止时间定义为：

也就是说，$N$ 是第一次走到桥的某一端所用的步数。

停止时的位置是：

第 2 步：定义要求的概率 $p$

令：

也就是“先到 100，而不是先到 0”的概率。

那么：

第 3 步：什么是鞅性质

鞅可以理解成“公平游戏”：已知现在的位置和过去所有历史，下一步的期望位置仍然等于现在的位置。

本题中，如果现在在位置 $x$，下一步：

• 概率 $1/2$ 到 $x+1$；
• 概率 $1/2$ 到 $x-1$。

所以下一步位置的条件期望是：

这就是 ${X_n}$ 是鞅的意思：

直觉：这个随机游走没有向左或向右的偏移，平均来说位置不会变。

第 4 步：为什么可以写 $E[X_N]=E[X_0]=17$

可选停止定理的直觉是：如果一个游戏是公平的，那么在合适条件下，按某个停止规则停下来，停止时的期望值仍然等于初始值。

本题桥长有限，酒鬼最终会到 0 或 100，所以可以用：

这里的 $X_N$ 是“停止时的位置”，不是第 $n$ 步的位置。停止时它只可能是 0 或 100。

第 5 步：为什么 $E[X_N]=100p$

因为停止时：

• 以概率 $p$，$X_N=100$；
• 以概率 $1-p$，$X_N=0$。

所以 $X_N$ 是一个只取两个值的随机变量。它的期望是：

又因为鞅给出：

所以：

因此：

直觉： 如果从 50 米处开始，左右对称，先到 100 的概率应该是 $1/2$；如果从 17 米处开始，离 0 更近，所以先到 100 的概率只有 $17/100$。

解法（问题 2，二次鞅方法）：

第 1 步：为什么用 $X_n^2-n$

只用 $X_n$ 这个鞅，可以算“先到 100 的概率”；但要算“平均走多少步”，需要一个包含步数 $n$ 的鞅。

对称随机游走有一个标准二次鞅：

它的意思是：虽然 $X_n^2$ 通常会随着随机游走扩散而变大，但平均每走一步，$X_n^2$ 增加 1；所以减去 $n$ 后又变成公平量。

验证一下。如果现在 $X_n=x$，下一步：

所以：

这说明：

是鞅。

第 2 步：停止后期望仍然等于初始值

由可选停止定理：$E[M_N] = E[M_0]$，即 $E[X_N^2 - N] = E[X_0^2 - 0]$。

第 3 步：计算 $E[X_N^2]$

游走停止时仍然只有两种可能：

• 以概率 $p=17/100$，$X_N=100$；
• 以概率 $1-p=83/100$，$X_N=0$。

所以：

代回：

因此：

一般公式： 从位置 0 出发，游走到位置 $\alpha$（概率 $P$）或 $-\beta$（概率 $1-P$）时停止。则： \(P = \frac{\beta}{\alpha + \beta}, \quad E[N] = \alpha \beta\)

面试中说： “我用鞅的可选停止定理。首先，$X_n$ 本身是鞅，所以期望值不变；停止时只能在两端，期望值是两端的加权平均，这给出吸收概率。其次，$X_n^2 - n$ 是二次鞅，停止时期望值也不变，从而我能算出期望步数。”

题目49b：Dice Game via Wald’s Equality（骰子游戏用瓦尔德等式）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.2

掷骰子直到总和超过 63。期望的总和是多少？

答案：

也就是大约 $63 + 8/3$。这个题如果只说“用 Wald’s Equality”，还需要先算出 $E[N]$；不能直接把步数粗略估成 20。

解法（Wald’s Equality）：

设 $X_i$ 为第 $i$ 次掷骰子的结果。$N$ 为停止时间（第一次使总和 > 63 的步数）。

骰子的期望值：$E[X] = (1+2+3+4+5+6)/6 = 3.5 = 7/2$。

由 Wald’s Equality： \(E[S_N] = E[X] \cdot E[N]\)

但 $E[N]$ 本身不直接等于 $63/3.5$，因为停止时有 overshoot。

更直接的做法是利用题目 47 的“最后一次不超过 63 的和”。

设 $L=S_{N-1}$，则 $L \in {58,59,60,61,62,63}$。

从 $L=j$ 出发，最后一掷必须大于 $63-j$。因此最后一掷的条件分布是：

其条件均值是：

所以：

由题目 47，$P(L=j)$ 近似为 $(j-57)/21$。于是：

计算得：

精确递推也给出几乎相同的数值。若要从 Wald 写回去：

面试关键： “Wald 等式告诉我 $E[S_N]=3.5E[N]$，但真正困难是停时 $N$ 的期望或 overshoot。更稳的路线是先分析最后一次未超过 63 的状态 $L$，再条件化最后一掷。答案约为 $65.67$，不是 70 多。”

题目49c：Ticket Line / Ballot Problem（售票排队问题）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.2

有 $2n$ 个人排队买票。$n$ 个人持有 $5 美元，$n$ 个人持有 $10 美元。票价 $5。售票员初始没有零钱。问有多少种排列方式使得售票员始终都有零钱（不会无法找零）？

答案的概率形式（随机排列）：$P = 1/(n+1)$（Catalan 数）。

答案： 排列总数：$(2n)!/(n! \cdot n!) = \binom{2n}{n}$

有效排列数：$\binom{2n}{n} / (n+1) = C_n$（第 $n$ 个 Catalan 数）

概率 $P = 1/(n+1)$。

解法（反射原理）：

在二维格子上，从 $(0, 0)$ 到 $(2n, 0)$，每个 $5 持有者是向上一步（+1），每个 $10 持有者是向下一步（-1）。

合法排列：路径始终不低于 $x$ 轴。

从 $(0, 0)$ 到 $(2n, 0)$ 的路径总数：$\binom{2n}{n}$。

触及 $x$ 轴下方（即进入 $y < 0$ 区域）的路径数（坏路径）：由反射原理等于从 $(0, -2)$ 到 $(2n, 0)$ 的路径数（关于 $y = -1$ 反射）。

坏路径数：$\binom{2n}{n+1}$。

好路径数：$\binom{2n}{n} - \binom{2n}{n+1} = \binom{2n}{n} \cdot \frac{1}{n+1} = C_n$。

概率：$P = \frac{C_n}{\binom{2n}{n}} = \frac{1}{n+1}$。

面试中说： “这是组合问题和概率的交叉。关键是用反射原理，把’违反条件的排列’映射到另一个容易计数的集合。售票员无法找零当且仅当某时刻 $10 持有者比 $5 持有者多（资金流为负）。这等价于路径触及 $x$ 轴以下，反射得到对应的坏路径，从而得到好路径占比。”

题目49d：E[First n Consecutive Heads]（期望第一次出现 n 个连续正面）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.2

反复掷硬币，求期望第一次出现 $n$ 个连续正面需要多少次掷？

答案： $E[T_n] = 2^{n+1} - 2$

解法（鞅方法 + 几何级数）：

定义 $T_n$ 为首次出现 $n$ 个连续 H 的时刻。

方法 1（状态方程）： 设状态 $S_k$ 表示：

当前历史末尾已经有 $k$ 个连续 H，且 $k<n$。

对应：

这里的 $k$ 不是“第 $k$ 步”，而是“当前已经连续匹配了多少个 H”。

例如目标是 HHHHH：

• $E_0$：当前末尾没有连续 H。
• $E_1$：当前末尾是 H。
• $E_2$：当前末尾是 HH。
• …
• $E_{n-1}$：当前末尾已有 $n-1$ 个连续 H，只差一个 H 就完成。
• $E_n=0$：已经完成。

对 $k<n$，从 $S_k$ 出发，下一步先抛 1 次：

\(E_k = 1 + \frac{1}{2} E_{k+1} + \frac{1}{2} E_0 \quad (k < n)\) \(E_n = 0\)

逐项解释：

• 左边 $E_k$：当前已经有 $k$ 个连续 H 时，还需要多少期望步。
• 右边的 $1$：下一次抛掷本身消耗 1 步。
• $\frac12E_{k+1}$：如果下一次是 H，连续 H 个数从 $k$ 增加到 $k+1$。
• $\frac12E_0$：如果下一次是 T，连续 H 被完全打断，回到 0 个连续 H。

当 $k=n-1$ 时，$E_{k+1}=E_n=0$，因为再抛一个 H 就完成。

从后往前递推： \(E_{n-1} = 1 + \frac{1}{2} \times 0 + \frac{1}{2} E_0 = 1 + \frac{1}{2}E_0\) \(E_{n-2} = 1 + \frac{1}{2}(1 + \frac{1}{2}E_0) + \frac{1}{2}E_0 = 1.5 + \frac{3}{4}E_0\) \(\vdots\)

可以证明，对于 $m=n-k$：

验证：

• $k=n-1$，$m=1$：$E_{n-1}=(1/2)(E_0+2)=1+\frac12E_0$
• $k=n-2$，$m=2$：$E_{n-2}=(3/4)(E_0+2)=1.5+\frac34E_0$

令 $k=0$，即 $m=n$：

方法 2（鞅直觉）： 每次掷硬币，定义一个”计分”：如果掷出 H，检查最后 $n$ 个是否全是 H。给予奖励。用 Wald 等式的推广…

具体推导较复杂，结果是 $2^{n+1} - 2$。

验证小情况：

• $n = 1$（一个 H）：$E[T_1] = 2^2 - 2 = 2$。掷两次，$P(HH) = 1/4, P(TH) = 1/4$，期望 = $1 \times 1/2 + 2 \times 1/4 + 3 \times 1/8 + \cdots = 2$。✓
• $n = 2$（HH）：$E[T_2] = 2^3 - 2 = 6$。这与之前题目中算出的 HH 期望值 6 一致。✓
• $n = 3$（HHH）：$E[T_3] = 2^4 - 2 = 14$。与题目 48b 中 HHH 期望值 14 一致。✓

面试中说： “这是一个递归期望问题。我从定义所有中间状态的期望开始（已有 $k$ 个连续 H 时还需多少步），然后写出递推关系。由于每个状态只看一步，递推关系形成几何级数，求和后得到闭形式 $2^{n+1} - 2$。”

九、动态规划与最优策略（Dynamic Programming）

知识点

Bellman Equation（贝尔曼方程）与逆向归纳

在多步决策问题中，从最后一步往前推。设：

• $J_k(x_k)$ = 在第 $k$ 步，状态为 $x_k$ 时，从这一步到终末的最优期望价值。
• $u_k$ = 在第 $k$ 步的决策（动作）。
• $g_k(x_k, u_k, w_k)$ = 在第 $k$ 步，状态 $x_k$、决策 $u_k$、随机冲击 $w_k$ 下的即时收益。
• $f_k(x_k, u_k, w_k)$ = 状态转移函数，下一个状态 $x_{k+1}$。

Bellman 方程： \(J_k(x_k) = \max_{u_k} \mathbb{E}_{w_k} \left[ g_k(x_k, u_k, w_k) + J_{k+1}(f_k(x_k, u_k, w_k)) \right]\)

其中期望是对随机冲击 $w_k$ 求的。

Principle of Optimality（最优性原理）

如果一个最优策略被采取，那么其后续部分对于该后续部分的初始状态也是最优的。换句话说，最优决策序列的任何子序列也是最优的。

解题步骤

1. 明确状态和决策变量： 状态是什么，每步可以做什么选择？
2. 确定收益函数： 即时收益或终末收益是什么？
3. 写出 Bellman 递推： 从最后一步往前。
4. 逐步求解： 最后一步最简单，逐步往前计算。

例题

题目49e：Dice Game with Reroll Option（骰子重掷最优策略）⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.3 + Two Sigma + Citadel

掷 6 面骰子，最多 3 次。每掷一次后可以选择：

• 保留这次掷的值。
• 放弃这次值，重新掷（只要还有次数）。

策略应该是什么？期望能得到多少钱（掷出的值）？

答案： 期望值 $E \approx 4.67 = 14/3$。

最优策略：

• 第 3 次（最后一次）：掷出任何值都保留。期望 = $(1+2+3+4+5+6)/6 = 3.5$。
• 第 2 次：如果掷出 $\geq 4$，保留；否则重掷。期望 = ?
• 第 1 次：如果掷出 $\geq 5$，保留；否则重掷。期望 = ?

解法（逆向归纳）：

第 3 步（最后一次）： 已经掷了，没有选择，必须保留。$V_3 = E[\text{掷出值}] = 3.5$。

这里的 $V_k$ 表示：

还处在第 $k$ 次掷骰子的决策点时，从现在开始采用最优策略能得到的期望收益。

它不是“第 $k$ 次实际掷出的点数”，而是“这个阶段的最优价值”。因为第 3 次是最后一次，没有继续机会，所以 $V_3=3.5$。

第 2 步： 掷出值 $x$，可以选择保留（得 $x$）或重掷（期望 $V_3 = 3.5$）。

逐项解释：

• 如果保留，收益就是当前点数 $x$。
• 如果重掷，就放弃当前点数，进入第 3 次，期望收益是 $V_3=3.5$。

• 所以理性选择是取二者最大值。

• 如果 $x \geq 3.5$，保留。
• 如果 $x < 3.5$，重掷。

期望值： \(V_2 = \sum_{x=1}^{6} P(X=x) \times V_2(x)\)

$= \frac{1}{6}[1, 2, 3 \text{重掷}；4, 5, 6 \text{保留}]$

$= \frac{1}{6}[3.5 + 3.5 + 3.5 + 4 + 5 + 6]$

$= \frac{1}{6}[10.5 + 15]$

$= \frac{25.5}{6} = 4.25$

第 1 步： 掷出值 $y$，可以选择保留（得 $y$）或重掷（期望 $V_2 = 4.25$）。

解释：第 1 次如果重掷，不是直接进入最后一次，而是进入“还剩两次机会”的第 2 阶段，所以重掷价值是 $V_2=4.25$。

• 如果 $y \geq 4.25$，保留。即 $y \in {5, 6}$。
• 如果 $y < 4.25$，重掷。即 $y \in {1, 2, 3, 4}$，因为 4 也小于 4.25。

期望值： \(V_1 = \frac{1}{6}[4.25 + 4.25 + 4.25 + 4.25 + 5 + 6]\)

$= \frac{1}{6}[17 + 11]$

$= \frac{28}{6} = 14/3 \approx 4.67$

最优策略总结：

• 第 1 次：掷出 $\geq 5$ 就保留，否则重掷。
• 第 2 次：掷出 $\geq 4$ 就保留，否则重掷。
• 第 3 次：保留（无选择）。

面试关键说法： “从后往前推。最后一次没得选，期望值 3.5。倒数第二次，任何大于等于 3.5 的值都值得保留，否则赌一把最后一次。期望上升到 4.25。倒数第一次，只有 5 或 6 才值得保留。所以阈值递增：第一步 5，第二步 4，第三步 3.5。这反映了’越靠后越保守’的直觉。”

Citadel 变种：100 面骰子 + 支付重掷费用

掷 100 面骰子，每次重掷需支付 $1。

问题： 应该定什么阈值？期望利润？

答案： 阈值约 87，期望收益约 $87.4。

解法思路：

设 $V$ = 玩这个游戏的期望价值。在任何时刻，掷出值为 $x$，选择：

• 保留：获 $x$ 美元。
• 重掷：支付 $1，进入新一轮（期望 $V$）。

这里的 $V$ 是：

从一个全新的“先掷 100 面骰子，再决定是否重掷”的机会开始，采用最优策略的期望收益。

它不是当前掷出的点数。当前点数是 $x$。如果你选择重掷，就支付 1 美元，然后重新回到同一个决策结构，所以重掷的价值是 $V-1$。

同时，$V$ 本身由保留或重掷的决策组成： \(V = E[\max(X, V - 1)]\)

这个式子完整读作：

新一轮掷出 $X$ 后，要么保留 $X$，要么支付 1 美元重掷并得到期望 $V-1$，所以这一轮的最优价值是 $\max(X,V-1)$。再对 $X$ 取期望，就得到 $V$。

其中 $X \sim \text{Uniform}(1, 100)$。

设阈值为 $\alpha$（掷出 $\geq \alpha$ 就保留）。

期望保留值：$\frac{1}{100} \sum_{x=\alpha}^{100} x = \frac{1}{100} \times \frac{(α + 100)(101 - α)}{2}$

概率重掷：$(\alpha - 1) / 100$。

两边乘以 $\frac{100}{101-\alpha}$：

因为是整数骰子，阈值 $\alpha$ 需要满足：

也就是：

逐个检查整数阈值，$\alpha=87$ 时：

并且：

所以阈值自洽。

数值上，最优策略是掷出 $\geq 87$ 就保留，否则支付 $1 重掷。期望收益：

面试中说： “这是带成本的最优停止问题。Bellman 方程变成 $V = \max(x, V - 1)$ 的期望形式。最优策略是阈值形式：掷出大于某个值就保留，否则支付 $1 重新开始。阈值由自洽方程确定。”

题目49f：Dynamic Dice Game（累加骰子游戏）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.3

掷骰子并累加总和。掷出 1-5 时，该值加入总和；掷出 6 时，全部清零（失败）。可以在任何时刻停止并保留当前总和。应该什么时候停止？

答案： 当总和 $\geq 15$ 时停止。期望收益 $\approx $6.15$。

解法（Bellman 方程）：

这题的关键是：阈值 15 不是先猜出来的，而是由”继续一次的 break-even point”推出来，再用 Bellman 方程验证。

先明确题意：这里假设掷出 6 后游戏结束，最终收益为 0；不是”清零后还能继续玩”。

设 $V(s)$ = 当前总和为 $s$ 时，之后采用最优策略的期望收益。

更准确地说：

$V(s)$ 是“当前已经累计到 $s$，从现在开始采用最优停止策略，最终能拿到的钱的期望”。

它不是“已经赚到的钱”；已经赚到的钱是 $s$。$V(s)$ 是在状态 $s$ 下，考虑继续/停止之后的最优价值。

当前有两个选择：

• 停止：立刻拿走 $s$，价值是 $s$。
• 继续：掷出 6 则失败拿 0；掷出 $i \in {1,2,3,4,5}$ 则总和变成 $s+i$，进入新状态。

所以 Bellman 方程是：

其中继续项里没有写 $V(0)$，因为掷出 6 不是回到 0 继续玩，而是直接失败，收益为 0。

逐项解释：

• $\frac16 \times 0$：掷出 6，游戏失败，最终收益 0。
• $\frac16 V(s+i)$：掷出 $i$，当前总和变成 $s+i$，之后从状态 $s+i$ 继续做最优选择。

第一步：先找 break-even point

如果当前总和已经很高，我们怀疑”下一次如果不掷出 6，就应该直接停”。在这种停止区域里，从 $s$ 继续掷一次的价值就是：

把它和现在停止的 $s$ 比较：

所以 break-even point 是 15：

• 当 $s<15$，继续至少有希望提高期望。
• 当 $s=15$，继续一轮再停和现在停打平。
• 当 $s>15$，继续一轮再停不如现在停。

这一步不是完整证明，但它给出候选阈值：15。接下来用 Bellman 方程验证。

第二步：验证 $s \geq 15$ 时停止是最优

假设在 $s \geq 15$ 的状态停止，则 $V(s)=s$。代回继续项：

比较：

所以：

• $s=15$ 时，继续和停止无差别；可以停止。
• $s>15$ 时，继续严格不如停止。

因此 $s \geq 15$ 停止和 Bellman 方程一致。

第三步：验证 $s<15$ 时继续，并向下递推

从 $s=14$ 开始，因为 $15,16,17,18,19$ 都属于停止区间：

所以 14 应该继续。

继续往下递推：

这样一直往下算。每一步都用同一个公式：

递推表：

所以从 0 开始的期望收益是：

最终策略：

期望收益：

验证直觉： 每次掷骰子，$5/6$ 的概率掷出 1-5（加价值），$1/6$ 的概率掷出 6（失败清零）。虽然失败概率不高，但损失的是全部累计值，所以一旦累积到 15，就应该停止。

面试中说： “This is an optimal stopping problem. I define $V(s)$ as the optimal expected payoff from current sum $s$. The Bellman equation is $V(s)=\max(s,\frac16\sum_{i=1}^5 V(s+i))$, because rolling a 6 ends the game with payoff 0. To find the threshold, compare stopping at $s$ with rolling once in the stopping region: the rolling value is $(5s+15)/6$, which equals $s$ at $s=15$. Verifying this in the Bellman equation shows that stopping is optimal for $s\ge15$, and backward recursion gives $V(0)\approx6.15$.”

题目49g：Dynamic Card Game（红黑牌游戏）⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.3 + Citadel 面经

52 张牌（26 张红，26 张黑）。一次抽一张：红牌 +$1，黑牌 -$1。可以在任何时刻停止并保留当前总钱数（可负数）。最优策略是什么？期望收益？

答案： 期望收益 $\approx $2.62$（通过动态规划）。

解法（DP 与游走）：

设状态 $(b, r)$ = 剩余 $b$ 张黑牌、$r$ 张红牌。

设 $f(b, r)$ = 从状态 $(b, r)$ 开始的期望收益。

更准确地说：

$f(b,r)$ 是“当前还剩 $b$ 张黑牌和 $r$ 张红牌时，从现在开始采用最优停止策略，未来还能获得的最大期望收益”。

它不包含已经累计的钱，因为已经累计的钱是一个常数；在最优停止问题里，我们只需要比较“现在停止多拿 0”和“继续后未来增量的期望”。所以递推里停止项写成 0。

递推关系： \(f(b, r) = \max\left(0, \frac{b}{b+r} \times (-1 + f(b-1, r)) + \frac{r}{b+r} \times (+1 + f(b, r-1))\right)\)

（停止得 0；抽黑牌损 1 然后进入新状态；抽红牌得 1 然后进入新状态）

逐项解释：

• 左边 $f(b,r)$：在剩余牌数状态 $(b,r)$ 下，未来最优期望收益。
• $\max(0,\cdots)$：可以选择立刻停止，未来增量收益为 0；也可以继续抽。
• 抽黑牌概率 $b/(b+r)$，本次收益 $-1$，然后进入 $(b-1,r)$。
• 抽红牌概率 $r/(b+r)$，本次收益 $+1$，然后进入 $(b,r-1)$。

边界： $f(0, 0) = 0$（没牌了）。$f(b, 0) = 0$（只剩黑牌时立刻停止）。$f(0, r) = r$（只剩红牌时全部抽完）。

通过动态规划（表格法或递推），从末端往前计算 $f(26, 26)$。

结果 $f(26, 26) \approx 2.62$。

关键洞察：

• 当红牌比例很高时，应该继续抽（期望正）。
• 当黑牌比例很高或总钱数已经不错时，应该停止。
• 价值函数 $f(b, r)$ 不是线性的，而是阶梯形的。

面试中说： “这个问题结合了 Markov 链和最优停止。状态是剩余的红黑牌数。每个状态的价值是’停止或继续’的最优选择。继续时，根据当前比例，期望抽到红或黑，然后递进入下一个状态。用 DP 从终端往前计算，最终得到初始状态的期望收益。”

题目49h：World Series Betting（世界大赛下注）⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.3

$100 下注于红队赢得世界大赛（7 局 4 先）。在 Red Sox 已赢 $i$ 局、对手已赢 $j$ 局的任何时刻，你可以选择只对单场比赛下注（而不是锁定 $100 在大赛结果）。

问题：为了复制”赌红队赢大赛”的收益曲线，在状态 $(i, j)$ 时应该在单场比赛上赌多少？

答案：

如果 $f(i,j)$ 表示 Red Sox 从状态 $(i,j)$ 赢得系列赛的概率，那么状态 $(i,j)$ 的单场下注额是：

如果把 $V(i,j)=100f(i,j)$ 直接定义为这张“赢系列赛得 $100，否则得 $0”的票据价值，那么：

解法思路（Delta Hedging）：

这是一个二叉树 Delta 对冲问题，与金融衍生品定价类似。

设 $f(i, j)$ = Red Sox 从状态 $(i,j)$ 赢系列赛的概率。

（下一场 Red Sox 赢或输都各 50%）

边界：$f(4, j) = 1$（Red Sox 赢了），$f(i, 4) = 0$（对手赢了）。

令票据价值：

在状态 $(i,j)$，我们用：

• 现金账户 $C$；
• 下一场比赛下注 $\beta$ 在 Red Sox 身上；

来复制票据下一步的价值。

如果 Red Sox 下一场赢，则组合变成：

这必须等于票据在新状态的价值：

如果 Red Sox 下一场输，则组合变成：

这必须等于：

于是：

两式相减：

所以：

代入 $V=100f$：

例子：开局 $(0,0)$。

Red Sox 赢 4 场系列赛的概率是 $1/2$，所以票据价值是 $50。

如果下一场赢，状态变成 $(1,0)$，赢系列赛概率：

如果下一场输，状态变成 $(0,1)$，由对称性：

所以开局下一场应下注：

也就是在第一场 Red Sox 上下注 $15.625。

面试中说： “这是二叉树复制。把系列赛赌注看成一个衍生品，状态价值是 $V(i,j)=100f(i,j)$。下一场赢和输对应两个子节点。用现金 $C$ 加单场下注 $\beta$ 复制两个子节点收益，解两条线性方程，得到 $\beta=[V_{\text{win}}-V_{\text{lose}}]/2$。”

十、布朗运动与随机微积分（Brownian Motion & Stochastic Calculus）

知识点

布朗运动（Brownian Motion / Wiener Process）定义

W(t), t≥0 是布朗运动，如果：

• W(0) = 0
• 增量独立：W(t_1)-W(0), W(t_2)-W(t_1), …, W(t_n)-W(t_{n-1}) 相互独立
• 增量正态：W(t_{i+1})-W(t_i) ~ N(0, t_{i+1}-t_i)

基本性质

• E[W(t)] = 0, E[W(t)^2] = t, W(t) ~ N(0,t)
• Cov(W(s), W(t)) = min(s,t)

• 鞅性质：E[W(t+s)

  W(t)] = W(t)

• Markov性质

重要的鞅

• W(t)^2 - t 是鞅（可用 Ito’s lemma证明：d(W^2-t) = 2W dW，无drift项）
• 指数鞅：Z(t) = exp{λW(t) - λ²t/2} 是鞅

Ito’s Lemma（随机微积分的链式法则）

设 X(t) 满足 dX = β(t,X)dt + γ(t,X)dW(t)，f(X,t) 二阶可微，则：

首次通过时间（First Passage Time）

τ_x = min{t: W(t)=x}，P(τ_x ≤ t) = 2 - 2N(x/√t)，E[τ_x] = ∞

Feynman-Kac公式

将PDE问题转化为期望问题

例题

题目49i：布朗运动基本性质 ⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.4 + Two Sigma 面经

B_t 是标准布朗运动。Corr(B_t, B_t^2) = ?

答案： 0

解法（逐步计算各矩）：

相关系数公式： \(\text{Corr}(X, Y) = \frac{\text{Cov}(X, Y)}{\sqrt{\text{Var}(X) \cdot \text{Var}(Y)}}\)

设 $X = B_t$，$Y = B_t^2$。

Step 1：计算 $E[B_t]$ 和 $E[B_t^2]$。

$B_t \sim N(0, t)$，所以：

• $E[B_t] = 0$
• $E[B_t^2] = \text{Var}(B_t) + (E[B_t])^2 = t + 0 = t$

Step 2：计算 $E[B_t^3]$。

$B_t \sim N(0, t)$，正态分布关于 0 对称，所有奇数矩为 0： \(E[B_t^3] = 0\)

（严格证明：令 $B_t = \sqrt{t} \cdot Z$，$Z \sim N(0,1)$。$E[Z^3] = \int_{-\infty}^{\infty} z^3 \frac{1}{\sqrt{2\pi}} e^{-z^2/2} dz = 0$，因为 $z^3 e^{-z^2/2}$ 是奇函数。）

Step 3：计算协方差。

Step 4：结论。

分子 $\text{Cov}(B_t, B_t^2) = 0$，所以 $\text{Corr}(B_t, B_t^2) = 0$。

验证直觉： $B_t^2$ 完全由 $B_t$ 决定（$Y = X^2$ 是确定性函数关系），但它们的相关系数却为 0。这是因为相关系数只衡量线性关系。$B_t^2$ 对 $B_t$ 是非线性依赖的，正值和负值的 $B_t$ 产生的 $B_t^2$ 完全对称，正好抵消。

面试中说： “我先计算协方差。$\text{Cov}(B_t, B_t^2) = E[B_t^3] - E[B_t]E[B_t^2]$。$B_t$ 是均值为 0 的正态，所有奇数矩为 0，所以 $E[B_t^3] = 0$，$E[B_t] = 0$，协方差为 0。这是一个经典的’不相关但不独立’的例子——$B_t^2$ 完全由 $B_t$ 决定，但相关系数只捕捉线性关系，对称的非线性依赖会被抵消。”

题目49j：P(B_1>0, B_2<0) ⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.4

设 ${B_t}_{t\ge 0}$ 是从 0 出发的标准布朗运动，即 $B_0=0$，且对 $0\le s<t$ 有独立增量：

求：

答案： $P(B_1 > 0, B_2 < 0) = 1/8$

解法（增量分解 + 几何概率）：

Step 1：引入独立增量。

令 $X = B_1$，$Y = B_2 - B_1$。由布朗运动增量独立性：

• $X = B_1 \sim N(0, 1)$
• $Y = B_2 - B_1 \sim N(0, 1)$
• $X$ 和 $Y$ 独立

Step 2：用 $(X, Y)$ 重新表达条件。

$B_1 > 0$ 等价于 $X > 0$。

$B_2 < 0$ 等价于 $X + Y < 0$，即 $Y < -X$。

所以需要：$X > 0$ 且 $Y < -X$。

Step 3：几何分析。

在 $(X, Y)$ 平面上，$(X, Y)$ 服从二元标准正态独立分布，关于原点旋转对称。

条件区域：$X > 0$ 且 $Y < -X$，即右半平面中直线 $Y = -X$ 下方的区域。

这条直线过原点，斜率为 $-1$，与正 $x$ 轴成 $-45°$（即 $315°$）。

从正 $x$ 轴到这条直线（顺时针方向），扫过的角度是 $45°$。所以 $X > 0$ 且 $Y < -X$ 对应的角度范围是从 $270°$ 到 $315°$，共 $45°$。

验证（数值）： 用联合 CDF 直接算。$P(B_1 > 0, B_2 < 0)$，其中 $(B_1, B_2)$ 是二元正态，均值 $(0,0)$，$\text{Var}(B_1) = 1$，$\text{Var}(B_2) = 2$，$\text{Cov}(B_1, B_2) = \min(1,2) = 1$，相关系数 $\rho = 1/\sqrt{2}$。查表或数值积分确认 $P = 1/8 = 0.125$。✓

面试中说： “我把 $B_2$ 分解为 $B_1 + (B_2 - B_1)$，引入两个独立标准正态 $X = B_1$ 和 $Y = B_2 - B_1$。条件变成 $X > 0$ 且 $Y < -X$，在 $(X, Y)$ 平面上是直线 $Y = -X$ 下方且 $X > 0$ 的区域。由旋转对称性，这个扇形区域占全平面的 $45°/360° = 1/8$。”

题目49k：Stopping Time E[T] via Martingale ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.4 + Two Sigma

设 ${B_t}_{t\geq 0}$ 是从 0 出发的标准布朗运动（standard Brownian motion），即 $B_0=0$，它可以理解成“连续时间版本的公平随机游走”。

定义停止时间 $T$ 为第一次 hit 1 或 -1 的时间：

求 $E[T]$。

答案： $E[T] = 1$

解法：

第 1 步：先理解 $B_t$ 和 $T$

$B_t$ 表示时间 $t$ 时布朗运动的位置。

• $B_0=0$：一开始在 0；
• $B_t$ 会连续随机上下波动；
• 它没有向上或向下的 drift，所以是公平的。

$T$ 是第一次碰到边界 $1$ 或 $-1$ 的时间。也就是说：

停下时一定有：

所以：

第 2 步：用二次鞅

标准布朗运动有一个重要鞅：

它是离散公平随机游走里 $S_n^2-n$ 的连续时间版本。直觉是：布朗运动平均不偏向上或下，但平方距离会随着时间增加；标准布朗运动满足 $E[B_t^2]=t$，所以减掉 $t$ 后变成公平量。

对停时 $T$ 用 optional stopping：

也就是：

停下时 $B_T \in {1,-1}$，所以：

因此：

推广：

如果从 0 出发，hit $\alpha>0$ 或 $-\beta<0$ 时停止，则：

并且：

推导同离散随机游走。先用 $B_t$ 是鞅求 hit 概率，再用 $B_t^2-t$ 是鞅求期望时间。

题目49l：带漂移的布朗运动首达概率 ⭐⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.4

设 ${W_t}_{t\ge 0}$ 是标准布朗运动。定义带漂移的布朗运动：

也就是：

令停止时间：

求：

也就是，从 0 出发，$X_t$ 先 hit $3$ 而不是先 hit $-5$ 的概率。

答案：

若 $m\neq 0$：

若 $m=0$，取极限得到：

解法（指数鞅 / harmonic function）：

令：

对于带漂移布朗运动：

函数：

是生成元

的 harmonic function，因为：

所以：

因此 $f(X_t)=e^{-2mX_t}$ 是鞅。optional stopping 给出：

设：

则：

解得：

无漂移检查：

当 $m\to 0$：

所以：

这和无漂移时“从 0 到 3 或 -5，先到 3 的概率等于离 -5 的距离 / 总距离”一致。

题目49m：Itô’s Lemma 应用 ⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.4

$Z_t = \sqrt{t} \cdot B_t$ 是鞅吗？求 $E[Z_t]$ 和 $\text{Var}(Z_t)$。

答案： 不是鞅。$E[Z_t] = 0$，$\text{Var}(Z_t) = t^2$。

解法（Itô’s Lemma 完整代入）：

Step 1：确定函数形式。

$Z_t = f(t, B_t)$，其中 $f(t, x) = \sqrt{t} \cdot x = t^{1/2} x$。

底层过程：$dB_t = 0 \cdot dt + 1 \cdot dW_t$（即 $\beta = 0$，$\gamma = 1$）。

Step 2：计算偏导数。

Step 3：代入 Itô’s Lemma。

Step 4：判断鞅性。

鞅要求 drift 项 = 0。这里 drift = $\frac{B_t}{2\sqrt{t}} \neq 0$（以概率 1），所以 $Z_t$ 不是鞅。

Step 5：直接法计算均值和方差。

题目49n：$W(t)^3$ 是鞅吗？⭐⭐⭐ ↑ 返回 list

来源： 绿皮书 5.4

答案： 不是鞅。

解法（Itô’s Lemma 完整展开）：

Step 1：确定函数。 $f(x) = x^3$，$X_t = W_t$（标准布朗运动，$\beta = 0$，$\gamma = 1$）。

Step 2：偏导数。 \(\frac{\partial f}{\partial t} = 0, \quad \frac{\partial f}{\partial x} = 3x^2, \quad \frac{\partial^2 f}{\partial x^2} = 6x\)

Step 3：代入 Itô’s Lemma。

Step 4：判断。 drift 项 $= 3W_t \neq 0$（概率 1），所以 不是鞅。

修正为鞅： 如果想构造一个与 $W_t^3$ 相关的鞅，需要减去 drift 的累积。由于 $d(W_t^3) = 3W_t \, dt + 3W_t^2 \, dW_t$，我们需要减去 $\int_0^t 3W_s \, ds$。即 $M_t = W_t^3 - 3\int_0^t W_s \, ds$ 是鞅。

验证小例子（直接法）： $E[W_t^3 | \mathcal{F}_s]$。令 $W_t = W_s + (W_t - W_s)$，展开： \(W_t^3 = [W_s + (W_t - W_s)]^3 = W_s^3 + 3W_s^2(W_t - W_s) + 3W_s(W_t - W_s)^2 + (W_t - W_s)^3\)

取条件期望（$W_t - W_s$ 独立于 $\mathcal{F}_s$，均值 0，方差 $t-s$）： \(E[W_t^3 | \mathcal{F}_s] = W_s^3 + 0 + 3W_s(t - s) + 0 = W_s^3 + 3W_s(t - s)\)

$= W_s^3 + 3W_s(t-s) \neq W_s^3$。确认不是鞅。✓

题目49o：$E[B(t)|B(1)=c]$（条件布朗运动）⭐⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经

答案： $ct$

解法（二元正态条件期望公式）：

Step 1：确定联合分布。

$(B_t, B_1)$ 是二元正态：

• $E[B_t] = 0$，$E[B_1] = 0$
• $\text{Var}(B_t) = t$，$\text{Var}(B_1) = 1$
• $\text{Cov}(B_t, B_1) = \min(t, 1) = t$（因为 $0 < t < 1$）

Step 2：二元正态条件期望公式。

Step 3：代入。

Step 4：条件方差（追问常见）。

这就是布朗桥（Brownian Bridge）的定义：给定起点 $B_0 = 0$ 和终点 $B_1 = c$，中间时刻 $t$ 处的条件期望是 $ct$（线性内插），条件方差是 $t(1-t)$（在中点 $t = 1/2$ 最大，两端为 0）。

验证特殊值：

• $t = 0$：$E[B_0

  B_1 = c] = 0$。✓（已知 $B_0 = 0$）

• $t = 1$：$E[B_1

  B_1 = c] = c$。✓

• $t = 1/2$：$E[B_{1/2}

  B_1 = c] = c/2$。直觉正确，取两端的中点。✓

十一、蒙特卡洛模拟与采样（Monte Carlo Simulation & Sampling）

知识点

从均匀分布生成其他分布

逆变换法（Inverse CDF）： 若 U~U(0,1)，则 X = F^{-1}(U) 的分布为 F

Box-Muller 变换： U_1, U_2 ~ U(0,1) → Z_1 = √(-2lnU_1)cos(2πU_2), Z_2 = √(-2lnU_1)sin(2πU_2)，Z_1,Z_2 独立标准正态

拒绝采样（Rejection Sampling）： 从简单分布采样，按接受概率保留

从均匀圆盘采样

不能直接用 (r,θ) 均匀！正确：r = √U, θ = 2πV（U,V独立U(0,1)）

生成相关正态变量

Cholesky分解 Σ = LL^T，X = LZ where Z~N(0,I)

例题

题目49p：U(0,1) → N(0,1) ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： Citadel 面经（高频）

如何用均匀随机数生成标准正态随机变量？

答案： 主要有两种方法：Box-Muller 变换和逆 CDF 法。

方法 1：Box-Muller 变换（最常考）

Step 1：取两个独立均匀随机数 $U_1, U_2 \sim U(0,1)$。

Step 2：计算： \(Z_1 = \sqrt{-2\ln U_1} \cos(2\pi U_2)\) \(Z_2 = \sqrt{-2\ln U_1} \sin(2\pi U_2)\)

则 $Z_1, Z_2$ 是两个独立的 $N(0,1)$。

Step 3：证明为什么这有效。

考虑逆过程。设 $Z_1, Z_2 \sim N(0,1)$ 独立。联合密度： \(f(z_1, z_2) = \frac{1}{2\pi} e^{-(z_1^2 + z_2^2)/2}\)

用极坐标 $R^2 = Z_1^2 + Z_2^2$，$\Theta = \arctan(Z_2/Z_1)$：

所以 $R^2 \sim \text{Exp}(1/2)$（即 $-2\ln U_1$ 的分布），$\Theta \sim U(0, 2\pi)$（即 $2\pi U_2$ 的分布）。

反过来，从 $U_1 \to R = \sqrt{-2\ln U_1}$ 和 $U_2 \to \Theta = 2\pi U_2$，再转回直角坐标，就得到了两个独立标准正态。

方法 2：逆 CDF 法

其中 $\Phi$ 是标准正态 CDF。由逆变换定理，$Z \sim N(0, 1)$。

缺点：$\Phi^{-1}$ 没有闭合形式，需要数值近似（如 Rational approximation）。

面试追问及回答：

• 为什么 Box-Muller 需要两个均匀？ 一个均匀给半径（决定离原点多远），一个给角度（决定方向）。极坐标需要两个自由度。作为回报，你同时得到了两个独立正态。
• 有没有只用一个均匀的方法？ 逆 CDF 法只需一个，但计算 $\Phi^{-1}$ 更慢。
• 如果 $U_1 = 0$ 怎么办？ $\ln(0)$ 未定义，实践中用 $U(0,1)$ 的开区间或加 $\epsilon$。

面试中说： “最经典的方法是 Box-Muller 变换。取两个独立 $U(0,1)$，一个通过 $-2\ln$ 映射到指数分布给半径的平方，一个乘 $2\pi$ 给角度，然后转直角坐标得到两个独立标准正态。本质上是利用了二元标准正态联合密度在极坐标下可以分离为半径和角度两个独立分量的性质。”

题目49q：Uniform Disk Sampling ⭐⭐⭐⭐ ↑ 返回 list

来源： Citadel 面经

如何在单位圆盘上均匀采样一个点？

答案： $R = \sqrt{U}$，$\Theta = 2\pi V$，其中 $U, V \sim U(0,1)$ 独立。然后 $(X, Y) = (R\cos\Theta, R\sin\Theta)$。

解法（从面积元素推导）：

Step 1：为什么不能直接 $R = U$？

面积元素 $dA = r \, dr \, d\theta$。如果 $R \sim U(0,1)$（$R$ 均匀），则半径 $r$ 附近的”带宽”是 $dr$，但对应的面积是 $2\pi r \, dr$——外圈面积大，内圈面积小。

$R$ 均匀意味着等概率落在每个半径处，但外圈面积更大，所以点会集中在圆心附近——不均匀！

Step 2：求 $R$ 的正确分布。

均匀采样要求概率正比于面积。半径 $\leq r$ 的区域面积占总面积的比例： \(P(R \leq r) = \frac{\pi r^2}{\pi \cdot 1^2} = r^2, \quad 0 \leq r \leq 1\)

所以 $R$ 的 CDF 是 $F_R(r) = r^2$。

Step 3：逆变换采样。

$F_R(r) = r^2$，令 $U = r^2$，解出 $r = \sqrt{U}$。

所以 $R = \sqrt{U}$，$U \sim U(0,1)$。

Step 4：角度 $\Theta$。

由对称性，$\Theta \sim U(0, 2\pi)$，即 $\Theta = 2\pi V$，$V \sim U(0,1)$。

验证（密度函数）： $f_R(r) = F_R’(r) = 2r$，$f_\Theta(\theta) = 1/(2\pi)$。联合密度 $f(r, \theta) = 2r/(2\pi) = r/\pi$。变换回直角坐标 $(x, y)$：$f(x, y) = 1/\pi$（常数），确认是均匀分布。✓

面试中说： “不能让半径均匀，因为面积元素是 $r \, dr \, d\theta$，外圈面积更大。均匀采样要求 $P(R \leq r) = r^2$（面积比），所以 $R = \sqrt{U}$。本质上就是逆 CDF 采样。同样的思路可以推广到球面均匀采样——三维中体积元素是 $r^2 \sin\phi$，所以需要 $R = U^{1/3}$。”

题目49r：四面体包含原点的概率 ⭐⭐⭐ ↑ 返回 list

来源： Citadel 面经

在单位球面上均匀随机取 4 个点，连成四面体。该四面体包含原点的概率是多少？

答案： $P = 1/8$

解法（对称性论证）：

Step 1：关键观察。

设 4 个点为 $P_1, P_2, P_3, P_4$。每个点 $P_i$ 和它的对径点 $-P_i$ 关于原点对称。

Step 2：对称性论证。

对于球面上的 4 个随机点，考虑所有可能的”符号组合”：每个点可以取 $+P_i$ 或 $-P_i$，共 $2^4 = 16$ 种组合。

但由于对称性，如果我们固定 $P_1$ 的方向（消除一个自由度），实际上有 $2^3 = 8$ 种本质不同的组合。

Step 3：原点包含条件。

四面体包含原点 $\Leftrightarrow$ 4 个点不全在某个半球内。

等价地：不存在一个过原点的平面使得 4 个点都在同一侧。

由 Wendel 公式或直接对称论证：对每个点独立地选 $+P_i$ 或 $-P_i$（各概率 1/2），恰好有 1 种选法使得四面体包含原点（在 $2^3 = 8$ 种可能中）。

Step 4：Monte Carlo 模拟验证。

import numpy as np
N = 1000000
count = 0
for _ in range(N):
    # 球面均匀采样：高斯向量归一化
    pts = np.random.randn(4, 3)
    pts = pts / np.linalg.norm(pts, axis=1, keepdims=True)
    # 检查原点是否在四面体内：
    # 原点在四面体内 ⟺ 4个面法向量的符号一致性
    # 等价：所有 det 符号相同
    signs = []
    for i in range(4):
        # 去掉第 i 个点，剩余3点构成面
        face = np.delete(pts, i, axis=0)  # 3x3
        det = np.linalg.det(face)
        signs.append(np.sign(det) * np.sign(np.dot(pts[i], np.cross(face[0]-face[1], face[0]-face[2]))))
    # 简化方法：检查 4 个三面角是否全同号
    M = pts  # 4x3
    d1 = np.linalg.det(M[[1,2,3]])
    d2 = -np.linalg.det(M[[0,2,3]])
    d3 = np.linalg.det(M[[0,1,3]])
    d4 = -np.linalg.det(M[[0,1,2]])
    if (d1>0 and d2>0 and d3>0 and d4>0) or (d1<0 and d2<0 and d3<0 and d4<0):
        count += 1
print(count / N)  # ≈ 0.125

面试中说： “这个问题的核心是对称性。4 个球面上的点，每个都可以取反（对径点），共 $2^4$ 种组合。固定一个自由度后有 8 种，其中恰好 1 种使得四面体包含原点。所以概率 $1/8$。如果要用 Monte Carlo 验证，球面均匀采样的标准做法是生成高斯向量再归一化，然后用行列式符号判断原点是否在四面体内。”

题目49s：生成相关正态变量 ⭐⭐⭐⭐⭐ ↑ 返回 list

来源： Two Sigma 面经（高频追问）

给定 $N$ 个变量，两两相关系数都为 $\rho$，如何生成？

答案： 两种方法：Cholesky 分解（通用）和公共因子法（等相关特殊情况）。

方法 1：公共因子法（等相关情况的直觉方法）

Step 1：构造。

令 $Z_0, Z_1, Z_2, \ldots, Z_N$ 为 $N+1$ 个独立标准正态。定义： \(X_i = \sqrt{\rho} \cdot Z_0 + \sqrt{1 - \rho} \cdot Z_i, \quad i = 1, 2, \ldots, N\)

Step 2：验证均值和方差。

Step 3：验证相关系数。

对 $i \neq j$：

因为 $\text{Var}(X_i) = 1$，所以 $\text{Corr}(X_i, X_j) = \rho$。✓

直觉： $Z_0$ 是”公共因子”，所有 $X_i$ 共享。$\sqrt{\rho}$ 控制公共因子的权重——$\rho$ 越大，$X_i$ 受公共因子影响越大，相关性越强。

方法 2：Cholesky 分解（通用方法）

Step 1：构造协方差矩阵 $\Sigma$。

对于一般的相关结构，$\Sigma$ 可以是任意半正定矩阵。

Step 2：Cholesky 分解。

其中 $L$ 是下三角矩阵。

Step 3：生成。

令 $\mathbf{Z} = (Z_1, \ldots, Z_N)^T \sim N(\mathbf{0}, I)$（独立标准正态向量），则： \(\mathbf{X} = L\mathbf{Z} \sim N(\mathbf{0}, \Sigma)\)

验证：$\text{Cov}(\mathbf{X}) = E[L\mathbf{Z}(L\mathbf{Z})^T] = LE[\mathbf{Z}\mathbf{Z}^T]L^T = LIL^T = LL^T = \Sigma$。✓

两变量特殊情况（$N = 2$，相关系数 $\rho$）：

所以 $X_1 = Z_1$，$X_2 = \rho Z_1 + \sqrt{1-\rho^2} Z_2$。

注意： $\rho$ 的约束。等相关矩阵要求 $\rho \geq -1/(N-1)$（半正定条件）。当 $N$ 很大时，$\rho$ 不能太负。

面试中说： “等相关情况有一个优美的公共因子构造：$X_i = \sqrt{\rho} Z_0 + \sqrt{1-\rho} Z_i$，所有变量共享 $Z_0$ 作为’系统性因子’，各自有独立的 $Z_i$ 作为’特异性因子’。方差是 $\rho + (1-\rho) = 1$，协方差是 $\rho$，非常直觉。一般情况用 Cholesky 分解 $\Sigma = LL^T$，然后 $X = LZ$。面试中如果被追问’为什么 Cholesky 一定存在’，答案是 $\Sigma$ 半正定保证可以分解。”