（2023 年 12 月，清华大学算法协会 THUPC 2024 初赛）

链接： https://thupc2024.thusaac.com/contest/2/problem/2

题意

给定一个实数 p，0 < p < 1，设 n 个随机变量 X_i 独立同分布于几何分布 G(p)，即

然后，令 Y_1, \dots, Y_n 为 X_1, \dots, X_n 的前缀和，又给定两个整数 l, r，满足 1 \le l \le r \le n，求落在区间 [l, r] 内 Y_i 的期望个数。

现场做法

猜想答案只与区间长度 r - l + 1 有关，平移区间 [l, r] 不改变答案，因此可只考虑区间为 [1, n] 的答案。

使用概率 DP 的方法，设 a_n 表示区间 [1, n] 内的 Y_k 的期望个数，则当 X_1 = k \le n 时，对期望产生 1 的贡献。此时若要 Y_2, \dots, Y_m 仍然落在 [1, n] 内，等价于 X_2, X_2 + X_3, \dots, X_2 + \cdots + X_m 落在 [1, n - k] 内，这个子问题的期望等于 a_{n - k}。由于 X_1 = k 的概率为 (1 - p)^{k - 1} p，有

于是有

等式右边方括号内恰好等于 a_{n - 1}，得到

因此

这说明这个数列是一个等差数列。由于 a_1 = P(X_1 = 1) = p，所以 a_n = np。

因此，原问题只要输出答案 a_n = (r - l + 1)p 即可。

官方题解

考虑有无穷多个灯，编号从 1 开始线性排开，每个灯都有概率 p 亮起。

设 X_1 表示从左向右第一个找到一个亮起的灯的编号，则这个编号就服从几何分布，也就是 X_1 的分布。因此，Y_i 表示第 i 个亮起的灯的位置。

问有多少个数落入 [l, r]，就是在询问，[l, r] 之间有多少个亮起的灯。由于每个灯亮起的概率为 p，由期望的线性，总的亮灯数就是 p(r - l + 1)。

评注

该过程非常类似于 Poisson 过程，只不过是离散的，这个随机过程可以称为 Bernoulli 过程。

同 Poisson 过程，可以定义 \{N(n): n \in \mathbb{N}\} 表示前 n 次抛硬币，有 N(n) 次正面朝上的随机过程，那么显然两次硬币朝上的时间间隔就是几何分布 G(p)，第 k 次硬币朝上的时刻就是负二项分布 Nb(k, p)。

类似泊松过程的模拟，该问题产生 n 个几何分布随机数，再对其求前缀和，也是一次 Bernoulli 过程的硬币朝上时刻的 Monte Carlo 模拟。因此，Y_i 表示第 i 次硬币朝上的时刻，而询问多少个 Y_i 落在区间 [l, r] 中，等价于询问区间 [l, r] 有多少次硬币朝上，该答案服从二项分布 b(r - l + 1, p)，期望为 (r - l + 1)p。