最近看到一个有趣的问题：
我们可以连续抛一枚均匀的硬币，并且随时可停下，在停下后可获得的回报为（正面出现次数/抛硬币的次数）。如果希望获得的回报越大越好，我们应该采取什么样的停止策略？
在第一次抛硬币时，如果出现正面时立即停止，此时获得一个最大的回报 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.
