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