劉應興的部落格

符號串之範型 (pattern) 問題，以最簡單，由 S/F 兩種符號構成的隨機串列如 SFFSFSSSF... 中特定範型如 SSS 出現的機率相關問題為例，包括平均多長的符號串出現一個指定範型、固定長符號串出現指定範型機率、及固定長符號串平均出現幾次指定範型。

假設符號串如上述是獨立地由 S 和 F 組成，並且，P{S}= p = 1 - q = 1 - P{F}，指定範型是 SFSF。考慮出現範型的期望時間 E[L]，E[L|s] 表示開頭符號串為 s 時 L 的期望值，則

E[L] = p E[L|S] + q E[L|F] = p E[L|S] + q(1+E[L])
E[L|S] = p E[L|SS] + q E[L|SF] = p(1+E[L|S]) + q E[L|SF]
E[L|SF] = p E[L|SFS] + q E[L|SFF] = p E[L|SFS] + q(3+E[L])
E[L|SFS] = p E[L|SFSS] + q E[L|SFSF] = p(3+E[L|S]) + 4q

因此得

E[L] = 1/(pq) + 1/(p^2q^2)

上列計算方式頗繁瑣，用馬可夫鏈 (Markov chain) 有較簡單的解釋：如果我們以 Zn 表示各次獨立二項試作 (independent Bernoulli trials) 結果是 S 或 F，又定義 Xn= (Z(n-3),Z(n-2),Z(n-1),Zn)，則 Xn, n = 4,5,6,... 構成一馬可夫鏈，上述 L 即是由狀態 (state) S0 = (S,F,S,F) 離開又回到狀態 S0 所需步驟。此馬可夫鏈的狀態空間 (state space) 共有 2^4 = 16 個不同狀態。另外，停在狀態 S0 的機率即是連續 4 個符號是 SFSF 的機率，即 p^2q^2。因此由 S0 回到 S0 的平均步驟數是 1/(p^2q^2)。但這意謂如果由 SF 開始，平均需經 1/(p^2q^2) 步才能得到 SFSF 這樣的結果；由於要得到 SFSF 必須先達到 SF，因此

E[time to pattern SFSF] = E[time to pattern SF] + 1/(p^2q^2)

用馬可夫鏈的方法，令 Xn = (Z(n-1),Zn) 類似先前以連績 4 次試作定義，只是現在改成連續兩次試作的結果，則離開 (S, F) 後回到 (S, F) 平均需步驟數 1/(pq)，但這又等於

E[time to pattern SF]　＝　１/(pq)

即初次達到 (S, F) 的平均試作數。何以故？在出現 SF 後出現 S，就如同第一次試作結果是 S；同樣，在 SF 之後出現 F 如同第一次試作結果是 F。結果同前面遞迴法所得，L 的期望值是 1/(pq) + 1/(p^2q^2)。

事實上

「由 SF 開始，得到 SFSF　平均需經的步驟數」= E[L|SF] - 2

因 E[L|SF] 是 SF 開始到達 SFSF 的期望步驟數，而此數包含 SF 兩步；上列「平均需經的步驟數」則是不計 SF 這兩步。由前面 E[L] 與 E[L|S] 的公式可解得

E[L] = E[L|SF] + q/p + p/q = (E[L|SF] - 2) + 1/(pq) = 1/(p^2q^2) + 1/(pq)

如果指定範型是 SSSS，則

E[L] = p E[L|S] + q(1+E[L])
     = p^2 E[L|SS] + q(1+E[L]) + pq(2+E[L])
     = p^3 E[L|SSS] + q(1+E[L]) + pq(2+E[L]) + p^2q(3+E[L])
     = 4p^4 + (q+2pq+3p^2q+4p^3q) + (q+2pq+3p^2q+4p^3q)E[L]
     = 4 + (q+2pq+3p^2q+4p^3q)/p^4
     = (1-p^4)/(qp^4)

用馬可夫鏈及縮減起始條件的方法：

E[till SSSS] = E[till SSS] + 1/p^4 = E[till SS] + 1/p^3 + 1/p^4
   = E[till S] + 1/p^2 + 1/p^3 + 1/p^4
   = 1/p + 1/p^2 + 1/p^3 + 1/p^4
   = (1-p^4)/(qp^4)

