无偏地掷 n 个硬币，每个硬币的成功值不同

Question

假设我们有 n 个硬币，硬币 i 正面朝下的概率是 f(i) 。求将 n 枚硬币全部抛完，出现偶数次正面朝上的概率。

f(i) = 1 / (2i + 3)

这里的n很大，数量级为1e5，所以需要高效的方法。

我试图分析蛮力案例，但这太过分了，即如果我计算 2 次成功、4 次、6 次...，可能需要数年才能运行。

然后我想以某种方式应用期望线性度，但无法想出任何有用的方法。

Answer 1

这应该是简单的递归，不是吗？

设 p(k) = 1/(2*k+3), q(k) = 1 - p(k), V(k) 是在 k 之后进行偶数抛掷的概率。

让我们考虑最后一次投掷

V(n) = q(n)*V(n-1) + p(n)*(1-V(n-1)) = (q(n)-p(n))*V(n-1) + p(n)
V(0) = 1

C++代码

#include <iostream>

inline double p(int k) {
    return 1.0/(2.0*k + 3.0);
}

inline double q(int k) {
    return 1.0 - p(k);
}

double V(int k) {
    if (k == 0)
        return 1.0;

    return (q(k) - p(k))*V(k-1) + p(k);
}

int main() {
    std::cout << V(10000) << std::endl;

    return 0;
}

V(10000) 确实非常接近 .5

V(10000) = 0.500075

无偏地掷 n 个硬币，每个硬币的成功值不同

Unbiased coin toss of n coins with different success values for each coin

probability