掷硬币问题

Categories: Uncategorized
Tags: No Tags
Comments: No Comments
Published on: 2011/07/11

这里讨论一个掷硬币问题:假如一个人要连续掷n (n>=1)次硬币,他可以掷大于或等于1的任意多次,并且可以随时决定是否停止。当他决定停止后,他会获得一定的收益,收益大小正比于掷硬币的结果中正面所占的比例。

例如:掷的第一次为反面,第二、三、四次都是正面。此时他认为得到的结果已经足够好了,决定停止。这次他的收益就为0.75。

另外还有个约束就是这个人的决策必须在期望有限的次数内停下。我们假设这个人足够聪明,采用最优策略使得收益的期望最大化。那么这个收益的期望是多少?最优策略是什么?

首先我们把这个问题符号化:
我们所做的决策,就是决定在什么时刻停止。假设某一状态下已经掷过m次硬币,其中有n次为正面(m >= n >= 0),条件期望收益函数f(m, n)表示在当前状态下得到收益的期望,那么该函数有如下递推表达:

f(m, n) = \max\{\frac{n}{m}, \frac{f(m+1,n+1) + f(m+1,n)}{2}\}

这个问题的难点在于f(m, n)的递推表达包含无穷多项。一种可行的数值解法是对问题中掷硬币的次数限制在N次以内。当N的值逐渐增大趋于无穷时,收益f(m,n;N)单调递增并趋于期望的收益。对于有限次数的问题可以通过动态规划算法求解,本文最后给出了我用C++写的数值计算程序。当N=1000000时,运算结果为0.792942。而且一个比较反直觉的例子是当连续掷三次出现两次正面的话仍然不应该停下来。

Ps: 这个问题是我在考虑一个信道估计的算法时抽象出来的一个问题的最简单情况。虽然转化成这个问题已经和原问题偏离很远了,但是感觉这个题目比较好玩,并且没有很显然的解,就在校内上提了出来。结果发现某姚班的同学在他的blog 阅微堂 中也提到过这个问题。
Ps2: 这里给出了数值计算并且进行了一定的优化。我的程序结果和他的数据略有出入,不清楚是因为有错误还是因为他的近似。100000的结果和阅微堂中的是吻合的。

#include <iostream>
#include <iomanip>
 
using namespace std;
 
const int buffersize = 1000002;
int maxnum;
long double buf1[buffersize + 1];
long double buf2[buffersize + 1];
long double *benefit = buf1;
long double *postbenefit = buf2;
long double *temp;
inline void swap() {
    temp = postbenefit;
    postbenefit = benefit;
    benefit = temp;
}
 
int main() {
    long double b1, b2, dm;
    cin >> maxnum;
    dm = (long double)(maxnum);
    for (int i = 0; i <= maxnum; i++) {
        // benefit[i] = f(maxnum, i)
        postbenefit[i] = (i * 2 < maxnum) ? 0.5 : ((long double)(i) / dm);
    }
 
    long long count = 0;
    long long all = (long long)(maxnum) * (maxnum + 1) / 2;
    long long percent = 1;
    long long nextstep = all / 100 * percent;
    for (int m = maxnum - 1; m >= 0; m--) {
        dm = (long double)(m);
        for (int i = 0; i <= m; i++) {
            ++count;
            if (count > nextstep) {
                nextstep = all * percent / 100;
                cerr << percent << "%" << endl;
                ++percent;
            }
            // postbenefit[i] = f(m+1, i)
            b1 = (long double)(i) / dm;
            // (f(m+1, i+1) + f(m+1, i)) / 2
            b2 = (postbenefit[i + 1] + postbenefit[i]) / 2;
            benefit[i] = (b1 > b2 ? b1 : b2);
        }
        swap();
    }
 
    cout << setprecision(10) << postbenefit[0] << endl;
 
    return 0;
}
No Comments - Leave a comment

Leave a comment

Your email address will not be published. Required fields are marked *


Close Print