#021. 绿皮书：概率、智力题与算法题解

“绿皮书”通常指 Xinfeng Zhou 的 A Practical Guide to Quantitative Finance Interviews。真正值得学的不是背 200 个答案，而是识别有限的底层套路：不变量、信息量、条件样本空间、状态递推、停止时刻、对称性和线性期望。

智力题概率随机过程算法

1. 怎么使用这份笔记

每道题按五步口述：

1. 先消歧义：抽样方式、信息如何获得、能否自适应操作；
2. 定义状态/样本空间：不要凭直觉直接报数；
3. 找结构：对称、不变量、递推、补事件或信息下界；
4. 推导并检查极端情况；
5. 主动说变式：展示你掌握的是方法而不是答案。

2. 智力题：先找不变量与信息量

2.1 10×10 棋盘去掉两个对角格，能否用 1×2 多米诺铺满？

答案：不能。

把棋盘黑白相间染色。每块多米诺必覆盖一黑一白。10×10 原有 50 黑 50 白，而两个对角格同色；删后变成 48:50。任何多米诺铺法都保持黑白数量相等，因此不可能。

迁移：看到“铺砖/走格/翻转”先找模 2、染色或边界不变量。面积相等只是必要条件，不是充分条件。

2.2 12 个球中 1 个或轻或重，只有天平，最少几次？

答案：3 次。

有 $12\times2=24$ 种状态。一次称量只有左重、平衡、右重三种结果，三次最多区分 $3^3=27$ 种，信息下界允许三次；接着还需给出能达到下界的构造。

第一称 4 vs 4：

• 若平衡，异常在剩余 4 个，且前 8 个可作标准球；两次足以定位并判轻重；
• 若不平衡，异常在上秤 8 个，且轻重方向已被约束：重侧某球偏重或轻侧某球偏轻，共 8 种状态。第二称通过混合交换，让三种结果把候选状态分成至多 3/3/2，第三称完成确认。

面试中只说“3 次”不够；信息下界证明“不能少”，决策树构造证明“确实能”。

2.3 8 个球中 1 个更重，最少称几次？

答案：2 次。 第一次 3 vs 3。平衡则异常在剩余 2 个；不平衡则在重侧 3 个。第二次 1 vs 1 即可。

2.4 两根燃烧速度不均的绳子，每根总燃烧 60 分钟，如何计 45 分钟？

同时点燃绳 A 两端和绳 B 一端。A 在 30 分钟烧完；此时点燃 B 的另一端。B 剩余部分从两端燃烧，再用 15 分钟，总计 45 分钟。

关键：总时长已知但局部速度未知，所以不能按长度切；必须用“两端点燃把剩余时间减半”。

2.5 100! 末尾有多少个 0？

零来自因子 10，而 2 远多于 5，因此数 5 的幂：

$$\left\lfloor\frac{100}{5}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor=20+4=24.$$

一般式为 $\sum_{k\ge1}\lfloor n/5^k\rfloor$。易错点是只算 5 的倍数，漏掉 25、125 提供的额外因子。

2.6 三袋水果标签全错，最少取几个水果可改正？

答案：1 个。 从标为“混合”的袋中取一个。因为标签全错，这袋不可能是混合；抽到苹果则它是全苹果，余下两袋利用“标签都错”唯一确定。

这题的核心是充分利用“全部错误”这一全局约束，而不是逐袋采样。

2.7 100 枚硬币中 20 枚正面，蒙眼分两堆使正面数相同

任取 20 枚作为 A，其余 80 枚为 B；把 A 中所有硬币翻面。若 A 原有 $x$ 个正面，则 B 有 $20-x$ 个正面；翻面后 A 也有 $20-x$ 个正面。

这是典型互补不变量：不知道 $x$，但翻转把 $x$ 变为固定总量减 $x$。

2.8 25 匹马、5 条赛道、无秒表，找最快 3 匹最少几场？

答案：7 场。

前 5 场分组赛；第 6 场让各组第一名比赛。设名次为 A1>B1>C1>D1>E1，则仍可能进前三的只有 A1、A2、A3、B1、B2、C1。A1 已确定最快，第 7 场让 A2、A3、B1、B2、C1 比，前两名加 A1 即总前三。

关键不是机械淘汰，而是把“输给至少三匹更快马”的候选人全部剪掉。

3. 条件概率：先问信息是如何产生的

3.1 两个孩子，已知至少一个是男孩，另一个也是男孩的概率？

在默认假设“两个孩子性别独立等概率，信息只是事件‘至少一个男孩’”下，条件样本空间为 BB、BG、GB，故答案 $1/3$。

但若随机选一个孩子告诉你“这个孩子是男孩”，另一个为男孩的概率是 $1/2$。若父亲有复杂的报信规则，答案还能变化。

面试高分点：先指出报信机制决定条件概率。九坤 2023 回忆帖作者写 0.5，而通常题意答案是 1/3；这正说明不能靠直觉。

3.2 Monty Hall：换门为什么是 2/3？

最初选中奖品概率 $1/3$，选错概率 $2/3$。主持人知道答案且必定打开一扇空门，因此“换门”恰好在你最初选错时获胜，概率 $2/3$。

