← 牌桌
自习室 · 3/6停还是继续
操作台 · 重掷游戏求解器
1
简报 · 自习室

停还是继续

用于:面试中的期望值谜题、比大比小

当你在游戏中可以做选择时,从最后一个决策往前倒推。每一步,如果手上的比继续玩的期望值更好,就保留它。

V₀ = (s+1)/2 Vₖ = E[ max(X, Vₖ₋₁) ]

Vₖ 是用 s 面骰子、还剩 k 次重掷时这个游戏的价值。阈值规则是:保留严格大于 Vₖ₋₁ 的点数。

原理:理解 Vₖ = E[ max(X, Vₖ₋₁) ]
s骰子的面数。
Vₖ还剩 k 次重掷、并且你完美操作时,这个游戏值多少。
V₀ = (s+1)/2没有重掷机会时,你必须接受下一次的点数,所以游戏的价值就是掷一次的普通期望值。
X你即将看到的点数。
Vₖ₋₁如果扔掉这次的点数你能得到的价值:同一个游戏,少一次重掷。
max(X, Vₖ₋₁)看到 X 后的收益:保留 X,或者换成剩下的游戏。取两者中较大的。
E[ … ]对你可能看到的每个点数,把这个收益取平均。

例题:六面骰,一次重掷

V₀ = 3.5。掷出 1、2 或 3 时,重掷(价值 3.5)比保留好,所以 max = 3.5。掷出 4、5 或 6 就保留。所以 V₁ = (3.5 + 3.5 + 3.5 + 4 + 5 + 6) ÷ 6 = 25.5 ÷ 6 = 4.25。

有两次重掷时门槛升到 4.25,只保留 5 和 6:V₂ = (4 × 4.25 + 5 + 6) ÷ 6 = 28 ÷ 6 = 4.67。

为什么要倒推?不知道继续玩值多少,就无法评估第一个决策。只有最后一个决策的后续是已知的(普通期望值),所以从那里开始,一步步往回推。这种方法叫逆向归纳,美式期权在二叉树上正是这样定价的:在每个节点,取立即行权和继续持有中的较大者。

速记
  • 六面骰一次重掷 = 4.25。两次重掷 = 4.67。记住这两个数。
  • 点数 > 继续玩的价值就保留。永远不要和总体平均值比。
随时点玩法说明重新打开。