随机位或

设有一列按均匀分布随机生成的32位二进制数$y_0, y_1, y_2\ldots$，序列$x_i$按如下方式递归定义：

$x_0=0$，以及$x_i=x_{i-1} | y_{i-1}$，其中$|$表示按位作或运算。

可以验证，总是存在下标N，使得对于所有$i\ge N$都有$x_i=2^{32}-1$。

求N的期望值，结果保留十位小数。

本题难度:

解答

显然本题是coupon collector问题的一种变体，即考虑有32种卡片，每次可以得到其中若干种，平均需要多少次能集齐。

记$f(n)$为还有$n$种卡片未集齐时的期望次数，则有 $$f(n)=1+\frac{1}{2^n}\sum_{k=0}^n\binom{n}{k}f(k),$$ 其中右侧表示本次分别获得了这n种卡片中的$0,1,\ldots,n$张时的期望次数。移项后得 $$f(n)=\frac{2^n+\sum_{k=0}^{n-1}\binom{n}{k}f(k)}{2^n-1},$$ 结合初值$f(0)=0$，递推计算即得结果$6.3551758451$。

注：为便于作除法以及使用math.comb函数，以下为Python 3代码

import math
f=[0]

for n in range(1,33):
    f.append(((1 << n)+sum(math.comb(n,k)*f[k] for k in range(n)))/((1 << n)-1))

print(f"{f[-1]:.10f}")