1
何时适可而止 ?
source link: https://zhiqiang.org/math/when-to-stop.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
何时适可而止 ?
系列：头脑风暴
最近看到一个有趣的问题：
我们可以连续抛一枚均匀的硬币，并且随时可停下，在停下后可获得的回报为（正面出现次数/抛硬币的次数）。如果希望获得的回报越大越好，我们应该采取什么样的停止策略？
在第一次抛硬币时，如果出现正面时立即停止，此时获得一个最大的回报 1 ，如果出现反面，则应该选择继续抛。假设前n 次抛硬币出现了k 次正面时最后能获取的期望回报值为f(n,k) ，利用动态规划的思想容易列出方程
f(n,k)=max(kn,f(n+1,k)+f(n+1,k+1)2)
但要解上面的方程可不是那么容易。事实上，它们的精确值还没有人知道。注意到由于一维随机游走的常返性，对任意的n 和k 都有f(n,k)≥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√n+n)/2 时停止。
这个问题，和以前的最佳约会策略一样，都是说如何基于当前的已知信息做决策，是在现实生活中不断遇到的，比如在赌场赌博，到底赌到什么时候该收手，上面答案可做一点参考。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK