随机序列的首次生成问题
题干
抛掷一枚均匀硬币若干次，记0为反面，1为正面，求直到抛掷结果序列\(s\)首次出现，所需抛掷次数的数学期望。
具体的\(s\)可以是001、1111或1101001等。
推广（猴子打字问题）：给定一个字符生成器，每次以概率\(p_i\)生成字符\(i\)，且\(\sum_i p_i = 1\)。求直到生成序列\(s\)首次出现，所需生成次数的数学期望。
解答
方法1：朴素马尔可夫链
这种方法适用于短序列的求解，通用性不强，因为需要求解一个维度为\(\Theta(2^{|s|-1})\)的线性方程组，当\(s\)的长度较大时难以计算。
方法2：考虑两个相同序列之间的期望距离
这一方法的通用性也不强，但提供了一种有趣的思路。它依赖如下定理：
定理 给定一个充分长的字符串，它由每次以概率\(p_i\)生成字符\(i\)，且\(\sum_i p_i = 1\)的字符生成器生成。现有一长度为\(|s|\)的滑动窗口框选出某一序列\(s\)，然后不断向右滑动，直到框选到某一内容与\(s\)相同的序列\(t\)（\(s\)与\(t\)位置不同，但可重叠）。记\(s = \{c_{i}\}_{i = 1, \dots, |s|}\)，此过程中滑动窗口滑动的距离为\(X\)，则\(E(X) = \left( \prod_{i=1}^{|s|} p_{c_i} \right)^{-1}\)。
特别地，对于均匀硬币字符生成器，有\(p_1 = p_2 = \frac{1}{2}\)，于是\(E(X) = 2^{|s|}\)，与\(s\)的具体内容无关。
定理的证明比较复杂，笔者也不会。
由此可对已生成了序列后的情况列状态转移方程。
例如，对于硬币序列\(s = 100\)，我们注意到，无论之后掷出0还是1，结果为000或001，这与从零开始掷骰子没有任何区别，即等价于000等价于0，001等价于1。于是从零开始掷出\(100\)所需次数的数学期望恰好等于两个\(100\)之间的距离的数学期望，为\(2^3 = 8\)。
而对于硬币序列\(s = 101\)，情况有所不同。如果之后掷出1，则011等价于1；但若之后掷出0，则会出现1010等价于10，并非从零开始。画出状态转移图如下：
记从状态\(i\)出发，首次回到状态\(101\)所需转移次数的数学期望为\(E_i\)，列出状态转移方程
\[ \begin{cases} E_{101} = \frac{1}{2}(E_{10} + 1) + \frac{1}{2}(E_{1} + 1) = 8, \\ E_{10} = \frac{1}{2} \times 1 + \frac{1}{2}(E_{0} + 1), \\ E_{1} = \frac{1}{2}(E_{1} + 1) + \frac{1}{2}(E_{10} + 1), \\ E_{0} = \frac{1}{2}(E_{0} + 1) + \frac{1}{2}(E_{1} + 1). \end{cases} \]
解得\(E_0 = 10, E_1 = 8\)。那么，从零开始直到生成\(s\)所需次数的数学期望就是\(E = \frac{1}{2}(E_0 + 1) + \frac{1}{2} (E_1 + 1) = 10 = E_0\)。
方法3：鞅
这是一个非常巧妙，也非常通用的方法。
设我们想要得到的序列为\(s = \{c_i\}_{i = 1, \dots, n}\)。
构造公平赌局。设想有一列赌徒在一个公平的赌场参赌，这个赌场使用的唯一一台赌博机就是题目中的字符生成器，且每天都只生成一个字符，因此所有的赌徒在相同天数看到的字符都是相同的。每个赌徒起初都有\(1\)元。第\(i\)名赌徒会在第\(i\)天的开始赌起，首先以他的\(1\)元打赌那天产生的字符将是\(c_1\)。若
- 打赌赢了，则获得\(d_1 = p_{c_1}^{-1}\)元。该赌徒现在有\(p_{c_1}^{-1}\)元，并继续以这些钱赌下一天的结果是\(c_{2}\)。
- 打赌输了，则永久退出赌局。
以此类推，若第二天的赌局也胜利了，则赌徒将拥有\(d_2 = p_{c_1}^{-1} \cdot p_{c_2}^{-1}\)元，并继续以\(d_2\)的钱赌下一天的结果是\(c_{3}\)，直到赌完\(n\)次，得到序列\(s\)为止。
可见，所有赌徒的赌法都是全押，即便输了，也只会给赌场贡献\(1\)元钱。但若有一名赌徒全胜，他将得到来自赌场的\(d_n - 1 = \prod_{i=1}^n p_{c_i}^{-1} - 1\)元的收益。
每天一开始，就会有一名新的赌徒开始赌。记\(Y_m\)为第\(m\)天结束时赌场的总收入，由于所有的打赌都是公平的，故 \(\{Y_m, m \geq 1\}\)是鞅，均值为\(0\)。
现在考虑直到一名赌徒全胜，赌场赢得的情况。记\(X\)为直到一名赌徒全胜，经过的天数。
对于长度为\(n\)的序列\(s\)，这名赌徒第一次赌的是第\(X- n+1\)天的结果。由于该序列在这名幸运赌徒赌的过程中首次出现，因此这名幸运赌徒的前辈都唯一例外输了\(1\)元，共计为赌场贡献了\(X-n\)元。
而幸运赌徒得到了\(d_n - 1\)元。
那么，幸运赌徒的后辈呢？他们可能有得有失。具体而言，在第\(X-k + 1\)（\(1 \leq k \leq n\)）天开始赌的赌徒赢钱，当且仅当\(s\)的长度为\(k\)的后缀与\(s\)的同等长度的前缀完全相同，且这名赌徒恰好赢得\(d_k - 1\)元。
故赌场在这一过程中的总收入为
\[ Y_X = X - n + \sum_{i=1}^n f_i \]
其中
\[ f_i = \begin{cases} 1, & s_{1:i} = s_{n-i+1:n}, \\ 1 - d_i, & \text{otherwise}. \end{cases} \]
化简得
\[ Y_X = X - \sum_{i=1}^n \delta_{i} d_i \]
其中
\[ \delta_i = \begin{cases} 1, & s_{1:i} = s_{n-i+1:n}, \\ 0, & \text{otherwise}. \end{cases} \]
由于\(E(Y_X) = 0\)，故
\[ E(X) = \sum_{i=1}^n \delta_{i} d_i = \sum_{i=1}^n \delta_i \frac{1}{p_{c_1}p_{c_2}\dots p_{c_i}}. \]
例子
- \(s = 0 ... 0\)（\(n\)个\(0\)），
\[ E(X) = \sum_{i=1}^n 2^{i} = \frac{2(1-2^n)}{1-2} = 2^{n+1}-2. \]
- \(s=100\)，\(E(X) = \sum_{i=1}^3 \delta_i d_i = d_3 = 2^3 = 8\)。
- \(s=101\)，\(E(X) = d_1 + d_3 = 2 + 2^3 = 10\)。
- \(s = \text{tencent}\)，\(p_{i} = \frac{1}{26}\)，\(i \in \{ \text{'a'}, \dots, \text{'z'}\}\)，
\[ E(X) = 26 + 26^7. \]