動機
如果目前狀態保留了決定下一次轉移所需的資訊,便較容易研究重複隨機變化。本節建立有限狀態模型,分別研究路徑、首次到達與長期分佈。
定義
狀態保留所需資訊
隨機遊走記錄粒子隨機移動後的連續位置。有限馬爾可夫(Markov)鏈推廣此想法:狀態可以是任何足以決定下一狀態分佈的摘要。狀態不必編碼全部歷史,但模型必須有理由捨去其餘歷史。
設 X0,X1,… 取值於有限集合 S。若每當條件事件概率為正時,
P(Xn+1=j∣X0=i0,…,Xn=i)=P(Xn+1=j∣Xn=i)=pij,且右邊與 n 無關,過程便是時間齊次馬爾可夫鏈。轉移矩陣 P=(pij) 的元素非負,每行之和為一。
本文用行向量,初始分佈 μ0 經一步後為 μ1=μ0P。
馬爾可夫性是條件陳述,不是說連續狀態獨立。知道目前狀態通常會大幅改變下一狀態的概率。反過來,如果狀態遺漏了持續存在的機器模式等重要隱藏變量,過程便可能不是馬爾可夫鏈。
證明思路
以下路徑計算結合乘法公式與馬爾可夫性;到達概率則按第一步分類。兩種方法均不假設相鄰狀態獨立。
路徑與轉移矩陣的冪
對初始概率為 μ0(i0) 的路徑 i0,i1,…,in,由乘法公式與馬爾可夫性,其概率為
P(X0=i0,…,Xn=in)=μ0(i0)pi0i1⋯pin−1in.
對中間狀態求和得到 Chapman–Kolmogorov 公式:從 i 經 n 步到 j 的概率是 (Pn)ij。兩步時它等於 k∑pikpkj;每一項代表一條經 k 的互斥路徑。因此 μn=μ0Pn。
在 0,1,2 三個狀態上,粒子從 0 或 2 必定走到 1;從 1 則以各 1/2 概率走到兩個鄰點。從 1 出發兩步後回到 1 的概率是 (1/2)(1)+(1/2)(1)=1。從 0 出發兩步後到達 2 的概率為 1⋅(1/2)=1/2。列出路徑可避免把互斥選項的概率錯誤相乘。
到達邊界
考慮 {0,1,…,N} 上的遊走,端點 0,N 為吸收狀態。內點每一步獨立地以概率 p 向右、q=1−p 向左,假設 0<p<1。令 hi 為從 i 出發先到 N 而非 0 的概率。
對 0<p<1 的這個遊走,以概率一在 0 或 N 被吸收。從 i 出發先到 N 而非 0 的概率,在 p=q=1/2 時為 hi=i/N;在 p=q 時為
hi=1−rN1−ri,r=pq.
吸收:從內點 i 出發,接下來 N−i≤N 步全部向右便到達 N,所以 N 步內被吸收的概率至少為 δ=min(p,q)N>0。在時刻 N,2N,… 應用馬爾可夫性,超過 kN 步仍未吸收的概率至多 (1−δ)k,極限為零。
方程:按第一步分類,並在時刻一應用馬爾可夫性,得
h0=0,hN=1,hi=phi+1+qhi−1(1≤i<N).求解:因 hi=phi+qhi,遞推式可寫成 p(hi+1−hi)=q(hi−hi−1),所以 hi+1−hi=ri(h1−h0)=rih1,且 hi=h1k=0∑i−1rk。若 r=1,此式為 ih1,由 hN=1 得 h1=1/N,故 hi=i/N。若 r=1,此式為 h1(1−ri)/(1−r),由 hN=1 得 h1=(1−r)/(1−rN),即得上式。方程組的每個解都被迫成為這個形式,所以方程組恰有一個解,而到達概率就是這個解。
證明透視
一個證明裏的三項工作
證明做了三件獨立的事。第一步分類給出方程;它只用到時刻一的馬爾可夫性,在任何狀態空間都成立。關鍵一步是代數的:把遞推式讀成 hi+1−hi=r(hi−hi−1),二階方程便化為只有一個未知數 h1 的等比數列。第二個邊界值隨即確定 h1;當 p=q 時 r=1,所以 1−rN=0。假設 0<p<1 用了兩次:p>0 使 r 有定義,min(p,q)>0 使 δ 為正。吸收保證 1−hi 正是先到 0 的概率;同一幾何存活上界在下文計算期望持續時間時再次使用。在無限狀態空間上沒有第二個邊界值,遞推式留下一族單參數的解,需要額外論證才能選出所求概率。
設 N=3、p=2/3、q=1/3,從 1 出發。r=1/2,故先到 3 的概率是 (1−1/2)/(1−1/8)=4/7。它大於公平遊走的 1/3,但小於一,因為第一步向左便結束實驗。
平穩與長期行為
若概率行向量 π 滿足 πP=π,稱它為平穩分佈。
由歸納法,初始分佈為 π 時,每個時刻的邊際分佈都是 π。這不表示每條路徑不變,也不表示其他初始分佈必定收斂至 π。
概念視角代數
平穩分佈是左特徵向量
方程 πP=π 表示 πT 屬於 PT−I 的零空間:平穩分佈是 P 對特徵值 1 的左特徵向量,並縮放至元素非負且總和為一。非零的左特徵向量必定存在,因為 P 每行之和為一,所以 P1=1、det(P−I)=0,於是 PT−I 亦奇異。這個觀點亦解釋一個實用步驟:把 πP=π 的 ∣S∣ 條方程全部相加,得到恆等式 i∑πi=i∑πi,所以方程互相依賴,可以把其中一條換成 j∑πj=1。單靠線性代數不能證明存在元素非負的特徵向量;對不可約鏈,下面的定理提供這一點。
不可約是指任意一個狀態都可在某個正步數到達任意另一狀態。若鏈亦非週期,則對每個初始分佈 μ0,有 μ0Pn→π。這裏陳述這些標準結果但不證明。不可約是唯一性的充分條件,並非必要條件;上述收斂還需非週期性。
兩狀態確定交替的鏈,其 P 的兩行是 (0,1) 和 (1,0)。方程 πP=π 要求兩個分量相等,唯一平穩分佈是 (1/2,1/2)。若從狀態零出發,分佈卻在 (1,0) 和 (0,1) 之間交替,永不收斂。此鏈不可約,但週期為二。
期望吸收時間
最終結果的概率並不說明遊走需時多久。對上述公平吸收遊走,令 ti 為從 i 出發至吸收所需步數的期望,則 t0=tN=0,按第一步分類得 ti=1+(ti−1+ti+1)/2。額外的一計算第一步,即使它直接進入邊界也要計算。
端點 0,N 吸收的公平最近鄰遊走,從 i 出發的期望吸收時間為 ti=i(N−i)。
要使遞推式成立,吸收時間 T 須有有限期望:上一個證明的幾何存活上界給出 E[T]=n≥0∑P(T>n)≤Nk≥0∑(1−δ)k<∞。遞推式等價於 ti+1−2ti+ti−1=−2。對 ti=Ni−i2,線性部分的二階差分為零,而 −i2 的二階差分為 −((i+1)2−2i2+(i−1)2)=−2;並且 t0=tN=0。若有兩個解,其差的二階差分為零且兩端值為零;該差是線性函數,因而恆為零。所以 i(N−i) 是唯一解。
邊界為 0,6 時,從 3 出發的公平遊走,其期望吸收時間為 3(6−3)=9 步;從 1 出發則為五步。這是平均值而非確定的停時。例如從 3 出發可連續向右三步到達 6,也可遊蕩更久。
此計算亦顯示「向兩個方向移動的概率相等」不表示期望到達邊界的時間只有一步。粒子必須走到端點,並可能因折返而走更長的路。此公式特別依賴有限邊界。
解 πP=π 只能找到轉移下保持不變的分佈,不能單憑此式斷言鏈會接近它。運用有限鏈收斂定理前,要檢查互通結構及週期性。
互通與閉類
若某整數 n≥0 滿足 (Pn)ij>0,稱 j 從 i 可達。若兩狀態互相可達,稱它們互通。
互通把狀態空間分割成類:自反性用到 P0=I,對稱性包含於定義中,而傳遞性來自把正概率路徑接起來。若類內沒有一步轉移到類外,稱該類為閉類。鏈進入閉類後便不會離開。
這個結構有助理解平穩方程。有限鏈若有兩個不同閉類,每個閉類都支持一個平穩分佈;不同的混合給出整條鏈的不同平穩分佈。因此不能因 P 是隨機矩陣就假定平穩分佈唯一。反之,不可約並非唯一性的必要條件。例如狀態零吸收,而狀態一以概率一走到零;唯一平穩分佈集中在零,雖然零不能到達一。
在 0,1,2 三個狀態上,兩端點均吸收,而狀態一以各 1/2 的概率走到兩端。(1,0,0) 和 (0,0,1) 都是平穩分佈,任何混合 (a,0,1−a),0≤a≤1,亦平穩。從一出發,一步後的分佈是 (1/2,0,1/2),以後不變。極限分佈依賴出發狀態,故沒有適用所有初始狀態的單一吸引分佈。
有限不可約鏈中,狀態的週期是所有可能正返回步數的最大公因數;所有狀態週期相同。若有正概率自環,它是一步返回,故不可約鏈的週期必為一。非週期性排除前面的確定交替,但不表示每個狀態都須有自環。只要有長度二和三的返回路徑,其最大公因數已是一。
以流量推導平穩分佈
πP=π 表示平衡:下一步處於某狀態的概率是流入該狀態的概率之和。這不要求每對狀態之間的流量相等。然而較強的成對條件,即細緻平衡,常方便計算。
若概率向量 π 對所有 i,j 滿足
πipij=πjpji,則 πP=π。
固定 j,對 i 把假設相加:i∑πipij=i∑πjpji=πji∑pji=πj,因為第 j 行之和為一。左邊正是 πP 的第 j 個分量。
反例模式
不滿足細緻平衡的平穩鏈
聲稱:每個平穩分佈都滿足細緻平衡。在狀態 0,1,2 上令鏈確定地沿 0→1→2→0 移動,即 p01=p12=p20=1,其餘元素為零。P 每一列恰有一個元素 1,所以 π=(1/3,1/3,1/3) 滿足 πP=π。但 π0p01=1/3,而 π1p10=0。聲稱不成立:每個狀態的總流入平衡,弱於每對狀態之間的平衡;定理只給出充分條件。
轉移矩陣兩行為 (3/4,1/4) 和 (1/2,1/2)。成對平衡要求 π0/4=π1/2,即 π0=2π1;加上 π0+π1=1,得 (2/3,1/3)。兩個非對角流量都等於 1/6。對角平衡自動成立,把答案代入 πP 可再作獨立檢查。
第一步分析與邊界問題
到達概率的遞推並不限於直線。對有限鏈中互不相交的目標集 B 與失敗集 C,令 hi 為先到 B 而非 C 的概率。在 B 上設 hi=1,在 C 上設 hi=0;在兩集以外,按第一步分類得 hi=j∑pijhj。若從每個其餘狀態出發都以概率一到達 B∪C,方程解唯一。
證明唯一性:兩個解之差記為 d。反覆代入可把 di 表為在第 n 時刻尚未到達邊界時 d 的期望。有限狀態空間上 d 有界,而尚未到邊界的概率趨零,所以期望趨零,故 di=0。
幾乎必然到達邊界的條件很重要。若外部有吸收狀態,該處方程只是 hi=hi,不能決定其值。先到目標而非失敗的事件仍然定義良好,但單靠邊界方程需要額外資訊。因此檢查可達性與終止性是建立計算的一部分,而非可有可無的代數細節。
狀態選擇與預測
指定狀態後,轉移矩陣才有意義。假設裝置有持續多步的隱藏模式,發出警告的概率取決於該模式。單獨的警告序列不一定是馬爾可夫的:即使知道目前警告,較早警告仍可提供目前模式的資訊,從而改變下一警告的預測。若模型的轉移確實只依賴擴大的狀態,把模式加入狀態便可能恢復馬爾可夫性。
即使轉移矩陣正確,沒有初始分佈也未指定完整過程。同一矩陣在不同出發分佈下可產生不同有限時間分佈,μn=μ0Pn 清楚顯示這點。平穩初始分佈只是一個選擇,不是預設假設。計算矩陣冪前應記錄狀態次序,以及分佈採行向量還是列向量;反轉約定會改變乘法次序。
以行向量表示分佈時,更新是 μn+1=μnP。若改算 PμnT,組合的是 P 某一列的元素。對兩行為 (3/4,1/4) 和 (1/2,1/2) 的矩陣及 μ0=(1,0),正確結果是 μ1=(3/4,1/4);而 Pμ0T=(3/4,1/2)T,元素之和為 5/4,並不是分佈。檢查元素之和是否為一,便能立即發現錯誤。
總結
轉移矩陣的冪決定有限時間的分佈;第一步方程可解邊界問題。平穩分佈在轉移下保持不變,而從所有初始分佈收斂還需要適當假設,例如有限、不可約及非週期。
練習
快速檢查
(公平遊走在 0,5 吸收,從 2 出發。求先到 5 的概率。)
解答 · 答案
公平公式 hi=i/N 給出 2/5。
快速檢查
(轉移矩陣兩行為 (3/4,1/4) 和 (1/2,1/2)。求平穩分佈。)
解答 · 答案
寫 π=(a,1−a)。平穩方程第一個分量為 a=3a/4+(1−a)/2,即 3a/4=1/2,故 a=2/3,π=(2/3,1/3)。
快速檢查
(上一題的鏈從狀態 0 出發,求兩次轉移後在狀態 1 的概率。)
解答 · 答案
把 0→0→1 與 0→1→1 兩條路徑相加:(3/4)(1/4)+(1/4)(1/2)=3/16+2/16=5/16。