何时适可而止?

作者:, 发表于

最近看到一个有趣的问题:

我们可以连续抛一枚均匀的硬币,并且随时可停下,在停下后可获得的回报为(正面出现次数/抛硬币的次数)。如果希望获得的回报越大越好,我们应该采取什么样的停止策略?

在第一次抛硬币时,如果出现正面时立即停止,此时获得一个最大的回报1,如果出现反面,则应该选择继续抛。假设前 \(n\) 次抛硬币出现了 \(k\) 次正面时最后能获取的期望回报值为 \(f(n, k)\) ,利用动态规划的思想容易列出方程

\[f(n, k) = \max ( \frac{k}{n}, \frac{f(n+1, k)+f(n+1, k+1)}{2})\]

但要解上面的方程可不是那么容易。事实上,它们的精确值还没有人知道。注意到由于一维随机游走的常返性,对任意的 \(n\)\(k\) 都有 \(f(n,k)\geq 0.5\) 。利用这个边界条件可以求出一些近似解,我用下面的Matlab跑了一下:

N = 100000;
f = max(0, 0:1/N:1);
for n = N-1:-1:0
    f(1:n+1) = max((0:n)/n, (f(1:(n+1))+f(2:(n+2)))/2);
end

f = f(1);

将边界设为第100000枚硬币,算出来从最开始抛时的期望回报大约为0.79289。由于我的破计算机速度以及Matlab的效率问题,我这里很难再提高它的精确性,但这里有人将边界提高到了67108864,计算出来的结果为0.79295350640770。

如果只想知道该在什么时候停止呢?精确的规则也没人知道,Larry A. Shepp在论文Explicit solutions to some problems of optimal stopping中证明了抛的硬币次数 \(n\) 足够多时,应该等到正面数为 \((0.83992\sqrt{n}+n)/2\) 时停止。

这个问题,和以前的最佳约会策略一样,都是说如何基于当前的已知信息做决策,是在现实生活中不断遇到的,比如在赌场赌博,到底赌到什么时候该收手,上面答案可做一点参考。

Q.E.D.


上一篇:一个腾讯游戏策划部门的面试题2010年9月20日
发信人: GGGGDDDDK (忠贾诩发动乱武,反华佗没法急救别人了), 信区: SanGuoSha 标  题: 据说此题是入职腾讯游戏策划部门一道题zz 发信站: 水木社区 (Mon Sep

下一篇:取格子游戏的构造性策略2011年2月27日
在MIT BBS上看到一个有趣的题目 一个M*N的方阵,每个格子里放一个硬币。甲乙轮流取:选定一枚硬币后,必须取走它上方、右方和右上方的所有硬币(


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。