用條件期望值逐步發展的方法，或馬可夫鏈縮減起始條件的方法，都能處理任何符號集任何範型的平均出現時間（平均符號串長度）, 只是前者計算繁瑣，後者需了解如何縮減。例如符號集 {0,1,2,3}，範型 012301，馬可夫鏈的方法是

E[till 012301] = E[till 01] + 1/[(p0^2)(p1^2)(p2)(p3)]
   = 1/[(p0)(p1)] + 1/[(p0^2)(p1^2)(p2)(p3)]

條件期望值的方法得到下列方程式：

E[L] = p0 E[L|0] + (1-p0)(1+E[L]) = E[L|0] + (1-p0)/p0
E[L|0] = p1 E[L|01] + (1-p1)(1+E[L|0]) = E[L|01] + (1-p1)/p1
E[L|01] = p2 E[L|012] + p0(2+E[L|0]) + (1-p0-p2)(3+E[L])
E[L|012] = p3 E[L|0123] + p0(3+E[L|0]) + (1-p0-p3)(4+E[L])
E[L|0123] = p0 E[L|01230] + (1-p0)(5+E[L])
E[L|01230] = 6(p1) + p0(5+E[L|0]) + (1-p0-p1)(6+E[L])

然後解出 E[L]。此例充分顯示馬可夫鏈方法的簡捷。

考慮擲公正銅板的例子，p = 1/2, 範型 HTHT 的平均等待時間是 4 + 16 = 20；範型 HHHH 的平均等待時間是 2 + 4 + 8 + 16 = 30。下面是模擬結果：

> MeanLength(n=50000,prob=0.5,pattern=c(1,0,1,0),ifprtr=F,ifprtl=F)
Total  50000  trials, obtained  2469  pattern matched.
MeanLength = [1] 20.24504
> MeanLength(n=50000,prob=0.5,pattern=c(1,0,1,0),ifprtr=F,ifprtl=F)
Total  50000  trials, obtained  2431  pattern matched.
MeanLength = [1] 20.56479
> MeanLength(n=50000,prob=0.5,pattern=c(1,1,1,1),ifprtr=F,ifprtl=F)
Total  50000  trials, obtained  1648  pattern matched.
MeanLength = [1] 30.30704
> MeanLength(n=50000,prob=0.5,pattern=c(1,1,1,1),ifprtr=F,ifprtl=F)
Total  50000  trials, obtained  1681  pattern matched.
MeanLength = [1] 29.72516
> MeanLength(n=50000,prob=0.5,pattern=c(1,1,1,1),ifprtr=F,ifprtl=F)
Total  50000  trials, obtained  1586  pattern matched.
MeanLength = [1] 31.51955

雖然是公正銅板，雖然範型 HTHT 和 HHHH 同樣是 4 個符號長度，但等待範型出現的平均（期望）時間卻不等，很難給予一個一般性公式。不過，對於特殊範型如 S...S, SF...SF 倒是可能給予一般式，例如連續 k 個 S 平均需

E[L] = 1/p + ... + 1/p^k = (1-p^k)/(qp^k)

個 S/F 符號；而 SF 重複 k 次則是需

E[L] = 1/(pq) + ... + 1/(pq)^k =[1-(pq)^k]/[(pq^k)(1-pq)]

指定範型初次出現的位置，或即範型的等候時間或間隔時間 L，和固定長字串是否出現該範型的機率有對應的關係：

[長度 n 的符號串出現指定範型] = [範型出現位置(L) ≦ n]

令  P(n) 代表指定範型在長度 n 的符號串出現的機率，考慮符號集 {S, F}，範型 SSSS；P(n)[s] 表示已有符號串 s 開頭，指定範型出現的機率。則

P(n) = p P(n)[S] + q P(n-1)
       = p^2 P(n)[SS] + pq P(n-2)) + q P(n-1)
       = p^3P(n)[SSS] + p^2q P(n-3) + pq P(n-2)) + q P(n-1)
       = p^4 + p^3q P(n-4) + p^2q P(n-3) + pq P(n-2) + q P(n-1)

這是一個 4 階遞迴式（差分方程式）,  加上初值條件 P(0) = P(1) = P(2) = P(3) = 0，可以得唯一解。一般，如果範型是連續 k 個 S，則

P(n) = p^k+ Σ_{j=1~k} p^(j-1)q P(n-j)

