動機
有限馬爾可夫(Markov)模型可以用不同方式完成:任務可能成功終止、永久失敗,或進入一組永遠互相切換的閉模式。前兩者是吸收狀態,後者是吸收目的類,卻不是單一吸收狀態。若太早把它們混為一談,計算會回答錯誤的概率問題。
正確次序是先看結構,再作代數。找出互通類及其中的閉類,然後分開仍可離開的狀態與最終到達的目的地。所得區塊矩陣使佔用次數、完成時間及目的概率,成為使用同一個逆矩陣的不同計算。
先備知識是有限隨機矩陣、條件概率及前文已證的擊中時刻馬爾可夫性。以下會證明逆為何存在及其分量的意義,而非以數值求逆代替理由。
定義
定義 2.7.1
(互通類與分塊形式)
若某有限步轉移概率正,稱一狀態可達另一狀態。互相可達把有限空間分成互通類;沒有轉移離開的類稱閉類。列出閉不可約類 ,聯集為 ,其餘狀態組成 。重排次序得
描述 內轉移, 進入 的個別狀態, 是 內隨機矩陣。若每個閉類都是單一吸收狀態,;閉目的類若仍切換, 一般不是單位矩陣。
定義 2.7.2
(離開時間與類指示矩陣)
令 。由 開始時,計算時刻 的所有暫態到訪,不包括時刻 的入口到訪。若閉狀態 屬於 ,令 ,否則為零。因此 是一步進入目的類的概率, 則保留精確入口狀態。 空是已在閉類的平凡情形,以下逆矩陣計算針對非空 。
定理/命題
定理 2.7.3
(幾何區段界保證離開)
每個 中狀態都幾乎必然到達 ,且 各矩有限。更確切地,存在有限 及 ,使
因此 ,且
是分量非負、數值有限的矩陣。
定理 2.7.4
(佔用、目的與所需時間)
對 ,基本矩陣滿足
精確入口矩陣為 ,目的類矩陣為 ,兩者每行都是和為一的概率。 的均值及二階矩列為
若每次暫態到訪支付代價列 ,終端類報酬列為 ,期望總值為 。
概念視角分析
把目的地概率看成邊值問題
固定一個類 ,對 令 ,對 令 。首步條件化使 在每個暫態狀態上調和,即 ,邊界值在 上為一、在其他閉類上為零。在 上這就是 ,其中 是第 個單位列向量; 可逆,使 成為唯一解。因此目的地概率是邊界數據唯一的調和延拓;平均持續時間則解同一問題,只是加上源項 ,並取零邊界值。
證明思路
求逆以前先找最終目的地
證明
(由類圖得到一致的離開路徑)
互通類的有向圖不能在不同類之間有有向循環,否則循環中的類互相可達,應屬同一類。有限有向無環圖的每個頂點,都有路徑到某個終端頂點,終端類正是閉類。因此每個暫態候選都有正概率有限路徑通往 。
從 各狀態選一條此類路徑。有限性提供共同長度上界 及共同正概率下界 。給定仍在 外的任意歷史,往後 步內進入 的概率至少 ,反覆條件化便得區段尾界。這也證明 各狀態暫態:在 外的期望總時間有限,個別狀態的期望到訪次數因而有限;不是單憑它不吸收便稱暫態。
的行和是至第 步仍在 外的概率,尾界因此證矩陣級數收斂。有限部分和乘 望遠鏡相消成 ,餘項趨零,證左右逆均成立,毋須先假設譜計算。同一幾何界給某個正參數的指數矩有限,故普通矩全部有限。
證明透視
有限性為何給出幾何離開界
有限性用了兩次。它令類圖成為有限無環圖,因此每個類都有路徑到達終端類,即閉類;它亦令同一個長度 及同一個概率 適用於 中每個起點。關鍵一步是在每段 步之後重新應用路徑下界:給定任何仍在 外的歷史,鏈正處於 的某個狀態,由該處沿所選路徑成功的概率至少為 。把這些條件失敗上界相乘便得 。論證以代數而非譜方法閉合: 的行和是生存概率,幾何尾界使 收斂,伸縮恆等式再確認此和為 。
沒有有限性,一致常數可以失效。在 上,令狀態 以概率 進入 ,否則移到 。每個狀態都有一步到達 的路徑,但由狀態 出發,鏈永遠留在 的概率是 。
解釋逆及其乘積
證明
(把逆矩陣解讀為次數、入口與時長)
是尚未進入 且第 步在 的概率。 閉,進入後不能回來。對非負指示變量求和並用 Tonelli,得到 的佔用意義。
在第 步進入閉狀態 的概率是 。各入口時刻互斥,除零概率外窮盡路徑,加總得 。再按類合併入口狀態得 。代數檢查是 ,故 。非負性與行和共同驗證真正概率,而不只是線性方程的解。
從暫態開始,無論下一步到暫態還是目的地,都先經過一步。首步條件化得 ;暫態續程的一加剩餘時間平方,給 。乘 ,用 即得矩公式。有限性已先證明,所以二階矩方程合法。代價及終端報酬則滿足 ,解為 ,不假設相鄰到訪獨立。
入口不是目的類內的平衡
完整有限時間轉移矩陣為
各項選擇首次進入的時間,再於閉類演化,可歸納或按互斥路徑證明。相比之下, 只記錄首次進入哪裏,一般並非最終狀態的極限分佈。
若每個閉不可約類皆非週期,前文已證的有限鏈收斂定理可用於各類。給定有限入口時刻與狀態,未來收斂至該類平穩分佈。把晚於 入口的尾部界為 ,先對截至 的有限多個入口時刻令觀察時間增大,再令 增大,便證極限混合權重為 。閉類有週期時,入口概率仍正確,但普通收斂須另查,不能由 推出。
截止時間與給定目的地
截止時間需保留已完成及未完成之別。截至第 步的目的類概率矩陣為
所以 :先在目的地外生存 步,再最終到指定類。對類求和得 ,正是未完成概率。這能精確檢查截止計算,毋須模擬。若把已完成概率除以其行和,則改為給定截止前完成的條件實驗。
時間與目的亦可同時保留。首步條件化給矩陣母函數
幾何離開界保證在一附近可微分。逆的導數給 ,用 得 。若 ,給定該目的類的平均時間就是 ;零概率目的地沒有此條件均值。這裏先求時間與目的地的聯合量,並非直接把它當成條件母函數;要條件化,必須再除以正的目的概率。稀有目的地與常見目的地可能需時不同,無條件均值並不能回答條件問題。
以下首例由 出發,給定目的 的均值三步,給定 為四步;加權平均 ,符合無條件均值。條件化改變路徑分佈,不能不加目的權重就沿用原鏈的普通均值公式。
例題詳解
例題 2.7.5
(兩暫態、兩目的的完整計算)
狀態次序 ,後兩者吸收,取
各行和一,各目的類只有一狀態,所以 ,此例類矩陣為 。逆及入口概率為
由 開始,完成前期望到訪 共 次,終到 的概率 。均值列 ,再乘得 ,方差為 。檢查 、目的概率各行和一、以及 ;三項驗證不同敘述,而非重複同一算術。
下面的互動圖對首個例題、賭徒破產及一條把閉類誤標為暫態的鏈,精確計算 N = (I − Q)⁻¹、B = NR 以及持續時間的均值與方差,並以另一條恆等式逐項核對。
例題 2.7.6
(閉類仍可移動)
暫態 以概率 留下, 到 , 到吸收 ;另一閉類內 確定性交替。則 ,到 的精確入口概率為 ,兩目的類概率為 ,平均入口時間二。進入 後並不留在 ,由 開始的分佈永遠交替。目的類計算未承諾 吸收,也未承諾類內普通收斂。
例題 2.7.7
(錯把陷阱留在暫態區塊)
以概率 留下,否則到吸收 ; 永留自身。若錯把兩者放入暫態區塊,, 奇異,由 的擬定完成時間無限。修正必須看結構: 是另一閉目的類。只留 暫態, 合法,且由 到 的概率為一。任意一組未指定目的的狀態,不自動全是暫態。
常見錯誤
常見錯誤
(漏計初始暫態到訪)
基本矩陣包括初始暫態到訪。省略會把 變成 ,破壞均值與代價;終端到訪屬目的地,則不計入暫態佔用。狀態次序及行分佈約定亦決定乘法方向。
常見錯誤
(先求逆再分類)
先求逆、後查互通結構,是把次序倒轉了。數值工具可能報奇異,但真正理由是仍包含閉類。
常見錯誤
(把截止前概率重新歸一化)
目的概率回答最終發生甚麼;截止前概率則用有限和 ,須保留未完成質量。把已完成的概率除以其行和,回答的是「給定已在截止前完成」這個不同問題。
總結
有限類圖找出目的地並提供共同幾何離開界;暫態矩陣冪的收斂產生基本矩陣。佔用、時間、代價及多目的入口,各由不同乘積解釋得到,閉類內運動仍須分開處理。
練習
快速檢查
(一個暫態以概率 留下, 到 , 到 。求 、目的概率、離開時間均值及方差。)
只有一個暫態時, 是純量。
解答 · 答案
,乘出口概率得 。均值 ,二階矩 ,故方差 。
快速檢查
(首例每次到 的代價為 ,終到 的額外代價為 。求兩初態的期望總值。)
用第一個例子的矩陣代入 。
解答 · 答案
暫態代價 ,終端代價 ,合共 。每次轉移前計暫態代價,入口後只計一次終端代價。
快速檢查
(第二例中,分清精確入口分佈、目的類分佈及由 開始的單時刻分佈,哪一個不收斂?)
分清鏈從何處進入,以及進入後如何移動。
解答
由 到 的精確入口為 ,到 的類入口為 。由 的單時刻分佈在 點質量間交替,沒有極限;入口概率並非此時間演化的敘述。
快速檢查
(對暫態 證明 ,並求首例由 在完成前訪問 的概率。)
在首次到訪 時使用擊中時刻馬爾可夫性。
解答
不擊中 時佔用為零;首次擊中後,由擊中時刻馬爾可夫性,包含首次在內的期望後續佔用是 。故 。因 可相除,所求為 。