趣题: 单词出现的期望时间

趣题: 单词出现的期望时间 #

题目 #

有一个损坏的打字机, 每次独立等概率地打出 ‘a’ - ‘z’ 这 26 个字母之一. 以下哪个单词出现的所需的期望时间最短?

1. salsa
2. level
3. greek
4. random

Solution 1 #

考虑一个 “猜测下一时刻字母” 的游戏, 如果玩家猜对, 会获得 $N=26$ 元 (含本金). 每个时间点都有一个新玩家带着 $1$ 的本金入场, 每个玩家都按照字符串 $S$ 的顺序下注, 如果猜错就离场, 如果猜对就 all in 下一轮. 这个游戏在 $S$ 第一次完整出现时停止, 这个时刻为 $T$.

考虑 $T$ 时刻, 所有留在场内的玩家的获得的总金额 (此时没有留在场内的玩家已经亏完离场了). 在 $T-L+1$ 入场时的玩家会收获 $N^L$ 元; 除了他, 如果 $S$ 存在前缀和后缀字符串相同的情况, 那么相应时刻押注前缀的玩家也能挣到后缀的钱, 后缀长度为 $K$ 时为 $N^K$ 元.

由于这个游戏是公平的 (猜对的概率乘上回报恰好等于投入), 所以截至最后一刻的总投入等于最后一刻的总支出, 有 $$E[T] = \sum_{k=1}^{L} N^k\cdot I(S[:k]==S[-k:])$$

因此, 存在前后缀的匹配的字符串, 其出现的期望时间反而更长. 在相同长度中, greek 出现的期望时间最短.

一些相关的问题以及更详细的解答可以参考这篇写得很好的博客: 模式的等待时间与反直觉概率.