動機
有限不可約馬爾可夫(Markov)鏈總有平穩概率分佈。同一句話放在可數無限狀態空間卻不成立。概率質量可以向任意遙遠的狀態漂移,不變權重的總和也可能無窮。甚至一條以概率一回到起點的鏈,其平均回返時間仍可以無窮。
無限最近鄰遊走把這些分別具體呈現出來。我們先使用上一節已證的有限邊界計算,再說明極限事件為何正確。回返循環則把路徑行為與平穩平衡聯繫起來。這些計算的價值,正是在於清楚展示有限狀態結論需要哪些新假設才能延伸。
定義
定義 7.1.1
(擊中時間與回返時間)
設 是可數狀態空間 上的時齊馬爾可夫鏈,轉移概率為 ,並已指定初始狀態或分佈。以 表示 時的概率與期望。狀態 的擊中時間為 ,正回返時間為 。空集合的下確界約定為無窮。
定義 7.1.2
(常返、暫留與平穩概率)
若 ,稱 為常返;若此概率小於一,稱為暫留。常返狀態在 時稱為正常返,在期望無窮時稱為零常返。這些定義把「會否回來」與「多久回來」分開。平穩概率序列 必須同時滿足 及 。不能歸一化的非負不變權重並不是平穩概率。
在 上的最近鄰遊走,每一步以概率 向右走一,以概率 向左走一,並獨立於過去步伐。空間平移使所有狀態有相同回返行為。狀態可數只容許逐項求和,並不保證和有限。
主要結果
定理 7.1.3
(在無限整數線上擊中較低水平)
對從整數 出發的最近鄰遊走,
若 ,則 。公平情形 的擊中概率為一,但 。
定理 7.1.4
(回返概率與總到訪次數)
對從 出發的可數馬爾可夫鏈,設 ,,包括初始到訪。則
若 ,期望為 ,且 幾乎必然有限。若 ,則幾乎必然到訪無窮次,期望也無窮。
定理 7.1.5
(有限平均回返循環建立平穩分佈)
設 , 幾乎必然成立,且 。定義
則 是平穩概率,而且 。這個構造需要有限平均回返,並非只要求終究以概率一回來。
以下直接證明這一方向。一般不可約可數鏈的逆向及唯一性定理不包括在此證明內。對反射遊走,我們會直接推導全部平穩候選,並明確分類每個參數情形。
證明或證明思路
賭徒破產事件的極限
證明
(賭徒破產事件取極限)
固定 。有限區間計算給出先到零而非 的概率:
隨 增加,事件 遞增。它們的聯集恰好是 :若一條路徑在有限時間擊中零,在此之前的最大位置也有限,所以選足夠高的上邊界,路徑不會先到達它。由概率的下連續性便可取極限。當 ,極限為 ;當 ,把分子分母除以 ,極限為一;公平公式也趨向一。
公平遊走的有限吸收時間 平均為 。此時間不超過 ,故每個 都有 。讓 趨向無窮便證明平均無窮,即使擊中本身幾乎必然發生。
當 ,設 。每步期望增量為 ,而事件 只取決於首 步,故
停止後的位置非負,因此 。單調收斂推出 。現在,停止之前所有增量的絕對值總和不超過可積變量 ,所以可以交換期望與這個和,得到 ,證得精確平均。此論證避免在尚未證明前就假定隨機停時平均有限。
每次回返重新開始同一個實驗
證明
(每次回返時重新開始)
每次有限回到 後,再回來一次的概率仍是 。這是停時上的強馬爾可夫性。在離散時間,可把停時等於 的各事件分開,逐一用普通馬爾可夫性,再對 相加而得到。歸納便有上述到訪次數尾概率。尾和公式給出 。另一方面,對非負到訪指示變量用托內利(Tonelli)定理,得 。這是同一數量的兩種表示。
若 ,任意固定有限次回返都以概率一發生。把這些可數個概率一事件取交集,便得到無窮次回返。但這仍未交代回返間隔的平均長短。
循環佔用為何滿足流量平衡
證明
(循環佔用平衡流量)
由托內利定理,;而 ,因為循環包括起始狀態,卻不包括最後回返。對固定 ,在每個事件 上向前一步取條件期望,得到
兩個和只差端點,而 。所有重排都涉及非負項,故合法;有限 再容許歸一化。除以 就證明平穩性及 。
證明透視
有限性究竟在哪裏使用
證明分為兩個階段,只有第二階段需要 。平衡等式 在各時刻 經由事件 使用馬爾可夫性;這些事件由 決定,所以可以在隨機和之內向前一步取條件。關鍵一步是交換端點:把循環平移一步,會去掉起始時對 的到訪,並加上最後一次到訪;因為 幾乎必然有限且 ,兩者抵消,所以等式在 亦成立。每次交換求和次序都只涉及非負項,因此即使某些權重為無窮,這一階段仍然成立。只有歸一化要除以 ,有限平均回返正是在這唯一一步使用。對公平遊走,循環幾乎必然有限,但 ,歸一化一步沒有有限的數可除。
例題
例題 7.1.6
(簡單對稱遊走是零常返)
從零出發,第一步到 或 。擊中結果及反射對稱性顯示,兩個起點都幾乎必然回到零,所以 。但從 擊中零的平均時間無窮,因此從零的回返時間,即一步加上之後時間,其平均也無窮。故每個狀態都是零常返。平均回返時間無窮並不妨礙回返概率為一。
反例模式
必定返回並不保證有平穩概率
斷言:與有限不可約情形一樣,各狀態都常返的鏈必有平穩概率。考慮 上的對稱遊走,它是常返的。平穩的 須滿足 ,即對每個 都有 ,所以 。對所有 非負迫使 ,而常數權重之和是 或 ,永不等於一。斷言不成立。修正的辦法是回返循環定理的額外假設 ,而這個遊走不滿足它。
例題 7.1.7
(向任何一方偏移的遊走都暫留)
設 。從 擊中零的概率為 ;從 則為一,因為該側漂移指向零。按第一步條件化,。若 ,對稱論證給出 。因此所有有偏遊走都滿足 ,從零開始的總到訪次數期望為 。若 ,回返概率為 ,包括初始時刻的總到訪平均為二。
例題 7.1.8
(反射邊界產生正常返鏈)
在 上,設 ;從每個正狀態,以概率 向右、概率 向左。設 ,令 。相鄰狀態的細緻平衡給出候選
它的和為一。由 ,把成對平衡相加即可證明平穩性,零點的自環也包含在內。零點的平均正回返時間為
若 ,則 ,平均回返時間為二。零點原地停留的一步也算在時刻一回返。
例題 7.1.9
(同一反射族也展示不能歸一化的情形)
零點的平穩方程給出 。每個內部狀態的平穩性表示,流量差 等於前一個流量差。初始流量差為零,因此每個平穩候選都必須滿足 。
若 ,這些權重為常數,任何非零候選都不能求得有限和。擊中結果顯示鏈常返,但平均回返無窮,所以是零常返。若 ,權重增長而不能歸一化;第一步分析給出回返概率 ,因此暫留。同一分佈族展示了正常返、零常返及暫留,並且明確保留了邊界條件。
常見錯誤
常見錯誤
(無窮次到訪不等於有限平均回返)
正常返鏈與對稱遊走都幾乎必然回來無窮次,兩者的總到訪期望也都是無窮。要區分它們,應考察兩次回返之間的時間,而非無限期間的到訪總數。
常見錯誤
(從無限擊中方程中隨意選一個解)
對 ,擊中概率 滿足 及 ()。 與 都是這組方程的解:對後者,令 ,則 ,而 。沒有無窮遠處的邊界,方程本身不會選出真正的概率;有限邊界的極限,或「擊中概率是最小非負解」這一事實,才選出 。同樣,對平穩分佈要逐一驗證非負、總質量為一及每條平衡方程。
常返也不等於時刻 的分佈收斂。整數線上的對稱遊走週期為二,而且沒有平穩概率。一般而言,即使正常返也不會消除週期性。本節沒有證明一個適用於所有可數鏈的收斂定理。
小結
有限賭徒破產結果,要在證明事件遞增至所需事件後,才成為無限擊中定理。暫留時重複回返給出幾何型到訪次數。有限平均循環則可透過歸一化佔用時間建立平穩概率。反射遊走說明,在無限空間中,常返、正常返與可歸一化平穩平衡必須分清。
習題
快速檢查
(整數線遊走有 ,從 出發。求終究擊中零的概率;再求從零出發的回返概率及總到訪零次數的期望。)
解答 · 答案
,所以從二擊中零的概率為 。從零的回返概率為 ,總到訪次數期望為 ,包括初始到訪。這三個量涉及不同起點或不同事件。
快速檢查
(向下偏移遊走有 ,從 出發。求 及 ,並解釋只解平均遞推式而沒有有限性論證為何不完整。)
解答 · 答案
因 ,擊中概率為一,。停止增量論證先證明平均有限,再支持對隨機長度的和交換期望。遞推式本身可能有其他形式解,也沒有保證候選期望真的有限。
快速檢查
(反射遊走有 。求平穩分佈、其平均狀態,以及零點的平均正回返時間。)
解答 · 答案
,故 。對等比級數求導或求尾和可得平均狀態 。回返平均為 ,也等於 。
快速檢查
(只用有限邊界結果,證明從一出發的對稱遊走之 幾乎必然有限,但平均無窮。)
解答 · 答案
對上邊界 ,有 ,遞增事件論證把此極限識別為 。同時,對每個 ,,故期望無窮,儘管時間幾乎必然有限。
快速檢查
(在一個三狀態常返類中,從第一個狀態出發,到首次正時間回返前的平均佔用權重為 。求平均回返及循環構造所得平穩分佈。另考慮可數無窮常返類,解釋總質量無窮的循環權重為何不能以此構造歸一化。)
解答 · 答案
循環佔用總和為平均回返 ,故 。起始常返狀態的座標為 。若總佔用質量無窮,除以這個量不能定義概率分佈,有限平均循環構造便不適用。但單是此構造失敗,並未證明任意可約鏈的所有可能平穩分佈結論。