若主持人并不知道答案或不保证总开空门，必须重新建模。

3.3 俄罗斯轮盘：该不该重新转轮？

答案取决于子弹布局。若 6 个膛室中 2 发相邻，前一枪空后不转：当前空膛室有 4 个，其中只有 1 个后继是子弹，死亡概率 $1/4$；重转为 $2/6=1/3$，所以不转更好。若两发不相邻，结论可能相反。

3.4 公平硬币依次抛，先出现反面者赢，先手胜率？

先手在第 1、3、5…次抛到反面获胜：

$$P=\frac12+\left(\frac12\right)^3+\left(\frac12\right)^5+\cdots=\frac{1/2}{1-1/4}=\frac23.$$

游戏不公平。递推写法也可：$p=1/2+(1/2)^2p$。

4. 组合概率与补事件

4.1 生日悖论：多少人时同生日概率超过 50%？

计算补事件“所有人生日不同”：

$$P(\text{no match})=\prod_{k=0}^{n-1}\frac{365-k}{365}.$$

最小 $n=23$ 时重复概率超过 1/2。近似用 $\log(1-x)\approx-x$：

$$P(\text{no match})\approx \exp\left(-\frac{n(n-1)}{730}\right).$$

4.2 圆上随机取 n 点，全落在某个半圆内的概率

答案：$n/2^{n-1}$。 对连续均匀点，若所有点位于某半圆，则几乎必有一个点是该覆盖半圆的起点。固定某点作为起点，其余 $n-1$ 点落在顺时针半圆的概率为 $2^{-(n-1)}$；起点有 n 种，事件几乎不重叠。

因此这些点不全在任何半圆的概率为 $1-n/2^{n-1}$，这也等于它们的凸包包含圆心的概率。

4.3 54 张牌有放回抽取，集齐所有牌的期望次数

当已有 $k$ 种牌时，抽到新牌概率为 $(54-k)/54$，等待时间期望为 $54/(54-k)$。线性相加：

$$E[T]=54\left(1+\frac12+\cdots+\frac1{54}\right)=54H_{54}\approx247.0732.$$

这里不需要等待时间彼此独立，期望仍可线性相加。

4.4 公平骰子直到六个点数都出现，期望次数

同理为 $6H_6=6(1+1/2+\cdots+1/6)=14.7$。

5. 几何概率

5.1 三个 $U(0,1)$ 长度能组成三角形的概率

设最大边为 $M$。不能组成三角形当且仅当最大边不小于另外两边之和。三个变量对称，以 $X$ 为最大失败边：区域 $x\ge y+z$ 的体积为

$$\int_0^1\int_0^{1-y}(1-y-z),dz,dy=\frac16.$$

三种最大边事件互斥，总失败概率 $3\times1/6=1/2$，故成功概率 1/2。

5.2 两人一小时内随机到达，各等 15 分钟，相遇概率

在单位正方形 $(x,y)$ 中，相遇条件 $|x-y|\le1/4$。补集是两个边长 $3/4$ 的直角三角形，总面积 $2\times(1/2)(3/4)^2=9/16$，所以相遇概率 $7/16$。

若等待时间改为 $t$（占总时长比例），概率为 $1-(1-t)^2=2t-t^2$。

6. 期望与停止时刻

6.1 期望多少次掷出连续 6 个 6？

一般地，伯努利成功概率 $p$，连续 $r$ 次成功的等待时间：

$$E[T]=\frac{1-p^r}{(1-p)p^r}.$$

取 $p=1/6,r=6$：

$$E[T]=\frac{1-6^{-6}}{(5/6)6^{-6}}=\frac{6^7-6}{5}=55{,}986.$$

易错点是写成 $6^6$，这忽略连续成功串发生重叠，不能把每个长度为 6 的窗口当作独立尝试。

6.2 $U_i\sim U(0,1)$，首次使累计和超过 1 的项数 $N$，求 $E[N]$

用尾和公式：$E[N]=\sum_{n\ge0}P(N>n)$。而 $N>n$ 等价于 $U_1+\cdots+U_n\le1$。单位立方体中该单纯形体积为 $1/n!$，所以

$$E[N]=\sum_{n=0}^{\infty}\frac1{n!}=e.$$

这是 Jump 高频原题。亮点是把停止时刻转成尾概率，再把概率转成几何体积。

6.3 掷 n 次公平六面骰，最大值的期望

对取值 1…6 的非负整数变量，用尾和：

$$E[M]=\sum_{k=1}^{6}P(M\ge k)=\sum_{k=1}^{6}\left[1-\left(\frac{k-1}{6}\right)^n\right].$$

等价地，$P(M=m)=(m/6)^n-((m-1)/6)^n$ 后直接求和。

6.4 两次掷骰，较大者期望

取上式 $n=2$：

$$E[M]=\sum_{k=1}^{6}\left[1-\left(\frac{k-1}{6}\right)^2\right]=\frac{161}{36}\approx4.4722.$$

7. 线性代数与统计

7.1 n 个随机变量两两相关系数均为 c，c 的范围

