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

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

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

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

数学期望 = 2 次

理论上，却可能任意多次

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

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

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

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

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

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

得：

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

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

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

设 XiX_iXi​ 表示出现第 iii 个正面所需实验次数，其符合几何分布，期望值为 222 。故有出现 kkk 次的期望值为：

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

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

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

Tk=Tk−1+1+p⋅0+(1−p)⋅TkT_k = T_{k-1} + 1 + p \cdot 0 + (1 - p) \cdot T_kTk​=Tk−1​+1+p⋅0+(1−p)⋅Tk​

又 T1=1pT_1 = \frac{1}{p}T1​=p1​ 则：

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

由于 p=0.5p = 0.5p=0.5，故：

Tk=2k+1−2T_k = 2^{k+1} - 2Tk​=2k+1−2

抛硬币次数的期望

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

Matrix67

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

几道抛硬币问题

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

抛硬币问题：抛硬币直到出现 5 次正面，抛硬币的次数的期望怎么求？