DevDocs

主题

概率题 ​

本章目标：修正概率直觉偏差，学会用条件概率和贝叶斯思维严谨求解。

题型特点 ​

概率题是面试中最容易"答错"的题型，因为人类对概率的直觉极不可靠。你的第一直觉很可能是错的，这正是面试官想看到的——你会不会轻易被直觉骗到，以及你能否用严谨的方法修正。

解题核心工具：样本空间枚举 → 条件概率公式 → 贝叶斯定理。关键是不信任直觉，一切用数学说话。

概率工具速查 ​

基础公式 ​

条件概率：

P(A∣B)=P(A∩B)P(B)P(A \mid B) = \frac{P(A \cap B)}{P(B)}

乘法公式：P(A ∩ B) = P(B) · P(A | B)

全概率公式（若 B₁, B₂, …, Bₙ 互斥且并为全集）：

P(A)=∑iP(A∣Bi)⋅P(Bi)P(A) = \sum_i P(A \mid B_i) \cdot P(B_i)

贝叶斯定理（后验 ∝ 似然 × 先验）：

P(Bi∣A)=P(A∣Bi)⋅P(Bi)∑jP(A∣Bj)⋅P(Bj)P(B_i \mid A) = \frac{P(A \mid B_i) \cdot P(B_i)}{\sum_j P(A \mid B_j) \cdot P(B_j)}

常见分布的期望与方差 ​

分布期望方差
伯努利(p)pp(1-p)
二项(n, p)npnp(1-p)
几何(p)（首次成功所需次数）1/p(1-p)/p²
帕斯卡(r, p)（r 次成功所需次数）r/pr(1-p)/p²
均匀(a, b)(a+b)/2(b-a)²/12
指数(λ)1/λ1/λ²

实用结论 ​

  • 几何分布无记忆性：已掷 5 次硬币没正面，第 6 次正面的概率仍 1/2。
  • 期望线性性：E[X+Y] = E[X] + E[Y]，无论 X、Y 是否独立。
  • 乘积期望：E[XY] = E[X]·E[Y] 仅当 X、Y 独立时成立。
  • 指示器技巧：把复杂随机变量拆成若干 0/1 指示器之和，期望相加。

题目 1：三门问题（Monty Hall） ​

题面 ​

你参加一个电视游戏节目。有三扇门，一扇后面是跑车，两扇后面是山羊。你选了 1 号门。**主持人（知道车在哪）**打开了 3 号门，后面是山羊。主持人问："你要不要换成 2 号门？"换门对你有利吗？

拆解与思考 ​

直觉陷阱：很多人觉得剩下两扇门概率各 1/2，换不换无所谓。

正确分析：一开始你选 1 号门，猜中概率 1/3，猜不中 2/3。主持人的行为不是随机的——他必定打开一扇有山羊的门。所以主持人的行为提供了信息，但不改变你初始 1/3 的概率。

  • 车在 1 号（概率 1/3）：不换赢。
  • 车在 2 号或 3 号（概率 2/3）：主持人会打开另一只有羊的门，你换到有车的那扇，换赢。

所以换的胜率是 2/3，不换的胜率是 1/3。

严格贝叶斯推导 ​

设车在 1 号门为事件 C₁，主持人开 3 号门为 H₃。

先验 P(C₁) = P(C₂) = P(C₃) = 1/3。

似然：

  • P(H₃ | C₁) = 1/2：车在 1 号，主持人随机开 2 或 3。
  • P(H₃ | C₂) = 1：车在 2 号，主持人必开 3 号。
  • P(H₃ | C₃) = 0：车在 3 号，主持人不能开 3 号。

后验：

P(C1∣H3)=P(H3∣C1)P(C1)P(H3)=(1/2)(1/3)(1/2)(1/3)+1⋅(1/3)+0=1/61/2=13P(C_1 | H_3) = \frac{P(H_3 | C_1) P(C_1)}{P(H_3)} = \frac{(1/2)(1/3)}{(1/2)(1/3) + 1 \cdot (1/3) + 0} = \frac{1/6}{1/2} = \frac{1}{3}