相关矩阵为 $R=(1-c)I+c\mathbf1\mathbf1^\top$。其特征值：沿全 1 方向为 $1+(n-1)c$，其余 $n-1$ 个方向为 $1-c$。相关矩阵必须半正定，因此

$$-\frac1{n-1}\le c\le1.$$

这是 Jump 高频题。不要只报范围；用特征值或取任意系数向量的方差非负证明。

7.2 独立标准正态 X,Y，求 $P(X>5Y)$

$X-5Y\sim N(0,26)$，分布关于 0 对称且连续，所以 $P(X-5Y>0)=1/2$。系数 5 是干扰项。

7.3 大样本如何判断是否正态

不要只跑一个 p-value：

• 先看直方图、ECDF、Q–Q 图，特别是尾部；
• 看偏度、峰度与分位数；
• Shapiro–Wilk、Anderson–Darling 等检验只能回答特定零假设；
• 大样本下微小、业务上无意义的偏差也会显著；
• 真正问题通常是“下游方法对哪类非正态敏感”。

8. 动态规划与算法

8.1 鸡蛋掉落：k 枚蛋、n 层楼最少多少次

传统 $dp[k][n]$ 枚举落点是 $O(kn^2)$，在 $n=10^4$ 可能超时。反向定义 $f[m][k]$：m 次尝试、k 枚蛋最多能覆盖多少层。一次扔下后：碎了覆盖 $f[m-1][k-1]$ 层，没碎覆盖 $f[m-1][k]$ 层，加当前层：

$$f[m][k]=f[m-1][k-1]+f[m-1][k]+1.$$

迭代 m 直到 $f[m][k]\ge n$。空间可压成一维，k 倒序更新。复杂度约 $O(km)$。

8.2 一次遍历计算方差：为什么朴素公式会失败

朴素式 $\operatorname{Var}(X)=E[X^2]-E[X]^2$ 在数值很大但方差很小时会发生灾难性消减。Welford 在线算法：

n += 1
delta  = x - mean
mean  += delta / n
delta2 = x - mean
M2    += delta * delta2
variance = M2 / (n-1)

它单遍、$O(1)$ 空间且数值稳定。并行场景可合并各分块的 n、mean、M2。

8.3 1000! 末尾 0 与通用实现

$$\lfloor1000/5\rfloor+\lfloor1000/25\rfloor+\lfloor1000/125\rfloor+\lfloor1000/625\rfloor=200+40+8+1=249.$$

算法循环不断令 $n\leftarrow\lfloor n/5\rfloor$ 并累加，复杂度 $O(\log_5 n)$。

9. 金融题：把公式放回无套利逻辑

9.1 Put–call parity

无分红欧式期权：

$$C-P=S_0-Ke^{-rT}.$$

证明方式不是背公式，而是比较两个到期现金流完全相同的组合：看涨 + 现值为 $Ke^{-rT}$ 的现金，与看跌 + 股票。若等式不成立即可构造套利。

9.2 最大回撤

净值序列 $V_t$ 的回撤为 $D_t=1-V_t/\max_{s\le t}V_s$，最大回撤为 $\max_t D_t$。它依赖路径，不能由终值或波动率单独决定；比较策略时还应报告发生区间、恢复时间与是否由单一暴露造成。

9.3 最优对冲比率

用资产变化 $\Delta S$ 对冲目标变化 $\Delta V$，最小化 $\operatorname{Var}(\Delta V-h\Delta S)$，一阶条件给出

$$h^*=\frac{\operatorname{Cov}(\Delta V,\Delta S)}{\operatorname{Var}(\Delta S)}.$$

它本质上就是带截距 OLS 的斜率；样本外稳定性、时间尺度与成本决定实际可用性。

10. 30 秒口述模板

遇到陌生题时可这样组织：

我先确认随机机制/操作限制。然后把状态写成……。直接枚举会是……，但这里有一个对称性/不变量/补事件。于是我计算……得到……。检查 n=1 或边界情况一致。如果条件改成……，原结论会因为……而变化。

11. 题源边界

• 绿皮书：Xinfeng Zhou, A Practical Guide to Quantitative Finance Interviews, 2008。
• HowToQuant 章节化题库：编号 1000 以下对应书题，1000+ 为站点加题。
• 阅微堂中文整理的部分绿皮智力题。
• 九坤、Jump 的公司题只在它们确有公开回忆时标注；其余是绿皮或通用高频题，不冒充公司原卷。

12. 我的判断

绿皮书真正训练的是“有限时间内搭建正确模型”。面试中的危险不是算慢，而是样本空间没定义、条件信息来源不清、把必要条件当充分条件。最有效的刷法是每题写一行“触发器”：看到两孩问题先问报信机制；看到称球先算信息下界；看到集齐类别先拆等待阶段；看到停止时刻先试尾和。这样陌生变式仍能做，而不是只记住 $1/3$、$e$ 或 $54H_{54}$。

13. 补齐智力题：把每一步真正做出来

这一部分是独立推导的学习题解，不是绿皮书全文翻译。相同题名在不同网站可能对应不同题干；以下先明确采用的条件，再解题。书中全部题目是否覆盖，必须拿具体版本逐页对账，不能用第三方题库数量代替。

