后宫佳丽三千，多久才能宠幸完

后宫佳丽三千，多久才能宠幸完？

皇上后宫佳丽三千，皇上从第一天开始每天随机挑选一个宠幸，恰好宠幸完所有佳丽的天数的期望是多少？

□韩迪 

答案是25751天 ，差不多是 70 年。

有人指出这个问题叫做 Coupon collector's problem(优惠券收集问题)。

如我想集齐小浣熊的 108 将人物卡，假设每张卡出现的概率是相同的（ ），则平均需要买多少袋干脆面。这实质上和本问题是一样的。

那么下次皇帝随机宠信佳丽时，遇到宠幸过的概率是 ，遇到没宠幸过的概率是

现在皇帝已经宠幸过了 位佳丽后，他再宠幸 1 位之前没宠信的佳丽，使得宠信过的佳丽数达到 需要的天数为 ，其满足几何分布，因此 的期望为：

而宠幸所有佳丽所需的总天数为：

而且不同的 之间相互独立，因此所需时间的期望为：

因为专业背景用排队论比较多，所以我最初把问题考虑成了一个马尔可夫链，虽然也能求出结果，但复杂了很多，也不是那么好理解，如果大家感兴趣也可以看一下。

我最初的解题过程如下：

第 天结束后，宠幸过妃子的数为 。

易发现随机序列 是一个马尔科夫链，状态转移图如下：

接下来让我们分析状态转移概率：

· 当 时，说明任何佳丽都没有宠幸，则第二天宠幸过的妃子数量一定会加 1，即 ;

· 晚上皇帝宠未幸到新妃子的概率为 ；

令 表示状态 一步转换到 的概率，有：

· 当 和 时， ，代表皇帝宠幸过的佳丽数量是不会减少的，以及每晚增加的数量最多为 1；

· 当 时， ；

接下来便是神奇之处:，其物理意义有点绕，我尽量解释一下：

· 皇帝每晚的宠幸都会使得时间花费+1；

· 上述二者应该等价，因此有该关系式；

又，上式等同于(第 6 行左侧为 0，所以舍去)：

其中 为单位矩阵。该公式展开可得：

会发现这个线性方程非常有规律，口算即可解出。递推公式为：

解得 ，即平均需要 11.4167 天。

得到平均时间为 25751 天（计算时间不到 6 毫秒）。

而且上述公式再加上一点简单的变化，还可以进一步化简为：

数学最美的地方便在于殊途同归~

我计算了几组后宫佳丽数量下的期望天数：

（重申一下，这道题用马尔科夫链是大炮打蚊子了，太过麻烦。但如果问题复杂一些，例如每隔一段时间都会有新人入宫，老人离宫，那么马尔科夫链可能会有用武之地）

2017-05-04