CF1392H ZS Shuffles Cards

· · 题解

这是一道关于期望的好题，经过仔细的思考后相信你能更加深刻而准确的领悟期望的本质。

下面给出一个较为简洁的做法及其证明。

我们称抽到一张 joker 并重排牌序之前的抽卡流程为一轮。

E(\text{游戏结束时期望抽牌数}) =\sum_{i=0}^{\inf}E(\text{游戏在第 i-1轮没有结束})\times E(\text{第 i 轮抽的牌数}) =\sum_{i=0}^{\inf}E(\text{游戏在第 i-1轮没有结束})\times E(\text{一轮抽的牌数}) =E(\text{轮数})\times E(\text{一轮抽的牌数})

注意这里轮数和每轮抽的牌数并不独立，但由于E(\text{第i轮抽牌数}) 都是一样的，所以我们可以将它们拆开。

先算 E(\text{一轮抽的牌数}) 。我们可以把抽到 joker 后结束一轮当成每轮都抽满了 n+m 张牌，只不过第一张 joker 之后的牌不算数。

我们考虑每张数字牌，他之前没有 joker 的概率显然是 \frac{1}{m+1}，所以 E(\text{一轮抽的牌数}) 就是 \frac{n}{m+1}+1。（加上一张joker）

再算 E(\text{轮数})。我们称一张数字牌为新的当且仅当之前没有抽到过这张牌。

E(\text{轮数}) =\sum_{i=1}^{n}E(\text{还剩i张牌没抽到过时抽到一张新牌所需轮数})+E(\text{所有数字牌都抽到过后游戏结束所需期望轮数})

在抽新牌时，已经抽到过的牌可以忽略不计（抽到了既不会是新牌，也不会让轮数+1）。

所以

E(\text{还剩i张牌没抽到过时抽到一张新牌所需轮数}) =E(\text{还剩i张牌没抽到过时抽到一张新牌所需抽 joker 或新牌张数})-1

-1 是因为最后一张新牌不会加轮数。每次抽到新牌的概率是 \frac{i}{m+i}，E(\text{还剩i张牌没抽到过时抽到一张新牌所需抽 joker 或新牌张数}) 就是 \frac{m+i}{i}。

所以 E(\text{还剩i张牌没抽到过时抽到一张新牌所需轮数})=\frac{m}{i}。E(\text{轮数})=mH_n+1。

最后，

E(\text{游戏结束时期望抽牌数}) =E(\text{轮数})\times E(\text{一轮抽的牌数}) =(mH_n+1)(\frac{n}{m+1}+1)