13.1 12 球：完整三称决策树

题设。 A～L 共 12 球，恰有一个异常，可能重也可能轻；目标同时找出球及轻重。记 H 为偏重，L 为偏轻。

先证下界。 24 个候选状态，两称只有 9 条结果路径，因此至少三称。三称有 27 路径，只说明信息容量够；下面的构造才证明够用。

第一次称 ABCD 对 EFGH。

第一次若右重：把表中 A↔E、B↔F、C↔G、D↔H 全部交换，再执行“左重”分支即可，I 仍是正常球。

为什么第二称这样摆？ 第一次左重后候选仅 AH、BH、CH、DH、EL、FL、GL、HL。第二称 ABE 对 CFI 将其分成左重 {AH,BH,FL}、左轻 {CH,EL}、平衡 {DH,GL,HL}，每组最多三种；最后一称恰好消歧。学习重点是“为候选假设设计实验”，不是记一串球名。

13.2 海盗分金：先确定平局算不算通过

标准版本。 五人 A～E，A 最资深；至少半数赞成即通过，自己可以投票；偏好依次是活命、金币更多、同等情况下让提案者死。

逆推：只剩 E 时拿 100；D、E 两人时 D 自己一票达到半数，分 (100,0)。C、D、E 三人时 C 还缺一票，给 E 1 枚胜过下一轮的 0，分 (99,0,1)。B～E 四人只需两票，买 C 的票要超过 99，买 D 只需 1，故分 (99,0,1,0)。A～E 五人需三票，下一轮 C、E 都拿 0，给二人各 1：(98,0,1,0,1)。

若严格过半才通过，答案会改变。 两人时 D 无法买到 E 的票，D 会死；三人时 D 为活命愿以 0 支持 C，所以 C 可全拿。四人时 B 须给 D、E 各 1，得 (98,0,1,1)。五人时 A 给 C 1，再给 D 或 E 2，得 (97,0,1,2,0) 或 (97,0,1,0,2)。原指南曾把“平局淘汰”与半数通过版答案混用，现已更正。

13.3 老虎与羊：为什么偶数保护羊

题设。 老虎先保证自己不被吃，再考虑吃羊；吃羊者变羊，其他老虎数量减一；所有老虎完全理性且这些规则是共同知识。

一虎时可以安全吃；二虎时谁吃就变成面对一虎的羊，必被吃，所以都不动；三虎时吃后剩二虎，二虎不敢吃，因此可以吃。归纳：奇数虎会吃，偶数虎不会吃。100 为偶数，羊安全。这个结论依赖“存活优先”，若饥饿到必死、不能预见后果或允许同时吃，模型须重写。

13.4 53 块 1×1×4 砖装 6×6×6 盒：面积够为什么仍不行

题设。 砖与单位网格平行放置，不允许斜塞。把每条坐标轴按相邻两格分组，格点颜色定义为 $(-1)^{\lfloor x/2\rfloor+\lfloor y/2\rfloor+\lfloor z/2\rfloor}$，其中 $x,y,z\in\{0,\ldots,5\}$。

每条轴上的颜色符号为 ++--++，总和为 2，故整个盒子两色数量差为 $2^3=8$。任意长度为 4 的连续格，符号总和为 0，因此每块砖恰占两正两负，始终不能改变颜色差。53 砖占 212 格，只剩 4 格，剩余格最多承载颜色差 4，无法留下原先的差 8，故不可能。

检查。 52 砖留下 8 格，不被此证明排除；但“不被排除”并不自动证明能装。另一些网站把 Box Packing 改成 27 块 1×2×4，不能只凭英文题名当成同一道。

13.5 日期骰子：六个面怎样表示 01～31

让一颗写 0、1、2、3、4、5，另一颗写 0、1、2、6、7、8；6 可以倒转充当 9。两骰可以交换左右。

为什么两颗都要 1 和 2？必须表示 11 和 22。为什么两颗都要 0？01～09 共九个搭配；若只有一颗有 0，另一颗六个面即使 6/9 共用也最多提供七种非零显示，不够。剩下逐查 03～09、13～19、23～29、30、31，都可以安排。若不许翻转 6/9，规则下无解：重复 0、1、2 已占六面，3～9 还需七面，共十三面。

13.6 三开关三灯泡、双卫兵两门

灯泡。 开 A 一段时间后关掉，再开 B，C 不动；入屋后亮的是 B，灭但温热的是 A，灭且冷的是 C。信息来自“亮灭＋温度”，前提是灯泡能保留可安全辨认的热量；若只准观察亮灭且没有其他状态，三个对象不能这样区分。

两门。 向任意卫兵问：“如果我问另一位哪扇是安全门，他会指这扇吗？”若答是，选另一扇；答否，选这扇。真卫兵准确转述假话，假卫兵歪曲真话，两种情况下都给出错误方向，再取反。两卫兵都必须知道门的含义和彼此规则。此题与三门 Monty Hall 分开，不共用答案。

13.7 八人平均工资：随机掩码为什么有效、又泄漏什么

