调和级数概率专题
收集一些答案与调和级数的部分和有关的概率问题。
目视柜台的人数问题
柜台前，有\(n\)人排成一队等候，他们的身高独立地服从某均匀概率分布。第\(i\)人能够目视最前方的柜台，当且仅当他的身高是前\(i\)人中最高的。求能够目视最前方的柜台的人数\(X\)的数学期望\(E(X)\)。
设\(Y_i\)表示第\(i\)人能够目视最前方的柜台，则\(E(X) = \sum_{i=1}^n E(Y_i)\)。考虑前\(i\)人中，第\(i\)人成为最高者的概率
\[ P(Y_i = 1) = \frac{1}{i}, \]
故\(E(X) = \sum_{i=1}^n \frac{1}{i} = H_n\)。
奖券搜集问题
设奖池里有\(n\)种奖品，每种奖品抽中概率均等为\(\frac{1}{n}\)，求直到集齐所有种类的奖品，所需抽奖的次数\(X\)的数学期望\(E(X)\)。
\[ \begin{aligned} E(X) &= 1 + \frac{n}{n-1} + \frac{n}{n-2} + \dots + \frac{n}{2} + n \\ &= n \left(1+\frac{1}{2}+ \dots + \frac{1}{n-1} + \frac{1}{n} \right) \\ &= n \cdot \sum_{i=1}^{n} \frac{1}{i}. \\ &= nH_n. \end{aligned} \]
不愿起身的占座问题
某剧场的席位是单向进入的，如下图所示：
即，座位号按\(1, \dots, n\)的顺序排列，并且\(n\)号座位靠墙，观众只能从\(1\)号座位侧进入。因此，座位号为\(k\)的观众在试图就坐时，如果存在座位号小于\(k\)的观众已经就坐，那么有人就需要因此起身让出通道，我们称这次就坐发生了“起身”行为。
现在，\(n\)位观演者会以随机的顺序串行地到达剧场，并按照他们各自的票上的座位号就坐。求此过程中，没有发生“起身”行为的就坐的数目的数学期望。
记所求为\(E_n\)，则\(E_1=1\)。针对第一次就坐，列状态转移方程：
\[ E_n = \frac{1}{n} \times 1 + \frac{1}{n} (1 + E_1) + \dots + \frac{1}{n} (1 + E_{n-1}) = 1 + \frac{1}{n}(E_1 + \dots E_{n-1}). \]
这个递推式可以这样求解：
\[ E_n = 1 + \frac{1}{n}(E_1 + \dots E_{n-1}), \\ E_{n-1} = 1 + \frac{1}{n-1}(E_1 + \dots E_{n-2}) \\ \]
两式相减得
\[ \begin{aligned} E_n - E_{n-1} &= \frac{1}{n} E_{n-1} + \left(\frac{1}{n} - \frac{1}{n-1}\right) (E_1 + \dots + E_{n-2}) \\ &= \frac{1}{n} E_{n-1} - \frac{1}{n(n-1)}(E_1 + \dots + E_{n-2}) \\ &= \frac{1}{n} \left(E_{n-1} - \frac{1}{n-1}(E_1 + \dots + E_{n-2}) \right) \\ &= \frac{1}{n}. \end{aligned} \]
故
\[ E_n = E_{n-1} + \frac{1}{n}. \]
代入初值条件得
\[ E_n = H_n, \]
补给线切断问题
现有\(v_0,v_1, \dots, v_{n-1}\)这\(n\)个节点，每个节点\(v_i\)均与其前驱节点\(v_{i-1}\)和后继节点\(v_{i+1}\)相连，节点\(v_0\)没有前驱，节点\(v_{n-1}\)没有后继。
现在，破坏者每轮执行如下操作：
- 从当前图中随机选择一个节点\(v_i\)；
- 移除\(v_i\)及其之后的所有节点，即\(v_i, \dots, v_{n-1}\)。
- 更新当前图为\(v_0, v_1, \dots, v_{i-1}\)。
求直到所有节点被移除，所需经过轮数的数学期望。
考虑每轮破坏相当于一个观众来访，每轮破坏行为与一个没有发生“起身”行为的就坐行为等价。事实上，本题列出的状态转移方程与“不愿起身的占座问题”完全相同。本题答案为\(H_n\)。