何时适可而止 ?

作者: , 共 1016 字 , 共阅读 0
系列:头脑风暴

查看该系列所有文章

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

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

在第一次抛硬币时,如果出现正面时立即停止,此时获得一个最大的回报 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.

系列: 头脑风暴 »
数学 » 头脑风暴
发信人: GGGGDDDDK (忠贾诩发动乱武,反华佗没法急救别人了), 信区: SanGuoSha
标   题: 据说此题是入职腾讯游戏策划部门一道题 zz
发信站: 水木社区 (Mon Sep 20 11:10:40 2010), 站内
在 MIT BBS 上看到一个有趣的题目
类似文章:
数学 » 赌博
何时适合而止中,我们提到一个有趣的硬币问题,抛一个硬币,选择合适的时点,使得正面数与总次数的比值最大。这个问题目前还没有被完全解决,之前我们也只是用模拟法逼近了一下结果
相似度: 0.121
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
相似度: 0.093
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个$ 2\times2$ 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
最佳约会策略里,我们提到,如果有 100 个女孩可以顺序挑选,那么最好的方法是先看前 37 个,然后在剩下的女孩里选择当时最好的那个女孩,这样有接近 40%的概率挑选到最好的那个女孩。同时,不可能有更好的策略
在 MIT BBS 上看到一个有趣的题目
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。
本文将证明:最佳约会策略里提到策略,忽略前 37%的对象,然后在剩下的对象里挑第一个比前 37%都好的对象,这个策略是最优的。更准确地,我们将证明:任何约会策略的成功概率都不可能超过$ \frac{u}{n}\sum_{i=u}^{n-1}\frac1i$ ,其中$ u$ 为满足$ \sum_{i=u}^{n-1}\frac1i\geq 1$ 的最大值。这个$ u$ 大约为 37%,最后成功的概率大约为 40%。
一个游戏:持续的抛一个均匀硬币,直到抛到出现反面为止,假设在之前你抛除了$ k$ 次正面,你将得到$ 2^{k+1}$ 次方这么多钱。
相似度: 0.080
$ n$ 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
相似度: 0.079
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。
过于集中持股风险较大是投资界的常识,俗话说不要把鸡蛋放在一个篮子里。在实际投资中中国的公募基金就有严格的 10%的个股持仓上限。