标准练习。 八人只求总和，不公开自己的工资，不考虑串谋。第一人选随机数 R，将 $R+s_1$ 私下给第二人；每人加自己的工资传给下一人。最后传回第一人，减 R 得总工资，再除 8。

对于收到中间和的人，未知 R 掩住了之前的工资；但如果所有中间值公开，相邻差就泄漏工资。相邻参与者串谋也可能恢复某人的贡献。因此这只是诚实参与、私密通道下的教学方案，不是安全多方计算协议。若要求对 n−1 人串谋仍完全保密，公开总和本身就能推算剩下一人的工资，必须先界定可接受泄漏。

13.8 Last Ball、Coin Piles、Wise Men：逐个给明确练习版本

Last Ball。 每轮拿两球，同色丢两球放回一蓝，异色丢蓝留红。红球数每步只减 0 或 2，奇偶不变；最后若最初红数奇则红、偶则蓝。20 红 20 蓝最后蓝。若题干换了“同色放红”，不变量就改成蓝数奇偶。

十堆假币。 十堆各至少十枚，只有一堆每枚 9g，真币 10g，电子秤可给精确重量。第 i 堆取 i 枚，共55枚，正常550g，实测比550少 i 克就说明第 i 堆假。这是把身份编码为可测量的重量差。若多堆可能假，可用二进制取样 1、2、4…，但要确保各堆数量足够；天平只能三态，不能照搬。

智者帽子。 三白两黑中给三人各戴一顶。A 看见 B、C，B 只看见 C，C 什么也看不到；A 说不知道，B 也说不知道，C 能判白。A 不知道排除 B、C 都黑。假如 C 黑，B 会据此知道自己白，然而 B 不知道，所以 C 白。每一句“不知道”都删去一组可能世界；若三人同时发言或彼此不知道规则，就无法如此推理。

13.9 过桥与河流运输

过桥标准练习。 四人耗时1、2、5、10分钟，一盏灯，每次最多两人，同行按慢者。1、2过(2)，1回(1)，5、10过(10)，2回(2)，1、2过(2)，总17。慢者一起运送，比反复由1护送节省：两慢者分开至少付5+10，再加回程与运快者；最优结构可比较 $a+3b+d$ 与 $2a+b+c+d$，此处17与19。不要将17套到任意四个时间。

狐狸、鸡、谷物。 人先带鸡过，独返，带狐狸过，带鸡返，带谷物过，独返，再带鸡过。每步检查两岸无人看守时不能有狐鸡或鸡谷。解法可系统化为状态搜索：四个二进制位表示所在岸，排除危险状态后 BFS，单位成本下得到最短合法路径。

14. 补齐概率：条件、状态和积分

14.1 面条围圈：n 根面条随机接端点

原回忆仅称“一根面条围圈”，缺少随机机制。这里采用标准版本：n 根面条的2n个端点，每次从尚未连接的端点中均匀选两个相接，直到全接好，求圈数期望。若真的只有一根且必接两端，答案当然是1。

当还有 k 条开放链时，任选一个端点，在其余 $2k-1$ 个端点中，恰一个是同链另一端，选到它就新闭合一圈。无论本轮合并还是闭环，开放链数都从 k 降至 k−1。以每轮是否新成圈的指示量求和：

$$E[C_n]=\sum_{k=1}^n\frac1{2k-1}=H_{2n}-\frac12H_n.$$

n=2 时三种配对中一种生成两个圈，另两种一个圈，期望4/3，与1+1/3一致。它不是 Coupon Collector，也无需假定各轮事件独立。

14.2 A 抛 n+1 枚、B 抛 n 枚：A 正面更多的概率

先让 A、B 各抛 n 枚，差记为 D，因交换两人不改分布，有 $P(D>0)=P(D<0)$。A 再抛额外一枚：D>0 时必胜，D=0 时半数胜，D<0 时不能严格胜。因此 $P(A>B)=P(D>0)+P(D=0)/2=1/2$。关键是“多一枚”恰好一半打破平局；若硬币不公平或两人硬币概率不同，对称性不成立。

14.3 HH、HT 等待时间，及 HTH 与 HHT 谁先出现

HH。 用 $E_0,E_H$ 表示无有效后缀、后缀为 H 时还需抛数。$E_0=1+(E_0+E_H)/2$，$E_H=1+E_0/2$，联立得 $E_0=6,E_H=4$。

HT。 第一式不变，但 $E_H=1+E_H/2$，因为再出 H 仍保留后缀 H，出 T 则完成；故 $E_H=2,E_0=4$。要解释的是状态回退区别，不能仅说“HH 比较难”。

竞争。 设 $u_s$ 为后缀 s 下 HTH 先于 HHT 完成的概率，有效后缀为 ∅、H、HT、HH。边界成功=1、失败=0。$u_0=u_H$，$u_H=(u_{HT}+u_{HH})/2$，$u_{HT}=(1+u_0)/2$，$u_{HH}=u_{HH}/2$。于是 $u_{HH}=0$，$u_0=(1+u_0)/4$，得 1/3；HHT 胜率2/3。单个模式等待时间和两模式竞赛是不同问题。

