動機
有限不可約鏈不能一直探索新狀態;無限空間卻可以,因此有限狀態平衡定理需要替代版本。即使鏈幾乎必然返回,遠遊也可能長得令平衡概率無法存在。關鍵分別是終會返回,還是以有限的平均時間返回。
合適的分析單位,是離開一個參考狀態後完整返回的一次遠遊。記錄其中各狀態的到訪次數,再把期望次數除以期望遠遊長度,應能產生概率分佈。但遠遊長度可能期望無限,無限求和也需要理由。本節會逐一處理,而不把無限測度形式地正規化。
本節以獨立可積變量的強大數定律為先備知識,不在此證明該定律。以下則會建立本節可數鏈結論所需的其餘論證。分佈以行向量表示,時間為離散。
定義
定義 2.2.1
(返回時間、正常返與循環佔用)
設可數空間 上的隨機矩陣 不可約。固定 ,令
常返表示 ;正常返再要求 ;均值無限的常返稱零常返。
在常返不可約鏈中,由每個起點都幾乎必然擊中其他狀態。理由是常返狀態有無限次返回,每次返回都有一個固定正概率沿有限路徑到達目標;持續失敗的概率趨零。在擊中時刻使用馬爾可夫(Markov)性,可按時刻等於哪個整數分類證明。
計算一個循環,包含起始的 ,但不包含終端返回,故 。由 Tonelli 定理,總質量是 ;此定理容許交換非負和與期望,即使結果無限亦可。在常返情況,各個 本身有限:由 有一條簡單路徑以正概率在再次到訪 以前到達 ,所以返回 前到訪 的次數有幾何尾界。
定義 2.2.2
(全變差距離與非週期性)
概率向量 的全變差距離定為
非週期表示某狀態所有正返回步數的最大公因數為一;不可約性使各狀態週期相同。平穩概率滿足 。
概念視角結構
全變差就是最佳耦合
全變差也是所有耦合中最小的不一致概率:在 、 的所有配對上,。對任何耦合,。反過來,在每個對角點 放質量 ;餘下質量為 ,而兩個正規化後的剩餘部分支撐不相交,其乘積便把這些質量全放在對角線以外。下文的相遇論證只是其中一種耦合,給出的是上界。
定理/命題
定理 2.2.3
(可數平穩判準與 Kac 公式)
不可約可數鏈存在平穩概率分佈,恰好當它正常返。此分佈唯一,各分量皆正,且
參考狀態可任意選取,所以每個狀態的平均返回時間都是 。
定理 2.2.4
(佔用平均與普通收斂)
對不可約正常返可數鏈,由任意初始狀態出發,對每個 均有
若鏈亦非週期,則各 都有 。此處不宣稱任何收斂速率。
證明思路
構造並識別平穩分佈
證明
(回返循環給出平穩分佈,反之亦然)
先設 。計算返回前各狀態的期望離開次數,並用條件期望,得到
起點和終點都是 ,所以把時刻 換成 不改變淨次數。和式非負,交換均合法。除以有限總質量 ,便得平穩概率。
反過來,設平穩概率 存在。不可約性推出各 :某個正質量狀態可在有限步內到達任何狀態,且 。以 開始。「第 步是往後永不到訪 的最後一次到訪」這些事件互斥,而且各有概率 。它們的總概率不能超過一,故共同概率為零, 常返。同樣論證各狀態,再用不可約性,得由每個起點幾乎必然擊中 。
按零至第 步之間最後一次到訪 的時刻,分解 。若最後到訪在 ,貢獻是 。餘項來自完全避開 的路徑,其對所有 的總質量至多 ,其中 包括零時刻。由幾乎必然擊中及控制收斂,此量趨零。因此
對 求和得 ,故 有限,Kac 公式成立,所有平穩概率都等於循環構造。改用另一參考狀態即得其相應公式。
由循環得到時間平均
證明
(再生與強大數定律)
由擊中時刻的馬爾可夫性,從 起的相鄰回返循環獨立同分佈。長度的均值為有限的 ;到訪 的報酬均值為 ,且報酬不超過循環長度。對兩組序列使用強大數定律,第 步前完成的循環數除以 趨於 ,每個完成循環的平均報酬趨於 。
未完成循環不造成漸近誤差。若返回時刻依次為 ,強大數定律給出 ;比較相鄰正規化和式,得到 。未完成報酬不超過該循環長度,故相對於 可忽略。由另一初始狀態出發,首次擊中 幾乎必然有限,只多出有限前綴。這證明路徑佔用極限。比例介於零與一之間,故可取期望得到平均轉移概率極限。
非週期收斂的耦合證明
證明
(與平穩副本相遇)
先證一個路徑事實:不可約非週期鏈中,每對 都有 對所有足夠大的 成立。在參考狀態,有限多個正返回步數已可令最大公因數為一。它們的非負整數組合包含所有足夠大的整數:選其中一個長度 ,對模 的每個餘類選一個非負組合代表,再添加若干個 。代表存在,因這些長度的餘數在有限循環群生成整個群,非負組合也能表示反元素。接上通往參考狀態及離開它的固定路徑,即證一般 的事實。
現在獨立運行兩個副本,一個從 出發,一個以平穩分佈開始。乘積鏈的轉移概率為 ,不變概率是 。上述路徑事實保證兩座標可在同一個足夠大的步數到達指定目標,故乘積鏈不可約。已證的平穩判準使它常返,因此幾乎必然擊中固定對角狀態 。
相遇後讓兩副本使用相同的未來轉移。由擊中時刻馬爾可夫性,每個邊際仍遵循原鏈,但兩者從此相等。對任意集合 ,兩者落在 的概率差,不超過尚未相遇的概率;後者趨零。對 取上確界,便得全變差收斂。第二副本可按平穩混合取任意初態,因為乘積鏈由每個起點都幾乎必然相遇。
證明透視
每個假設用在哪裏
有限平均返回長度容許正規化及報酬強大數定律;不可約性傳播常返並保證唯一性;非週期性只用於普通收斂證明中的乘積鏈不可約性。移除非週期性,不會令循環平均或 Kac 公式失效。
不可約步驟還有一個重要細節。由常返的 重複嘗試固定路徑,必能最終到達 。若由該 出發有正概率永不到 ,則由 沿正概率簡單路徑在返回前到 ,再避開 ,便給出正概率不返回 ,與常返矛盾。因此每個狀態都幾乎必然擊中 ;改換目標重複此論證,就得到循環與耦合證明使用的整個常返類性質。
例題詳解
例題 2.2.5
(倒數後重置的鏈)
由零以概率 選非負整數 並跳至 ,之後確定性地逐步倒數至零。假設每個 ,且 。一個回返循環長 ;正狀態 恰在 時到訪一次,所以
若 ,則 ,所有 都有 。零處正自環使鏈非週期,因此全變差收斂。若重置值幾乎必然有限但均值無限,每次遠遊仍返回,卻沒有平穩概率。
例題 2.2.6
(零常返整數遊走)
整數線上的簡單對稱遊走滿足 。期望到訪級數發散,故常返。候選不變概率向量 則須滿足 ,即相鄰差為常數。整條整數線上的非負仿射序列只能是非負常數,非零時不可和。Kac 判準因此識別它為零常返。其週期亦為二;常返與非週期是不同問題。
例題 2.2.7
(有限均值不消除週期)
確定性兩狀態交替的平均返回步數都是二,平穩分佈為 。每條路徑漸近一半時間在各狀態,但由固定狀態開始,一維分佈永遠交替,全變差收斂失敗。獨立乘積鏈分成對角與非對角類,正好指出耦合證明中哪個假設失效。
常見錯誤
常見錯誤
(把無限不變向量歸一化)
總質量無限的不變向量並非概率;反過來,候選權重之和有限,也須先證明對實際鏈不變。回返循環論證在明確假設下同時提供兩點。單條相依軌跡的平均由再生性證明,並非把相鄰狀態當成獨立。
反例模式
逐點收斂不等於對起點一致收斂
收斂定理一個誘人的加強版是 。取 的倒數鏈即可推翻它,儘管該鏈不可約、非週期且正常返,並有 。從 出發時,在每個時刻 鏈都位於 ,故 ,且
由於 任意,在每個固定時刻對起點取上確界都至少是 。定理只斷言每個固定起點的收斂。在有限空間上,有限多個起點的最大值確會趨於零;但在可數空間上,一致性需要另外的控制。
耦合相遇時間也毋須期望有限;幾乎必然有限已足以證明全變差收斂。
總結
回返循環把常返問題變成正規化問題。有限平均循環等價於唯一平穩概率,其倒數給出參考狀態質量。再生報酬證明佔用平均;非週期性再容許乘積鏈耦合,把平均提升為單時刻分佈收斂。
練習
快速檢查
(倒數模型取 ,。求平穩分佈與各狀態平均返回時間。)
用 及 Kac 公式。
解答 · 答案
幾何尾為 ,,故所有 有 ,而 。零自環保證非週期。
快速檢查
(若 ,, 使總和為一。不求 ,分類倒數鏈並說明理由。)
把 與調和級數比較。
解答
平方倒數級數收斂,概率可正規化;但 ,由與調和級數比較可見。每次 幾乎必然有限,故每次返回發生但均值無限。鏈不可約且零常返,沒有平穩概率。
快速檢查
(不可約平穩鏈有 。求平均返回時間及長期到訪比例。單憑此數據可否證普通收斂?)
分清時間平均與單一時刻分佈。
解答 · 答案
Kac 公式給五步,佔用比例幾乎必然趨於 。所用普通收斂定理還要求非週期,單憑 數值不能驗證。
快速檢查
(兩個確定性交替副本從相反狀態出發,為何乘積鏈耦合失敗,即使各鏈皆正常返?)
追蹤兩個座標之差模二的值。
解答
兩座標在每步仍相反,乘積鏈無法到對角,因此可約。不能由整個乘積空間有平穩概率,就推論從非對角狀態出發的不可約常返性。缺少的非週期條件,正是先前保證乘積不可約性的條件。