随机序列的首次生成问题

一道抛硬币问题的不同解法和比较 | 统计之都 (cosx.org)

题干

抛掷一枚均匀硬币若干次,记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,并非从零开始。画出状态转移图如下:

states
states

记从状态\(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}}. \]

例子

  1. \(s = 0 ... 0\)\(n\)\(0\)),

\[ E(X) = \sum_{i=1}^n 2^{i} = \frac{2(1-2^n)}{1-2} = 2^{n+1}-2. \]

  1. \(s=100\)\(E(X) = \sum_{i=1}^3 \delta_i d_i = d_3 = 2^3 = 8\)
  2. \(s=101\)\(E(X) = d_1 + d_3 = 2 + 2^3 = 10\)
  3. \(s = \text{tencent}\)\(p_{i} = \frac{1}{26}\)\(i \in \{ \text{'a'}, \dots, \text{'z'}\}\)

\[ E(X) = 26 + 26^7. \]