火锅捞蛋

今天逛 v2ex 看到一个挺有意思的问题：

假如我去吃火锅，已知锅里有 N 个鹌鹑蛋，我想要把这些蛋捞来吃。每个蛋被捞到的概率均为 P ，并且一次捞出的个数没有限制。但是，如果我连续 T 次都一个没捞到，那我就会放弃。

问题：当我放弃后，锅里剩下的鹌鹑蛋的个数的期望 E 是多少？（可以假设 N=10, P=0.2, T=5 ）

这道题如果是做算法题的话，很容易想到用 DP 解，定义状态 $(n,k)$ 表示在锅中还剩 $n$ 个蛋并且已经白给了 $k$ 次后，锅中剩下的蛋的个数。

显然，从状态 $(n,k)$ 可以转换到 $(n, k+1)$（又白给）、$(n-l, 0)$（捞起来 $l$ 个，其中 $l \in \left[1, n\right]$）。

设 $f(n,k)$ 为状态 $(n,k)$ 剩下的蛋的期望，有转移方程： $$\tag{1.1} f\left( n,k \right) =\left( 1-p \right) ^n f\left( n,k+1 \right) + \sum_{l=1}^n{ C_{n}^{l} p^l\left( 1-p \right) ^{n-l}f\left( n-l,0 \right)}$$

注意到方程 $(1.1)$ 中，右侧的求和与 $k$ 无关。将此记为 $g(n)$，有 $$\tag{1.2} f\left( n,k \right) =\left( 1-p \right) ^n f\left( n,k+1 \right) +g\left( n \right)$$ 令 $h(n)=\frac{1}{(1-p)^n -1}g(n)$，则有 $$\tag{1.3} f(n,k)+h(n)=(1-p)^n\left[f(n,k+1)+h(n)\right]$$ 结合边界条件 $$\tag{1.4} f(n,T)=n$$ 我们可以得到 $$\begin{aligned} f(n,0)+h(n) &= \left((1-p)^n\right)^T\left(f(n,T)+h(n)\right) \\ &= (1-p)^{nT}\left(n+h(n)\right) \end{aligned} \tag{1.5}$$ 因此， $$\begin{aligned} f(n,0) &= n\left(1-p\right)^{nT}+\left((1-p)^{nT}-1\right)h(n) \\ &= n\left(1-p\right)^{nT} + \frac{(1-p)^{nT}-1}{(1-p)^n-1}g(n) \end{aligned} \tag{1.6}$$ 将 $f(n,0)$ 记为 $f(n)$ 并展开 $g(n)$，我们得到 $$\tag{1.7} f(n)=n(1-p)^{nT}+\frac{(1-p)^{nT}-1}{(1-p)^n-1}\sum_{l=1}^n{C_{n}^{l}p^l\left( 1-p \right) ^{n-l}f\left( n-l\right)}$$ 式 $(1.7)$ 是我目前能得到的比较好的结果，尝试消去 $f(n-l)$ 无果。

式 $(1.7)$ 具体可以通过递推求解。计算其前几项可得： $$\begin{aligned} f(0) &= 0 \\ f(1) &= (1-p)^T \\ f(2) &= 2 (1-p)^{2 T}+\frac{2 \left((1-p)^{2T}-1\right) (1-p)^{T+1}}{p-2} \\ f(3) &= 3 (1-p)^{3 T}+\frac{3 p \left((1-p)^{3 T}-1\right) \left(2 (1-p)^{T+1}+\frac{2 (p-1)^2 \left((1-p)^{2 T}-1\right)}{p-2}+p\right) (1-p)^{T+1}}{(1-p)^3-1} \end{aligned} \tag{1.8}$$ 如果代入数据（$p=0.2,T=5$），可以得到结果 $$\begin{aligned} f(0) &= 0 \\ f(1) &= \frac{1024}{3125}=0.32768 \\ f(2) &= \frac{14488051712}{30517 578125}=0.474744 \\ f(3) &= \frac{491898817322794070016}{93132257461 5478515625}=0.528172 \end{aligned} \tag{1.9}$$ 分别代表锅中还有 $n$ 个蛋时，剩下蛋数量的期望。