抛硬币问题

Contents
  1. 1. 原问题
  2. 2. 原问题解释
    1. 2.1. 判断奇偶的方法
    2. 2.2. 原问题期望求解
  3. 3. 出现 k 次正面才停止
  4. 4. 连续出现 k 次正面才停止
  5. 5. References

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

原问题

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

假设: 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

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

原问题期望求解

设所求期望为 EE , 显然 E1E \geqslant 1 ,设正面概率为 pp ,若第一次即抛得正面,则还需要抛 00 次,若第 11 次未抛得正面,则除了已经抛过一次以外,该问题回到了又原点,故有:

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

得:

E=1pE = \frac{1}{p}

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

出现 k 次正面才停止

考虑这样一个问题:连续抛一枚硬币,出现 kk 次正面方停止,求抛掷次数的数学期望?

XiX_i 表示出现第 ii 个正面所需实验次数,其符合几何分布,期望值为 22 。故有出现 kk 次的期望值为:

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

连续出现 k 次正面才停止

考虑这样一个问题:连续抛一枚硬币,连续地出现 kk 次正面方停止,求抛掷次数的数学期望?

TkT_k 表示连续出现 kk 次正面所需次数的数学期望,则类似 原问题 期望求解方法,可类似得到:

Tk=Tk1+1+p0+(1p)TkT_k = T_{k-1} + 1 + p \cdot 0 + (1 - p) \cdot T_k

T1=1pT_1 = \frac{1}{p} 则:

Tk=i=1k1piT_k = \sum_{i=1}^k \frac{1}{p^i}

由于 p=0.5p = 0.5,故:

Tk=2k+12T_k = 2^{k+1} - 2

References

抛硬币次数的期望

有道概率题:一个有趣的抛硬币问题

Matrix67

抛硬币直到出现连续 N 次正面为止的期望

几道抛硬币问题

抛的硬币直到连续出现两次正面为止,平均要扔多少次

抛硬币问题:抛硬币直到出现 5 次正面,抛硬币的次数的期望怎么求?