P(C2∣H3)=1⋅(1/3)1/2=23P(C_2 | H_3) = \frac{1 \cdot (1/3)}{1/2} = \frac{2}{3}

答案 ​

必须换。 换的胜率是 2/3，不换的胜率是 1/3。

延伸：极端变体 ​

100 扇门：你选 1 号，主持人打开 98 扇有山羊的门，问你要不要换到剩下的那扇？此时换的胜率高达 99/100，直觉上明显多了。

主持人不知情版（Monty Fall）：主持人不知道车在哪，随机开了一扇，恰好是山羊。此时换不换无区别，各 1/2。

这两个版本的对比说明：主持人的知情与否决定概率，而不只是表面动作。

直觉陷阱的本质 ​

人们误以为是"两扇门二选一"，但实质是"我最初选错的概率"vs"主持人帮我排除了一个错误后剩下的概率"。主持人的"知道"使他不随机开门——信息流向关键。

题目 2：双孩问题 ​

题面 ​

你的朋友有两个孩子。你得知"其中至少有一个是男孩"。请问另一个也是男孩的概率是多少？（假设生男生女等概率）

拆解与思考 ​

直觉陷阱：很多人立刻回答 1/2——"另一个孩子的性别独立，所以是 1/2"。

正确分析：用样本空间枚举。两个孩子的可能组合（按出生顺序）：

组合描述
BB老大男，老二男
BG老大男，老二女
GB老大女，老二男
GG老大女，老二女

每种概率 1/4。条件"至少一个男孩"排除了 GG，剩下三种等可能：BB、BG、GB。

"另一个也是男孩"即 BB，概率 = 1/3。

答案 ​

另一个也是男孩的概率是 1/3。

措辞的微妙影响 ​

已知信息答案
至少一个男孩1/3
老大是男孩1/2
我看到一个男孩（不指定是老大还是老二）1/3
那个孩子是男孩（特定指某一个）1/2
至少一个男孩生于星期二13/27（接近 1/2，反直觉）

星期二男孩悖论：条件越具体（指定星期几），概率越接近 1/2。这是因为条件越具体，样本空间越小，被排除的情况越多。

延伸 ​

措辞的微妙差异会导致概率巨变——这是条件概率的精髓。面试时一定要把条件说清楚、写下来，避免口头歧义。

题目 3：生日悖论 ​

题面 ​

一个房间至少需要多少人，才能让"至少两个人生日相同"的概率超过 50%？（不考虑闰年，假设生日均匀分布）

拆解与思考 ​

直觉陷阱：一年 365 天，感觉需要 365/2 ≈ 183 人才有 50% 机会。

正确分析：正面计算"至少两人同生日"很复杂，转而算"所有人生日都不同"的概率，再用 1 减。

n 个人的房间，所有人生日都不同的概率：

