图 1:本文封面,收手与继续的决策分叉。
「扔骰子返现,不满意可以再扔一次」这类题的完整计算,这个系列昨天的真题解析已经做过——结论是 4.25 元,分界点 3.5。那道题背后的通用框架比答案本身值钱:凡是「看完结果可以选择再来一次」的题目,都是同一套期望决策框架的实例。这篇把框架抽出来讲透,以后遇到任何变体都能套。文中所有概率推演均为自证推导,并用蒙特卡洛模拟验证。
通用框架只有三步:建模、求解、比较。
第一步建模:把局面抽象成手里的确定值 V 和两个选择——收手拿 V,继续拿期望 E。第二步求解:算出 E。这里有个容易漏的关键:E 的定义里必须包含「之后也都按最优策略行动」,否则你算的是「盲目继续」的价值,不是「最优继续」的价值。第三步比较:E 大于 V 就继续,否则收手。框架的全部威力来自这个观察——当继续的期望与当前手牌无关时(比如重扔骰子的期望不取决于你刚才扔了几点),E 就是一个常数,决策规则必然塌缩成一条阈值:手里的值超过 E 就停,低于 E 就继续。这就是为什么这类题的最优策略总是「一个分界线」的形式。骰子题里 E 等于重扔的期望 3.5,所以分界点落在 3.5:超过就收下,不够就再来。
多步决策:从终点倒着算。
上面是只剩一次机会的情形。如果可以选择两次、三次甚至任意次,E 就不再是常数——每一次「继续」的价值里,还嵌着后面每一步的最优选择。处理办法是逆向递推:定义 V(t) 为第 t 步的最优价值,则 V(t) 等于「停在 t 的收益」与「V(t+1) 的期望」取大者。递推没有起点怎么办?从终点开始:最后一次机会没有「之后」,它的价值就是裸期望;算出来往回带一层,倒数第二步的 E 就有了;逐级回传直到第一步。每一步的分界阈值会随剩余机会数变化——机会越多,继续的期权价值越高,阈值也越高,直觉上就是「手里牌还多,可以更挑剔」。面试里遇到「可以重抽 k 次」的变体,答出「从最后一次机会倒推、每级阈值递增」就站住了。
经典特例:最优停止与 37% 法则。
框架有一个著名的特例:n 个候选按随机顺序依次出现,每个看完必须当场决定收或不收,不可回头,目标是选中全场最佳——这就是最优停止问题(秘书问题)。它没有「确定值 V 对期望 E」的形态,因为收益不是点数而是「是否选中最佳」,但分析骨架相同:把过程分成观察期与行动期。最优策略是放掉前 r 减 1 个候选、只记录其中最优者作为基准,之后遇到第一个超越基准的就立即收下。数学上可以证明,n 充分大时最优观察比例 r/n 收敛到 1/e,约 37%,而此时选中最佳者的概率也约 37%。用蒙特卡洛验证(Node.js 22.15.0,node secretary.js):n 取 100、每个观察比例跑 20 万次:
function success(n, r, trials) {
let win = 0;
for (let t = 0; t < trials; t++) {
const arr = Array.from({ length: n }, () => Math.random());
const best = Math.max(...arr); // 全场最佳的分值
const record = Math.max(...arr.slice(0, r - 1)); // 观察期的最优记录
let pick = -1;
for (let i = r - 1; i < n; i++) {
if (arr[i] > record) { pick = arr[i]; break; } // 首个超越记录者
}
if (pick === best) win++;
}
return win / trials;
}
实测输出:
观察前 9 个(r/n=0.10): 选中最佳概率 22.2%
观察前 19 个(r/n=0.20): 选中最佳概率 31.9%
观察前 29 个(r/n=0.30): 选中最佳概率 36.4%
观察前 36 个(r/n=0.37): 选中最佳概率 36.9%
观察前 39 个(r/n=0.40): 选中最佳概率 37.1%
观察前 49 个(r/n=0.50): 选中最佳概率 35.3%
观察前 79 个(r/n=0.80): 选中最佳概率 18.6%
曲线在 r/n 约 0.37 处见顶、成功率约 37%,与理论值 1/e 吻合。观察太短基准不稳、太长容易把最佳者放过去,37% 是两者的平衡点。
图 2:三步框架、逆向递推与 37% 法则。
面试怎么用这套框架。
遇到「要不要再看看」类题目,先把直觉翻译成算术:声明手里的确定值 V,明确继续的期望 E 怎么算、是否依赖当前状态。E 与状态无关,直接得出阈值策略;E 依赖剩余机会,声明用逆向递推从终点倒推,并指出阈值随剩余机会递增。如果题目是「只能选一次、不可回头」的形态,识别出最优停止模型,给出观察期加行动期的结构与 37% 法则。最后加一句边界:框架假设期望可算,现实中概率分布估不准时,要把规则回调到更保守的阈值——这句话展示的是工程判断力。你被问过哪道「再看看」的变体题?当时是硬算期望还是套了阈值策略?欢迎分享。