抛硬币问题

Contents

记录一个由整数奇偶问题引发的思考。

原问题

算法有穷性讨论 - 理想硬币 - 几何分布

假设： rand() 为理想的随机整数发生器 // 尽管这似乎不可能

于是： rand() 为奇、偶的概率均为 50%

1
2
3

void dice(){
    while (rand() & 1); // 这个循环将迭代多少次？
}

数学期望 = 2 次

理论上，却可能任意多次

偶数的二进制的末尾为 0 ，奇数的二进制的末尾为 1 。

按位与：将参与运算的两操作数各对应的二进制位进行与操作，只有对应的两个二进位均为 1 时，结果的对应二进制位才为 1 ，否则为 0 。在做位运算时，位数不够的数，自动在前面补 0 。比如 21 & 1 ：10101 & 00001 = 00001 = 1 。

故 偶数 & 1 = 0 ， 奇数 & 1 = 1 。

因此，这个问题可以等效为抛硬币，抛到正面就停止的问题。

设所求期望为 $E$ ，显然 $E \geqslant 1$ ，设正面概率为 $p$ ，若第一次即抛得正面，则还需要抛 $0$ 次，若第 $1$ 次未抛得正面，则除了已经抛过一次以外，该问题回到了又原点，故有：

E = 1 + p \cdot 0 + (1 - p) \cdot E

得：

E = \frac{1}{p}

由于 $p = 0.5$ ，故数学期望为 $2$ 。事实上此即为几何分布的数学期望公式。

考虑这样一个问题：连续抛一枚硬币，出现 $k$ 次正面方停止，求抛掷次数的数学期望？

设 $X_i$ 表示出现第 $i$ 个正面所需实验次数，其符合几何分布，期望值为 $2$ 。故有出现 $k$ 次的期望值为：

E \left \lbrack \sum_{i=1}^k \right \rbrack = \sum_{i=1}^k E[X_i] = 2k

考虑这样一个问题：连续抛一枚硬币，连续地出现 $k$ 次正面方停止，求抛掷次数的数学期望？

设 $T_k$ 表示连续出现 $k$ 次正面所需次数的数学期望，则类似 原问题 期望求解方法，可类似得到：

T_k = T_{k-1} + 1 + p \cdot 0 + (1 - p) \cdot T_k

又 $T_1 = \frac{1}{p}$ 则：

T_k = \sum_{i=1}^k \frac{1}{p^i}

由于 $p = 0.5$ ，故：

T_k = 2^{k+1} - 2