14.4 连续 r 次成功：从状态方程推到闭式

状态 $E_i$：已经连续 i 次成功，还需的尝试数；$E_r=0$，对 i<r 有 $E_i=1+pE_{i+1}+(1-p)E_0$。令 $A=1+(1-p)E_0$，从尾向前代入得到 $E_0=A(1+p+\cdots+p^{r-1})$。

将 A 展开并移项：$p^rE_0=(1-p^r)/(1-p)$，因此 $E_0=(1-p^r)/((1-p)p^r)$。p=1 时单独取极限 r，p=0 时无穷；r=1 时回到几何分布1/p。骰子六连6为 $6+36+216+1296+7776+46656=55986$。

14.5 双面硬币的后验、时间戳缺失

100枚硬币等概率选一枚，其中1枚双正，99枚公平，连出10个正。假设 D 表示双正，证据 H 表示10正：

$$P(D\mid H)=\frac{(1/100)\cdot1}{(1/100)+(99/100)2^{-10}}=\frac{1024}{1123}\approx0.91184.$$

似然与先验都不能漏。 10正不是公平币不可能发生，且公平币先验数量多99倍。一般先验π、m次全正可写 $\pi/[\pi+(1-\pi)2^{-m}]$。

时间戳练习。 缺测率π，缺测一律补9个0，真实记录末9位恰为0概率q，观察到9个0后的缺测后验为 $\pi/[\pi+(1-\pi)q]$。只有在真实纳秒尾数均匀时才可设 $q=10^{-9}$；若系统按整秒生成数据，q可能很大。原题未给π、q，不能报唯一数值。

14.6 赌徒破产、酒鬼下桥、偏游走到 −1

在0～N整数位置游走，初始i，每步以p向右、q=1−p向左，碰边界停止。到N的概率满足 $h_i=ph_{i+1}+qh_{i-1}$、$h_0=0,h_N=1$。

齐次差分方程的两根为1和q/p，故 p≠q 时 $h_i=[1-(q/p)^i]/[1-(q/p)^N]$；公平时重根得到直线 $h_i=i/N$。期望时间满足 $t_i=1+pt_{i+1}+qt_{i-1}$，边界0；公平时代入二次函数得 $t_i=i(N-i)$，不公平时 $t_i=(Nh_i-i)/(p-q)$。例：桥0～10，从4出发，公平右端离桥概率0.4，平均24步。

无限直线上从0出发，p=2/3向上，q=1/3向下，最终到−1概率为q/p=1/2，可先设远端N、解有限区间后令N→∞。有1/2路径永不到达，所以把未到达时间记无穷时，无条件到达时间期望是无穷，不能混成“概率1/2故平均两步”。

14.7 无放回抽到第一张 A 的期望

52张牌有4张A，随机排列。4张A将48张非A分成5段，包括头尾。按对称性，每段非A期望48/5；第一张A的位置为头段长度+1，故 53/5=10.6。一般N张K张目标牌，期望$(N+1)/(K+1)$。若有放回，每次成功K/N，等待期望N/K，两者不同。

14.8 飞镖：第二支比第一支远，第三支的概率究竟是多少

设距离 $R_1,R_2,R_3$ 独立同分布连续，已知 $R_2>R_1$。三支相对大小6种等可能，满足已知条件剩3种：$R_1<R_2<R_3$、$R_1<R_3<R_2$、$R_3<R_1<R_2$。

若问第三支比第二支远，只有第一种，概率 1/3；若问第三支比第一支远，有前两种，概率 2/3。不需要知道距离具体分布；但若投手逐次调整瞄准或给定了第二支实际距离r，则不能只枚举对称排序。

14.9 三个独立均匀边长：锐角概率算到底

令最大边为z，另外两边x、y在(0,z)内；锐角条件 $x^2+y^2>z^2$ 自动蕴含 $x+y>z$。在边长z的正方形里，满足条件是第一象限四分之一圆外的区域，面积 $z^2(1-\pi/4)$。最大边可以是三个变量中的任意一个：

$$P(\text{锐角})=3\int_0^1 z^2(1-\pi/4)\,dz=1-\pi/4\approx0.214602.$$

成三角形概率1/2，故已经能组成三角形的条件下锐角概率为 $2-\pi/2\approx0.429204$。若先随机截断一根棒成三段，总和固定，样本空间变成单纯形，不能套这两个数。

14.10 单位正方形：离中心比离最近边更近

把正方形放在 $[-1,1]^2$，均匀面积抽样。由对称性，只算 $0\le y\le x\le1$ 的八分之一区域。到中心为 $\sqrt{x^2+y^2}$，到最近边为 $1-x$。不等式平方得 $y^2<1-2x$，因此 $0\le y<\min(x,\sqrt{1-2x})$，且 x<1/2。

两上界相交于 $a=\sqrt2-1$。全区域概率为8倍面积除以总面积4：

$$P=2\left[\int_0^a x\,dx+\int_a^{1/2}\sqrt{1-2x}\,dx\right]=a^2+\frac23a^3=\frac{4\sqrt2-5}{3}\approx0.218951.$$