P(\text{全不同}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{365-n+1}{365}

逐项计算：

nP(至少两人同生日)
52.7%
1011.7%
2350.7%
3070.6%
5097.0%
7099.9%

n=23 时概率恰好超过 50%。

直觉错在哪 ​

人们往往只拿"自己"和别人比（22 次比较），而实际上任意两人之间都可以配对。23 人有 C(23,2) = 253 对组合——配对数远超直觉。

近似公式 ​

当 n 远小于 365：

P(\text{至少两人同生日}) \approx 1 - e^{-n^2 / (2 \cdot 365)}

令其等于 1/2，解得 n ≈ √(2 × 365 × ln 2) ≈ 22.5，与精确值 23 一致。

答案 ​

只需 23 人，"至少两人生日相同"的概率就超过 50%。

延伸：生日攻击 ​

生日悖论是密码学的重要概念。n 位哈希只需约 2^(n/2) 次运算就能以高概率碰撞。这也是为什么哈希值至少需要 256 位——128 位哈希只需 2^64 ≈ 1.8×10¹⁹ 次运算即可碰撞，对现代计算能力而言不再安全。

工程上：MD5（128 位）已被破解；SHA-1（160 位）已被破解；SHA-256 仍是安全标准。

题目 4：赌徒破产问题 ​

题面 ​

一个赌徒初始有 n 元，每次以概率 p 赢 1 元、概率 q=1-p 输 1 元。目标是到达 N 元（N > n）就收手，或者到 0 元就破产。问破产概率是多少？

拆解与思考 ​

设 P(k) 是当前有 k 元时的破产概率。边界条件：P(0) = 1（已破产），P(N) = 0（已达到目标）。

递推关系：

P(k)=p⋅P(k+1)+q⋅P(k−1)P(k) = p \cdot P(k+1) + q \cdot P(k-1)

这是二阶线性递推。特征方程 p x² - x + q = 0，两根 x=1 和 x=q/p。

当 p ≠ q（即 p ≠ 1/2），通解 P(k) = A + B · (q/p)^k。代入边界条件解得：

P(n)=(q/p)n−(q/p)N1−(q/p)NP(n) = \frac{(q/p)^n - (q/p)^N}{1 - (q/p)^N}

当 p = q = 1/2（公平赌博），取极限得 P(n) = 1 - n/N。

答案 ​

  • 公平赌博（p=1/2）：破产概率 = 1 - n/N。即使公平，只要你玩得够久（N → ∞），破产概率趋于 100%。
  • 不利赌博（p < 1/2）：q/p > 1，分子分母都趋向 (q/p)^N，破产概率接近 1。
  • 有利赌博（p > 1/2）：q/p < 1，(q/p)^N → 0，破产概率近似 (q/p)^n。

数值例子 ​

赌场优势pn/N破产概率
公平0.50.550%
公平0.50.190%
1% 劣势0.490.5≈ 100%
1% 优势0.510.5≈ 0%

延伸 ​

这就是为什么"久赌必输"在数学上是正确的——即使每次期望为零（公平赌局），有限资本面对无限资本（庄家），破产概率趋于 1。现实赌场还有"赌场优势"（轮盘的 0、21 点的庄家优先等），p 永远小于 1/2。

工程意义：资金管理比"赢得概率"更重要。凯利公式（Kelly Criterion）给出最优下注比例：f* = (bp - q) / b，其中 b 是赔率。

题目 5：圣彼得堡悖论 ​

题面 ​

一个游戏：你付一笔入场费，然后掷硬币。如果第 n 次才出现正面，你赢得 2^n 元。这个游戏的期望收益是多少？你愿意付多少钱玩？

拆解与思考 ​

计算期望值：

E=∑n=1∞12n⋅2n=∑n=1∞1=∞E = \sum_{n=1}^{\infty} \frac{1}{2^n} \cdot 2^n = \sum_{n=1}^{\infty} 1 = \infty

期望收益是无穷大！但大多数人只愿意付几十元来玩。这就是悖论。

答案 ​

数学期望是无穷大，但理性人只愿付有限金额（通常 10-40 元）。

解释 ​

解释 1：对数效用（伯努利）

人们评估的不是金钱本身，而是金钱的"效用"。伯努利提出效用函数 U(x) = ln(x)。重新计算：

E[U]=∑n=1∞12n⋅ln(2n)=ln2⋅∑n=1∞n2n=2ln2E[U] = \sum_{n=1}^{\infty} \frac{1}{2^n} \cdot \ln(2^n) = \ln 2 \cdot \sum_{n=1}^{\infty} \frac{n}{2^n} = 2 \ln 2

对应确定等价值 e^{2 ln 2} = 4 元——和直觉吻合。

解释 2：有限资金约束

现实中没人有无限财富赔付。若庄家最多有 2^20 ≈ 100 万 元，则期望收益约为 20 元，与人们愿意支付的金额相当。

解释 3：风险规避

大额奖金的边际效用递减，且人们厌恶极端方差。

延伸 ​

这个悖论催生了期望效用理论，是现代经济学和决策理论的基石之一。冯·诺依曼-摩根斯特恩定理（vNM）形式化了"理性偏好"的公理基础。

题目 6：抛硬币直到连续 k 次正面 ​

题面 ​

反复抛一枚公平硬币，直到连续出现 k 次正面为止。求抛掷次数的期望值。

拆解与思考 ​

设 E(i) 是当前已连续 i 次正面、到游戏结束的期望抛掷次数。目标：求 E(0)。

状态转移：

  • E(k) = 0（已经连续 k 次，游戏结束）
  • E(i) = (1/2) · (1 + E(i+1)) + (1/2) · (1 + E(0))，i = 0, 1, …, k-1

（下一次正面 → 状态 i+1；下一次反面 → 重置到 0。）

k=3 的求解：

  • E(2) = 1/2 · 1 + 1/2 · (1 + E(0)) = 1 + E(0)/2
  • E(1) = 1/2 · (1 + E(2)) + 1/2 · (1 + E(0)) = 1 + E(2)/2 + E(0)/2
  • E(0) = 1/2 · (1 + E(1)) + 1/2 · (1 + E(0)) = 1 + E(1)/2 + E(0)/2

逐一代入求解：E(0) = 14。

一般公式 ​

对公平硬币：

E(\text{连续 } k \text{ 次正面}) = 2^{k+1} - 2
k期望次数
12
26
314
430
562
102046

指数增长是关键——连续 10 次正面的期望抛掷数超过 2000。

一般情况（概率 p） ​

连续 n 次出现某事件（概率 p）的期望试验次数为：

E=1−pn(1−p)⋅pn=p−n−11−pE = \frac{1 - p^n}{(1-p) \cdot p^n} = \frac{p^{-n} - 1}{1-p}

当 p=1/2 时简化为 2^{n+1} - 2。

工程意义 ​

模式匹配的期望等待时间——KMP 算法、字符串搜索的复杂度分析有类似结构。

题目 7：贝叶斯医疗检测（假阳性陷阱） ​

题面 ​

某病在人群中发病率为 1%。某检测准确率为：患者中 90% 阳性（灵敏度），健康人中 10% 阳性（假阳性率）。某人检测为阳性，请问他真正患病的概率是多少？

拆解与思考 ​

直觉陷阱：很多人觉得"准确率 90%"，所以患病的概率是 90%。

正确分析：用贝叶斯。设事件 D（患病）、+（阳性）。

  • 先验：P(D) = 0.01，P(¬D) = 0.99
  • 似然：P(+ | D) = 0.9，P(+ | ¬D) = 0.1

P(D∣+)=P(+∣D)P(D)P(+)=0.9×0.010.9×0.01+0.1×0.99=0.0090.108≈8.3%P(D | +) = \frac{P(+ | D) P(D)}{P(+)} = \frac{0.9 \times 0.01}{0.9 \times 0.01 + 0.1 \times 0.99} = \frac{0.009}{0.108} \approx 8.3\%

答案 ​

阳性者真正患病的概率只有约 8.3%，远低于直觉的 90%。

为什么这么低 ​

基础率谬误（base rate fallacy）：因为健康人占 99%，假阳性的人数远超真阳性。

具体数字（1000 人样本）：

类别人数阳性阴性
患者1091
健康人99099891
合计—108892

108 个阳性中，只有 9 个真患者，占比 8.3%。

延伸：如何提高准确率 ​

  • 重复检测：第二次独立检测若仍阳性，则 P(D | ++) 大幅上升。
  • 高风险人群筛查：在有症状者中发病率上升到 50%，则阳性预测值跃升至 90%。
  • 多指标融合：机器学习的诊断模型就是综合多个特征的贝叶斯推断。

工程意义：垃圾邮件过滤、欺诈检测、推荐系统中，假阳性控制与基础率密切相关——这就是为什么 ML 模型在不平衡数据上易出问题。

题目 8：飞机乘客找座位 ​

题面 ​

100 个乘客排队登机。第一个乘客弄丢了登机牌，随机选一个座位坐下。其他乘客如果自己座位空着就坐那儿，否则随机选一个空座。问：最后一个乘客能坐到自己座位的概率？

拆解与思考 ​

直觉：看似很复杂，要分多种情况。

关键洞察：注意一个不变量——第一个乘客选的座位，要么是 1 号（他自己的），要么是 100 号（最后一位的），要么是某个中间乘客的。

  • 若他选 1 号：所有人都坐自己座位，第 100 号乘客坐到自己的座。
  • 若他选 100 号：第 100 号乘客无座可选（除了被占的 100 号）。
  • 若他选第 k 号（2 ≤ k ≤ 99）：第 k 号乘客被迫"随机选"。这个随机选择再次面临同样的三选项！

等价模型：把第一个乘客和后续"被迫随机"的乘客看作同一个角色。最终问题归约为：第一个随机选座的人最终选到 1 号还是 100 号——这两者对称，概率各 1/2。

答案 ​

最后一个乘客坐到自己座位的概率是 1/2。

推广 ​

n 个乘客的情况，答案仍是 1/2（n ≥ 2）。无论人数多少，对称性保证 50%。

严谨证明（归纳法） ​

设 f(n) 是 n 人时最后一人坐到自己的座的概率。

  • f(2) = 1/2：第一人随机选，1/2 选自己（末位有座），1/2 选末位（末位无座）。
  • 假设 f(k) = 1/2 对所有 k < n。考虑 n 人，第一人选：
    • 1 号位（1/n 概率）：末位有座。
    • n 号位（1/n 概率）：末位无座。
    • k 号位（2 ≤ k ≤ n-1，共 n-2 个位置，每个 1/n）：第 k 人被迫随机，问题降为 n-k+1 人的子问题，由归纳假设概率 1/2。

求和：f(n) = 1/n · 1 + 1/n · 0 + Σ(1/n · 1/2) = 1/n + 0 + (n-2)/(2n) = (2 + n - 2)/(2n) = 1/2。

题目 9：秘书问题（最优停止） ​

题面 ​

要面试 n 个候选人，逐一面谈后必须当场决定是否录用，不能回头选已拒绝的。每个候选人有客观的"分数"，但只能两两比较（不知绝对值）。如何最大化选中最佳候选人的概率？

拆解与思考 ​

最优策略（37% 法则）：

  1. 先观察前 r = n/e ≈ 0.368n 个候选人，全部拒绝，记住这批中最高分 M。
  2. 之后遇到的第一个分数超过 M 的候选人，立即录用。
  3. 若没有超过 M 的，被迫录用最后一个。

为什么是 1/e：

设策略以 r 为分界点。选中最佳候选人的概率：

P(r) = \sum_{k=r+1}^{n} P(\text{第 } k \text{ 个是最佳}) \cdot P(\text{第 } k \text{ 个被选})
  • P(第 k 个是最佳) = 1/n
  • P(第 k 个被选 | 第 k 个是最佳) = r/(k-1)（前 k-1 个中的最高分必须在前 r 个中）

所以：

P(r)=rn∑k=r+1n1k−1≈r∫r1dtt=−rlnrP(r) = \frac{r}{n} \sum_{k=r+1}^{n} \frac{1}{k-1} \approx r \int_r^1 \frac{dt}{t} = -r \ln r

对 r 求导得最大值在 r = 1/e ≈ 0.368，此时 P(r) = 1/e ≈ 0.368。

答案 ​

使用 37% 法则：先观察 37% 的样本，然后选第一个超过样本最佳的。选中最佳的概率约为 1/e ≈ 36.8%。

延伸 ​

  • n 很大时仍然只 36.8%？是的，这就是无信息先验下的理论上界。
  • 可变策略：若有"全拒了"的兜底（最后必须选一个），最优解不变。
  • 有信息版：若知道分数分布，可改为阈值策略，胜率显著提升。

工程意义：在线算法、流式数据中的"最优选择"问题——这种"过时不候"的设定在求职、相亲、买房、卖股中无处不在。

题目 10：优惠券收集问题 ​

题面 ​

某品牌有 n 种不同的优惠券，每件商品随机附赠 1 张（均匀分布）。期望要买多少件商品才能集齐 n 种优惠券？

拆解与思考 ​

把过程分为 n 个阶段：第 i 阶段是"已经集了 i-1 种，正在收集第 i 种新券"。

  • 第 1 阶段：第一次必是新券，期望 1 次。
  • 第 i 阶段（1 < i ≤ n）：每次获得新券的概率 (n - (i-1)) / n = (n-i+1)/n。这是几何分布，期望 n/(n-i+1)。

总期望：

E=∑i=1nnn−i+1=n⋅HnE = \sum_{i=1}^{n} \frac{n}{n - i + 1} = n \cdot H_n

其中 H_n = 1 + 1/2 + 1/3 + … + 1/n 是第 n 个调和数。

答案 ​

期望购买次数 = n · H_n。

对于大 n，H_n ≈ ln n + γ（γ ≈ 0.5772 为欧拉-马歇罗尼常数），所以：

E≈nlnn+0.5772nE \approx n \ln n + 0.5772 n

n期望次数
511.4
1029.3
50225
100519
3652365

注意 365 这个数字：要集齐 365 个"生日"，期望需要 2365 人——这从反面呼应了生日悖论。

延伸：方差 ​

收集次数的方差为：

Var=∑i=1nn(i−1)(n−i+1)2\text{Var} = \sum_{i=1}^{n} \frac{n(i-1)}{(n-i+1)^2}

大约 n² · π²/6，标准差与 n 同数量级，分布有长尾。

工程意义：哈希表分析、负载均衡、随机抽样、网络爬虫的"覆盖率"评估都基于此模型。

题目 11：两枚硬币诡计 ​

题面 ​

桌上有 3 枚硬币：

  • A：两面都是正面（双正）。
  • B：两面都是反面（双反）。
  • C：一正一反（公平）。

随机选一枚抛出，结果是正面。问：这枚是双正币 A 的概率？

拆解与思考 ​

直觉陷阱：很多人回答 1/2，因为"看到正面"似乎排除了 B，剩 A 和 C 各半。

贝叶斯：

  • 先验：P(A) = P(B) = P(C) = 1/3
  • 似然：P(正面 | A) = 1，P(正面 | B) = 0，P(正面 | C) = 1/2
P(A | \text{正面}) = \frac{1 \cdot 1/3}{1 \cdot 1/3 + 0 + 1/2 \cdot 1/3} = \frac{1/3}{1/2} = \frac{2}{3}

答案 ​

是双正币 A 的概率是 2/3，不是 1/2。

为什么不是 1/2 ​

直觉错在忽略"双正币必然出正面"这一信息。在所有可能产生正面的"路径"中，A 占 2 份（一定正面），C 占 1 份（一半正面），所以 A 的后验是 2/3。

延伸：男孩女孩版的对应 ​

这道题与"双孩问题"中"至少一个男孩"版本质相同：

  • 双正币 A ⇒ 两个都是男孩
  • 公平币 C ⇒ 一男一女

答案都是 1/3（在"双正 A 给定正面"框架下，2/3 是双正的条件后验；类比到双孩问题，"两个男孩"在"至少一个男孩"条件下的概率是 1/3）。

Bertrand 盒悖论 ​

这是Bertrand 盒悖论（Joseph Bertrand, 1889）的经典版本，是最早被正式分析的条件概率悖论之一。

题目 12：睡美人问题 ​

题面 ​

睡美人参与实验：周日她睡着后，实验者掷一枚公平硬币。

  • 正面：周一唤醒她，问问题，再让她睡着并抹除周一记忆。
  • 反面：周一唤醒她，问问题；让她睡着抹除记忆；周二再次唤醒她，问同样的问题。

每次唤醒时实验者问她："你觉得硬币是正面的概率是多少？"

拆解与思考 ​

两派对立：

  • Halfer 派（1/2）：硬币是公平的，睡美人没有获得新信息（她早就知道会被唤醒），所以概率仍是 1/2。

  • Thirder 派（1/3）：考虑"三次唤醒"等可能：

    • 正面-周一（H-Mon）
    • 反面-周一（T-Mon）
    • 反面-周二（T-Tue）

    每次唤醒都被均匀抽到。其中 H-Mon 占 1/3，故正面概率 1/3。

Thirder 的严格证明：

若硬币是不公平的（正面概率 p），睡美人的"自我定位采样"会有偏向。考虑实验重复很多次：

  • 期望唤醒次数：1·p + 2·(1-p) = 2 - p。
  • 其中"正面-周一"的唤醒次数：p。
  • 占比：p / (2-p)。

当 p = 1/2：1/2 / (3/2) = 1/3。

答案 ​

没有公认答案——这是哲学界至今仍有争论的问题。多数贝叶斯派学者支持 1/3，多数频率派支持 1/2。

哲学意义 ​

睡美人问题揭示了自我定位采样（anthropic / indexical sampling）的微妙性：当观察者本身的存在依赖于随机事件时，如何更新信念？

延伸到人择原理（anthropic principle）：为什么宇宙常数恰好适合生命？因为如果不是这样，就没有观察者来问这个问题。

题目 13：两次抛硬币的期望最大值 ​

题面 ​

抛两次公平硬币，正面记 1、反面记 0。你能选择"停止"或"继续"。求最优策略下的最大期望得分。

拆解与思考 ​

反向归纳（动态规划）：

第二次抛掷后（若已抛两次）：得分就是两次结果之和。

第一次抛掷后：

  • 若第一次正面（1 分）：选择"停"得 1 分，或"继续"——继续的期望是 1 + E[第二次] = 1 + 0.5 = 1.5。继续更优。
  • 若第一次反面（0 分）：选择"停"得 0 分，或"继续"——继续的期望是 0 + 0.5 = 0.5。继续更优。

初始：第一次必须抛。期望 0.5 + max(继续的期望 1.5 vs 停的 0.5)……不对，重新理解题意。

正确表述：抛 N 次，每次可停止。求期望最大分。

简单版（最多 2 次抛掷）：

记 V(i, s) 为已抛 i 次、当前累计 s 分时的最优期望最终得分。

  • V(2, s) = s（必须停）。
  • V(1, s) = max(s, E[V(2, s + X)]) 其中 X ~ Bernoulli(0.5)。
    • V(1, 0) = max(0, 0.5·V(2,0) + 0.5·V(2,1)) = max(0, 0.5) = 0.5。继续。
    • V(1, 1) = max(1, 0.5·V(2,1) + 0.5·V(2,2)) = max(1, 1.5) = 1.5。继续。
  • V(0, 0) = 0.5·V(1,0) + 0.5·V(1,1) = 0.5·0.5 + 0.5·1.5 = 1。

答案 ​

最多 2 次抛掷的最优期望得分是 1（永远继续）。

延伸：n 次抛掷 ​

最优策略为：若剩余次数还能弥补，则继续。一般期望得分约为 n/2 + √(n/(2π))。

这是最优停时理论的简单例子，与期权定价（Black-Scholes）中的"提前行权"边界同构。

题目 14：随机游走与赌徒相遇 ​

题面 ​

整数数轴上，A 从位置 0 出发，每步 +1；B 从位置 n 出发，每步 -1。两人同时开始，每步独立。问：他们相遇（在同时刻同位置）的概率？

拆解与思考 ​

两人速度相反，必定在某时刻相遇（除非步长不等）。在位置 n/2、时刻 n/2（如果 n 偶数）相遇。

但若改成：A、B 每步等概率 +1 或 -1（独立），求相遇概率？

变换：定义 C(t) = A(t) - B(t)，初始 C(0) = -n。每步 ΔC = ΔA - ΔB，可能取 -2, 0, +2 各概率 1/4, 1/2, 1/4。

问题化为：C 从 -n 出发，每步 ΔC ∈ {-2, 0, +2}（对应概率 1/4, 1/2, 1/4），求首次到达 0 的概率。

对称随机游走的命中概率：从位置 x 出发，对称随机游走到 0 的概率为 1（在一维随机游走中，任何点都会被几乎必然访问）。

答案 ​

若步长相同方向相反：必然相遇于 n/2。 若两人独立随机游走：几乎必然（概率 1）相遇。

延伸：二维与三维 ​

  • 二维随机游走仍然回归原点的概率为 1（Pólya 定理）。
  • 三维及以上：回归原点的概率 < 1（约 0.34）。

"喝醉的人总能找到回家的路，喝醉的鸟可能永远迷失。" — 角谷静夫

解题模板（总结） ​

通用流程 ​

  1. 先别信直觉——概率直觉是进化遗留的产物，在现代概率题中经常失灵。
  2. 枚举样本空间，标注每种结果的概率。
  3. 明确条件——"已知什么"会彻底改变概率分布。
  4. 用"补事件"简化（算"不发生"再用 1 减）。
  5. 递推法处理序列：设状态变量，建递推方程。
  6. 量纲检查：概率在 [0, 1]，期望值应该合理。

信号清单 ​

题面信号推理工具
"主持人/典狱长知情后开门/透露"贝叶斯，注意信息流
"至少 k 个"补事件，1 减去"少于 k"
"连续 k 次某事件"状态机期望，公式 2^{k+1} - 2（p=1/2）
"所有人等概率"生日悖论，关注配对数
"随机选 X" / "随机抽取"期望线性性
"选择停止时机"反向归纳 / 最优停时
"已知有男孩/阳性/正面"贝叶斯，警惕基础率谬误
"重复试验直到首次成功"几何分布，期望 1/p
"集齐所有种类"优惠券收集，期望 n H_n
"资金有限 vs 无限庄家"赌徒破产，资金管理

常见陷阱 ​

  • 基础率谬误：低基础率下，高灵敏度检测的阳性预测值也很低。
  • 条件概率≠联合概率：P(A|B) 和 P(A ∩ B) 是两回事。
  • 独立假设滥用：两个事件不独立时，乘法公式 P(AB) = P(A)P(B) 不成立。
  • 赌徒谬误：独立事件没有"补偿"，连续反面的硬币下一次仍 1/2。
  • 样本空间不全：枚举要包括所有可能（双孩问题的 BG vs GB 是两个不同结果）。
  • 忽略机制：观察结果的过程本身影响概率（主持人是否知情）。

延伸阅读 ​

书籍 ​

  • 《概率论与数理统计》— 陈希孺，中文概率论最好的入门书之一
  • 《Fifty Challenging Problems in Probability with Solutions》— Frederick Mosteller，必读
  • 《概率论基础教程》— Sheldon Ross，经典教材
  • 《概率论及其应用》— William Feller，第 1 卷经典
  • 《Stochastic Processes》— Sheldon Ross，进阶

文章与资源 ​

练习平台 ​

基于 VitePress 构建 · 部署于 Cloudflare Pages

Copyright © 2024-present DevDocs