討論一個有趣的概率問題：

[P3334 ZJOI2013] 拋硬幣 - 洛谷

實際上是一個猴子打字問題，考慮一直無規律隨即打字的猴子，鍵盤上只有A-Z一共26個字母，對于一個特定的字符串 $S$ ： ABCABCAB ，能否在有限的打字次數后精確得到這個字符串。

所需的打字次數的期望是有限的，但是打字次數是呈指數增長的。

期望次數是 $26^8+26^5+26^2$ （與前后綴相同 (border) 的長度有關系）

一個巧妙的證明可以用 停時與鞅的性質 來完成。

首先介紹停時的概念：停時，通俗而言，一個事件停止的時間，并且這個事件停止的時間只依賴于停止之前的所有狀態。形式上，停時是一個隨機變量 $\tau$，指的是對于任意的時間 $t\in I$ ，滿足 { τ ≤ t } ∈ F t \{\tau\leq t\} \in F_t {τ≤t}∈Ft? ，即對于任意時間 $t$ ，任意在 $t$ 之前停止的事件 { τ ≤ t } \{\tau \leq t\} {τ≤t} 只依賴于 $t$ 之前的狀態（$F_t$ 即為在 $t$ 之前發生的所有事件的集合，也就是所有 $t$ 之前發生的狀態）。

用 $T$ 表示猴子得到目標字符串所需要的時間。

例如字符串一匹配完我們就停止，那么這個事件的停止時間只依賴于停止之前的所有狀態（所打的字符），而不依賴于停止之后的所有狀態（還沒有打的字符），那么就說明這個停止時間 $\tau$ 是一個停時 ($\text{stopping?time/optinal?time}$) 。

停時具有很好的性質，利用可選停止定理來得到停時的期望，具體是構造一個公平賭博。

假設存在無數個賭徒，當猴子每打出一個字符前的一瞬間，一個賭徒進場并投注 $1$ 元給 $S_1$ ，假如中了就翻 26 倍，投給 $S_2$ … 直到字符串完全匹配為止或者出現失配情況。并且我們假設賭場在遇到目標字符串馬上關閉賭場，這個時間為 $T$ ，顯然 $T$ 是一個停時。

可以發現，$T$ 時刻賭徒們的帶入賭資一共為 $T$ 元，帶出的錢一共是 $26^8+26^5+26^2$ 。

為什么？因為一共只有三個人能贏錢出去，其中有一個人大贏，另外兩個人贏到一半賭場就關閉了，（注意這個長字符串的后綴是特定字符串 $S$，所以只有特定字符串中前后綴相同的長度可以贏錢，其他人都是輸光走人）

由于是公平賭場，當這個 $T$ 是停時的時候，可以用鞅的性質和可選停止定理來證明，帶入賭資的期望和帶出的錢的期望是相等的。也就是 $T$ 的期望是 $26^8+26^5+26^2$ 。具體可以參考 鞅 。

那么我們也很容易可以完成類似的題目，只要產生字符的概率是獨立的，且產生相同字符的概率是相等的，就可以用所有 $\text{border}$ 的概率積的倒數之和來算出產生該字符串的期望。