最近角版本另算。 在第一象限，最近角(1,1)，比较平方距离得到x+y<1；占该象限一半，故概率1/2。最近边与最近角不是同一道题。

14.11 圆内抛物线区域：缺方程时如何规范解答

原题标题没有给出抛物线方程。取自拟练习：单位圆 $x^2+y^2\le1$ 内均匀点，求 y>x² 的概率。两曲线交点横坐标满足 $x^4+x^2=1$，令 $a=\sqrt{(\sqrt5-1)/2}$。

$$P=\frac1\pi\int_{-a}^{a}(\sqrt{1-x^2}-x^2)dx=\frac{a\sqrt{1-a^2}+\arcsin a-2a^3/3}{\pi}.$$

先找相交点，再用上曲线减下曲线，最后除以圆面积π。若原题是y>ax²+b，需重新解交点并判断空集/全集；若按半径均匀采样，点并非面积均匀，面积法就不适用。

14.12 嵌套随机区间：长度、中心和停止必须区分

随机保留左半或右半。 从[0,1]开始，独立等概率保留一半，做n次。长度确定为 $2^{-n}$，其标准差为0。中心为 $C_n=2^{-(n+1)}+\sum_{j=1}^n B_j2^{-j}$，$B_j$为独立公平0/1，因此 $\operatorname{Var}(C_n)=(1-4^{-n})/12$。极限中心服从U(0,1)，标准差趋于$1/\sqrt{12}$。

从[0,L]均匀选点作新右端点。 $L_n=\prod_{j=1}^nU_j$，故 $E[L_n]=2^{-n}$，$E[L_n^2]=3^{-n}$，方差 $3^{-n}-4^{-n}$。遇到“嵌套随机区间”先问每轮抽一个端点还是两个端点、保留哪段、求长度还是中心；不能把上述两组公式混用。

14.13 均匀抽数最优停止：从最后一轮倒推阈值

自拟标准练习。 最多n次独立U(0,1)，看到数可接受并结束，拒绝后不能回选，无成本且最后一次必须接受。令 $V_n$ 为开始前最优期望，$V_1=1/2$。当前x只有在x≥$V_{n-1}$时值得接受：

$$V_n=\int_0^1\max(x,V_{n-1})dx=\frac{1+V_{n-1}^2}{2}.$$

V₂=5/8，V₃=89/128。注意阈值是剩余机会的价值，而不是固定1/2。若无限次且每次重抽成本c，Bellman方程改成 $V=E[\max(X,V-c)]$；成本或回选规则不同，策略会变。

14.14 随机歌曲、听花、抛物线下均匀点

歌曲练习。 A有m首、B有n首(n≥2)，所有歌曲随机排列，A全部出现在B第二首之前。在只保留A/B的子序列中，A末首以前至多一个B。合法类型串共1+m种，总共$\binom{m+n}{m}$，概率 $(m+1)/\binom{m+n}{m}$。例m=n=2得1/2；其他歌手的歌不影响A/B相对次序。

德州扑克听花。 已知手牌2张和翻牌3张中同花4张，剩47张未知有9张补花；转牌即成9/47；转河至少一次成花 $1-(38/47)(37/46)=1-\binom{38}{2}/\binom{47}{2}$。这是已知这些牌且未知其余牌的模型；对手亮牌后分母和outs须改。

抛物线下均匀点练习。 区域 $0<x<1,0<y<x^2$ 面积1/3，所以密度3。$E[X]=3\int_0^1x\cdot x^2dx=3/4$，$E[Y]=3\int_0^1x^4/2\,dx=3/10$。注意X并非U(0,1)，它的边缘密度为3x²，横向宽处更容易取到点。

15. 绿皮书其他章节的基础补全

15.1 微积分与约束优化：一份可演算的例题

练习。 在x+y=1下最小化$x^2+2y^2$。直接代入y=1−x，目标变$3x^2-4x+2$，一阶导6x−4=0，得x=2/3、y=1/3；二阶导6>0证明全局最小，值2/3。

拉格朗日法令 $L=x^2+2y^2+\lambda(x+y-1)$，一阶条件2x+λ=0、4y+λ=0和约束，解一致。它训练组合最小方差的同一结构：用乘子处理约束，再用凸性证明最优；只有一阶导为0并不总是极小值。

泰勒与牛顿。 从 $f(x+\Delta)\approx f(x)+f'(x)\Delta$，令右边0得 $x_{k+1}=x_k-f(x_k)/f'(x_k)$。求√2即迭代$(x+2/x)/2$，x₀=1→1.5→1.416667→1.414216。导数接近0或初值不合适会失败，可用保留根区间的二分法兜底。

15.2 OLS、QR、PCA：三个问题的一条几何主线

OLS。 最小化$\|y-X\beta\|^2$，梯度$2X^T(X\beta-y)=0$，正规方程$X^TX\beta=X^Ty$。若满列秩，唯一解$(X^TX)^{-1}X^Ty$；实际不要显式求逆，用QR或SVD。QR写X=QR，因Q列正交，解上三角$R\beta=Q^Ty$即可。例$x=(0,1,2),y=(1,2,2)$，带截距斜率1/2，截距7/6。

