皇上后宫佳丽三千，皇上从第一天开始每天随机挑选一个宠幸，恰好宠幸完所有佳丽的天数的期望是多少？
韩迪，公众号：科研学徒
答案是25751 天 ，差不多是 70 年。
刚开始写答案时不够认真，没仔细检查，虽然结果是对的，但中间步骤有很多纰漏和笔误，给不少人造成了困扰，十分抱歉。幸而不断有知友帮忙指出错误，大家的帮助下，我应该是把错误都改正了。
感谢评论区，有人指出这个问题叫做 Coupon collector"s problem(优惠券收集问题)。
例如我想集齐小浣熊的 108 将人物卡，假设每张卡出现的概率是相同的（
），则平均需要买多少袋干脆面。这实质上和本问题是一样的。
在这个问题中，我们假设皇帝现在已经宠幸了
位佳丽，也就是还没宠幸的佳丽是
位。
那么下次皇帝随机宠信佳丽时，遇到宠幸过的概率是
，遇到没宠幸过的概率是
现在皇帝已经宠幸过了
位佳丽后，他再宠幸 1 位之前没宠信的佳丽，使得宠信过的佳丽数达到
需要的天数为
，其满足几何分布，因此
的期望为：
而宠幸所有佳丽所需的总天数为
而且不同的
之间相互独立，因此所需时间的期望为
因为专业背景用排队论比较多，所以我最初把问题考虑成了一个马尔可夫链，虽然也能求出结果，但复杂了很多，也不是那么好理解，如果大家感兴趣也可以看一下。
我最初的解题过程如下：
第
天结束后，宠幸过妃子的数为
。
易发现随机序列
是一个马尔科夫链，状态转移图如下:
接下来让我们分析状态转移概率：
当
时，说明任何佳丽都没有宠幸，则第二天宠幸过的妃子数量一定会加 1，即
;
当
时，代表
个佳丽已经被宠幸，
个佳丽未被宠幸，则晚上皇帝宠幸到新妃子的概率为
，即
晚上皇帝宠未幸到新妃子的概率为
；
令
表示状态
一步转换到
的概率，有：
当
和
时，
，代表皇帝宠幸过的佳丽数量是不会减少的，以及每晚增加的数量最多为 1；
当
时，
当
时，
；
以
情形举例，则状态转移方程为：
然后设列向量矩阵
，其中
代表皇帝宠信
个佳丽所需时间的期望，显然
。
接下来便是神奇之处：
，其物理意义有点绕，我尽量解释一下：
皇帝每晚的宠幸都会使得时间花费 +1；
而
代表过去 1 晚后，各个期望的变化；
上述二者应该等价，因此有该关系式；
又，上式等同于(第 6 行左侧为 0，所以舍去)：
其中
为单位矩阵。该公式展开可得
会发现这个线性方程非常有规律，口算即可解出。递推公式为：
解得
，即平均需要 11.4167 天。
以此类推，得到
情况下的矩阵
。计算机计算结果如下：
得到平均时间为 25751 天（计算时间不到 6 毫秒）。
而且上述公式再加上一点简单的变化，还可以进一步化简为：
数学最美的地方便在于殊途同归~
我计算了几组后宫佳丽数量下的期望天数：
（重申一下，这道题用马尔科夫链是大炮打蚊子了，太过麻烦。但如果问题复杂一些，例如每隔一段时间都会有新人入宫，老人离宫，那么马尔科夫链可能会有用武之地）
查看知乎原文（73 条讨论）
如果觉得《大误 · 后宫佳丽三千人》对你有帮助，请点赞、收藏，并留下你的观点哦！