注意 1 = p^k + Σ_{j=1~k} p^(j-1)q，這意謂 P(n) ≡ 1 是一解。但此解違反初值設定（及 P(k) = p^k），所以 P(n) = 1 只能是穩定解。事實上 n 愈大 P(n) 愈大，而它又受限於不超過 1，因此 lim P(n) 存在，而此極限（穩定解）就是 1。

要解上列遞迴式，可先解其特徵方程式

r^k = Σ_{j=1~k} p^(j-1)q r^(k-j)

當且僅當 p = k/(k+1) 時，其唯一正實根是 r = p。若 r ≠ p 則特徵方程式可簡寫成

r^k = (r^k - p^k)/(r-p)

解得特徵方程式的 k 個根 r[j], j = 1,...,k 後

P(n) = C0 + Σ_{j=1~k} Cj r[j]^n

而由 P(0) = … = P(k-1) = 0 及 P(k) = p^k 可得出係數 Cj, j = 0, 1, ..., k 的值。不過，如何解得特徵方程式是個問題，筆者不知是否能得公式解，但應可用數值法解得數值解。若不需要得在一般 k 或特定 k 時 P(n) 的通式，當然亦可由 P(n) 的遞迴式逐步計算特定 k 之下 P(n) 的結果。

考慮範型 SFSF，則

P(n) = p P(n)[S] + q P(n)[F] = p P(n)[S] + q P(n-1)
P(n)[S] = p P(n-1)[S] + q P(n)[SF]
P(n)[SF] = p P(n)[SFS] + q P(n-3)
P(n)[SFS] = p P(n-3)[S] + q P(n)[SFSF]
P(0) = P(1) = P(2) = P(3) = 0 = P(1)[S] = P(2)[S] = P(3)[S]

其中 P(n)[SFSF] 當 n < 4 時是 0, 當 n ≧ 4 時是 1，以 δ 代之。經整理後得

P(n) = q P(n-1) + pq^2 P(n-3) + p^2 P(n-1)[S] + p^3q P(n-3)[S] +p^2q^2δ
P(n)[S] = q^2 P(n-3) + p P(n-1)[S] + p^2q P(n-3)[S] + pq^2δ

這聯立差分方程比前例的單一差分方程更麻煩，因為涉及矩陣運算，遠不似純量運算那麼簡單。不過，在給定 P(n)[S] 的情況下，

P(n) = q P(n-1) + pq^2 P(n-3) + f(n)

其中 f(n) = p^2 P(n-1)[S] + p^3q P(n-3)[S] +p^2q^2δ；而在給定 P(n) 情況下，

P(n)[S] = p P(n-1)[S] + p^2q P(n-3)[S] + g(n)

其中 g(n) = q^2 P(n-3) +  pq^2δ。分開處理的方式一方面讓我們可透過遞迴計算得到 P(n) 及 P(n)[S]；另方面也可利用三次方程式公式解得到用 f(n) 及 g(n) 表達的 P(n) 和 P(n)[S] 通式，不過要得到 P(n) 的明確通式可能還是有困難。

假設對一特定範型，對每一長度 n 的符號串都計算得 P(n)，則依前面所述，

P(n) = P[L≦n]

其中 L 是符號串開始至首次出現（完成）範型之總符號數，或前一次出現範型之後至下一次範型出現的符號數。由上式知

P[ L = n ] = P(n) - P(n-1), n = k, k+1, ... (k 為範型長度)

考慮連績出現指定範型之長度 L(m), m = 1, 2,...，則 L(m) 是 i.i.d. 的，這是範型出現的間隔時間過程。又令 N(t) 是間隔時間過程 L(m) 對應的計數過程，t = 1, 2, ...，則 N(t) 是一個間斷型時間的更新過程 (renewal process)，理論上可以得到長度 T 的符號串出現 N 次指定範型的機率分布。由於它是一個更新過程，有關更新理論的一些結果也可應用。

隨機符號串中的範型問題，困難在於計算，範型的結構決定了範型等候時間 L 的機率分布計算，而且通常很難得到機率分布的通式，只能用遞迴式計算；不過，L 的期望值相對於其機率分布，就簡單多了。

本文假設符號每次是 i.i.d. 出現的，若非這種情形，則問題會更加繁複。