梯度下降。 用损失$\|X\beta-y\|^2/(2n)$，梯度$X^T(X\beta-y)/n$，每步β减η倍梯度。全批二次问题在 $0<\eta<2/\lambda_{\max}(X^TX/n)$ 且满秩下收敛；列尺度悬殊会慢。不能只写更新而不解释步长。

PCA。 中心化数据协方差S，找单位向量v使投影方差$v^TSv$最大。拉格朗日一阶条件Sv=λv，最大值是最大特征值。减去第一主方向后继续在正交补求解。PCA不看标签，最大方差不保证最有预测力；只能在训练数据上拟合中心、尺度和主轴。

15.3 等相关矩阵求逆、PSD 修复、矩阵多项式

求逆。 设$R=(1-c)I+c11^T$，猜逆为αI+β11ᵀ，用$(11^T)^2=n11^T$展开乘积，比较I项与11ᵀ项得：

$$R^{-1}=\frac1{1-c}\left(I-\frac{c}{1+(n-1)c}11^T\right).$$

要求c≠1且c≠−1/(n−1)，端点矩阵奇异。例n=2可与普通2×2求逆交叉核对。

近PSD协方差。 先对称化S←(S+Sᵀ)/2，特征分解QΛQᵀ，把负特征值截到0得QΛ₊Qᵀ。这是对称矩阵在Frobenius范数下投影到PSD锥；若还要求对角为1，单次截断不保证满足，需额外投影或适当归一化，不能称一次完成“最近相关矩阵”。

$A^5+A^3+A=3I$。 若A实对称，任一实特征值λ满足λ⁵+λ³+λ=3，左边导数5λ⁴+3λ²+1>0，唯一实根1，所以A=I。若A一般实矩阵，非实共轭根可形成2×2实块，不能直接说A=I；必须先确认对称或其他谱限制。

15.4 旋转矩阵与特征值

二维旋转$R_\theta=\begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}$，两列单位且正交，故RᵀR=I；特征方程λ²−2cosθ λ+1=0，根$e^{\pm i\theta}$，不是所有实正交矩阵都有实特征值。

绕三维单位轴u旋转180°，沿轴分量不变、垂直分量取反。任意v分解$(uu^T)v+(I-uu^T)v$，变换后$(2uu^T-I)v$，所以R=2uuᵀ−I，特征值1、−1、−1，行列式1。轴向量必须先归一化。

15.5 随机过程：从布朗运动到 GBM 的对数

布朗增量$\Delta W\sim N(0,\Delta t)$，所以$(\Delta W)^2$累计不消失，极限贡献dt。Itô公式因此比普通链式法则多半个二阶导项：若dX=a dt+b dW，则$df=(f_t+af_x+b^2f_{xx}/2)dt+bf_xdW$。

对$dS=\mu Sdt+\sigma SdW$取f=logS，$f'=1/S,f''=-1/S^2$，得到$d\log S=(\mu-\sigma^2/2)dt+\sigma dW$，积分得$S_t=S_0e^{(\mu-\sigma^2/2)t+\sigma W_t}$。于是$E[S_t]=S_0e^{\mu t}$，对数均值却为$\log S_0+(\mu-\sigma^2/2)t$。这是“均值增长”和“典型复利路径”不同的来源。

15.6 无套利定价：BS PDE 与数字看涨 delta

课堂模型。 无分红股票服从GBM，连续交易、可借贷、无成本，r、σ常数。期权V(S,t)的Itô展开含随机项σSV_S dW，用持有$\Delta=V_S$股的自融资对冲消去该项，剩余无风险组合按r增长，整理得：

$$V_t+\frac12\sigma^2S^2V_{SS}+rSV_S-rV=0.$$

终值决定具体合约；数字看涨到期支付$1_{S_T>K}$，风险中性价$D=e^{-r\tau}\Phi(d_2)$，其中$d_2=[\log(S/K)+(r-\sigma^2/2)\tau]/(\sigma\sqrt\tau)$。对S求导：$\Delta_D=e^{-r\tau}\phi(d_2)/(S\sigma\sqrt\tau)$。现金支付Q再乘Q。临近到期且价平附近delta可很尖；不能把它当普通call的Φ(d₁)。这些是定价模型推导，不是可直接执行的交易建议。

15.7 统计和数值计算的自测题

均匀次序统计量。 n个U(0,1)最大值M，$F_M(x)=x^n$，密度nxⁿ⁻¹，积分得$E[M]=n/(n+1)$。第k小的期望k/(n+1)，可用n+1个间隔对称性理解。

Monte Carlo。 用N个独立样本均值估μ，方差σ²/N，标准误σ/√N；误差缩小十倍通常要一百倍样本。对偶变量把U与1−U成对使用，只有诱发负相关时才降方差；控制变量估计$Y-b(X-E[X])$最优b=Cov(X,Y)/Var(X)，与最小方差对冲同形。

数值验证不是证明。 模拟能发现漏因子、方向写反，但罕见事件和无限期望不能靠“跑了一万次都结束”判定。先给解析递推，再以小参数穷举、积分或模拟做交叉检查。