n次生成下的随机序列出现概率
相关问题：随机序列的首次生成问题 | Mercury's Blog (zrephel.fun)
简单形态（\(p=1/2\) 的推广形态）：抛掷一枚均匀硬币若干次，记 0 为反面，1 为正面。求在 \(n\) 次抛掷后，至少出现了一次连续 \(m\) 个 1 的概率。
推广形态：给定一个字符生成器，每次以概率 \(p\) 生成字符 \(i\)。当生成次数为 \(n\) 时，求至少产生了一次连续 \(m\) 个字符 \(i\) 的概率。
解答
我们直接解答推广的问题形态。
记当生成次数为 \(n\) 时，至少产生了一次连续 \(m\) 个字符 \(i\) 的概率为 \(f_n\)。记生成 \(i\) 看作出现了结果 1，否则看作出现了结果 0。
我们考虑已经生成了 \(n\) 个字符时的状态。此时，我们倒着考察第 \(n\) 次生成的结果，直到第 \(n - m + 1\) 次生成的结果。将这 \(m\) 个结果按照生成次序倒序编码为 \(1, \dots, m\)。考虑它们之中倒序首次出现 0 的位置：
- 若这些结果中没有出现 0，则此时已经出现了连续 \(m\) 个 1，\(f_n = 1\)。出现这种情况的概率为 \(p^m\)。
- 若这些结果中首次出现 0 的位置在第 \(i\) （\(1 \leq i \leq m\)）个结果处，那么这 \(n\) 次生成中，如果能产生一次连续 \(m\) 个 1，就只能是在第 \(n-i\) 次生成之前产生了，于是我们可以考虑从状态 \(f_{n-i}\) 转移过来。出现这种情况的概率为 \(p^{i-1} (1-p)\)。
从而，状态转移方程为
\[ f_n = p^m + \sum_{i=1}^m p^{i-1} (1-p) f_{n-i}, i \geq m \]
初值条件为 \(f_0 = f_1 = \dots = f_{m - 1} = 0\)。
编程求解，时间复杂度为 \(O(nm)\)。
特别地，当 \(n = 1000, m = 10, p = 1/2\) 时，结果约为 \(f_{1000} \approx 0.3854\)。
容易证明，当 \(n \gg m\)，\(p > 0\) 时，\(\lim_{n \to \infty} f_n = 1\)。