求完成卡牌跳跃游戏所需的期望回合数

嘿，这个问题的解法其实比你想的更优雅，我来帮你把思路理顺～

首先先明确问题：

把n张卡牌排成一行，最左边是卡牌1，最右边是卡牌n。游戏规则是从卡牌1开始，每次随机选择右边的任意一张卡牌跳过去，重复这个动作直到到达卡牌n。求完成游戏所需回合数的期望值。

你的思路分析 #

你提到的两种思路都很有道理：

1. 枚举序列的方法：确实每个游戏过程对应一个递增序列，但不同序列的概率差异很大，直接求和计算期望会非常繁琐，不是最优解。
2. 指示变量分解：这个方向完全正确！你把总回合数拆分成多个伯努利变量的和，利用线性期望的性质来简化计算，这是解决这类期望问题的常用技巧，只是还差最后一步计算每个变量的期望（即停在卡牌i的概率）。

优雅的递推解法 #

我们可以用递推的方式直接求解期望，设E_i表示从卡牌i出发，到达卡牌n所需的期望回合数。显然：

• E_n = 0（已经到达终点，不需要任何回合）
• 对于i < n，从卡牌i出发，有n-i种可能的跳跃目标（卡牌i+1到n），每种目标的概率是1/(n-i)。每跳一次算1回合，之后还要加上从目标卡牌出发的期望回合数，因此递推式为：

  E_i = 1 + (1/(n-i)) * sum_{k=i+1}^n E_k
  

我们可以从后往前计算这个递推式，很快就能发现规律：

• E_{n-1} = 1（只能直接跳到n，1回合）
• E_{n-2} = 1 + (1/2)(E_{n-1} + E_n) = 1 + 1/2
• E_{n-3} = 1 + (1/3)(E_{n-2} + E_{n-1} + E_n) = 1 + 1/2 + 1/3
• ...
• 最终E_1 = 1 + 1/2 + 1/3 + ... + 1/(n-1)

这个结果就是第n-1个调和数，记为H_{n-1}。

联系你的指示变量思路 #

你定义的X_i是“停在卡牌i时为1，否则为0”，总回合数m等于所有X_i的和（因为每停在一个卡牌就需要进行一次跳跃，直到到达n）。根据线性期望：

E(m) = sum_{i=1}^{n-1} P(停在卡牌i)

现在计算每个P(停在卡牌i)：

• P(停在卡牌1) = 1（游戏从卡牌1开始，必然停在这里）
• 对于2 ≤ i ≤ n-1，P(停在卡牌i)等于从1出发，第一次进入卡牌i到n的集合时，恰好选中卡牌i的概率。由于每次跳跃是等可能选择右边的卡牌，这个概率是1/(n - i + 1)。

把这些概率加起来：

E(m) = 1 + 1/2 + 1/3 + ... + 1/(n-1)

和递推得到的结果完全一致！

举个例子验证 #

比如n=4时，期望是1+1/2+1/3=11/6≈1.833，和实际计算所有路径的期望结果一致：

• 路径1→4：概率1/3，回合数1，贡献1*(1/3)
• 路径1→2→4：概率(1/3)(1/2)=1/6，回合数2，贡献2(1/6)
• 路径1→2→3→4：概率(1/3)*(1/2)1=1/6，回合数3，贡献3(1/6)
• 路径1→3→4：概率1/31=1/3，回合数2，贡献2(1/3)
  总和为1/3 + 2*(1/6+1/3) +3*(1/6)=11/6，正确。

备注：内容来源于stack exchange，提问作者initech1999