動機
返回概率可以趨零,但其和仍發散,所以某時刻佔據特定狀態變得不大可能,不能判斷是否終會返回。暫態與零常返的轉移概率都趨零,但期望總到訪次數分開兩者。正常返則有另一極限結構,由週期決定哪些子序列可收斂。
本節證明逐點敘述,不把時間平均直接當成普通極限;平均零的序列仍可偶爾有尖峰。零常返情形缺少的是分析論證:馬爾可夫(Markov)算子收縮加權平方範數,迫使晚期可能取值在各狀態漸近相同;無限不變質量再迫使共同值為零。
先備的平穩判準及非週期耦合定理,已在可數常返、Kac 公式與耦合證明,其證明使用回返循環及強大數定律。以下明確指出此依賴;新趨零論證所需的加權方差及子序列事實則全部展開。不假設更新、Tauberian 或未命名的分析收斂定理。
定義
設 為可數 上不可約隨機矩陣,寫 。常返表示返回概率一;平均返回時間有限為正常返,否則零常返;返回概率小於一是暫態。不可約性使各狀態分類相同。
定義 2.8.1
(不變測度與加權平方範數)
不變測度是向量 ,各 且 ,總質量可無限。對實函數 定義
分析中只使用平方範數有限的函數;單一狀態的指示函數屬於此空間,因該狀態的不變權重有限。
定義 2.8.2
(週期與循環類)
正返回步數的最大公因數為 ,稱週期。選參考狀態 ,循環類 是可從 以模 餘 的步數到達之狀態,類索引按模 解讀。以下會證明標籤定義良好及所需性質,而不單憑記號假設。
定理/命題
定理 2.8.3
(非正常返情形的趨零)
不可約可數鏈若暫態或零常返,則
零常返敘述不需非週期。暫態時 ;零常返的返回和發散,即使每項趨零。
定理 2.8.4
(正常返週期極限)
鏈正常返,平穩概率為 、週期為 ,則各循環類有 。若 ,對 ,
整個子序列分佈甚至以全變差收斂至 上為 、外部為零的概率向量。重標循環類即可處理其他初態。
證明思路
暫態與回返循環測度
證明
(有限到訪,以及由回返循環得到的不變測度)
狀態 返回概率 時,包括零時刻的總到訪期望是 ,因至少 次到訪的概率,由擊中時刻馬爾可夫性為 。從別處開始先擊中 或永不擊中,期望次數是擊中概率乘上述有限均值。Tonelli 使期望次數等於 。非負收斂級數的項趨零,證暫態情形。
常返時固定 ,令 是首次正返回。定義 為時刻零至 到訪 的期望,則 ,各項正且有限,。正性來自返回前由 到 的簡單路徑。對 ,每次到訪都有正概率沿固定簡單路徑在另一個 以前到 ,所以次數有幾何尾界。
把循環中的期望離開改計為期望到達,初終都是 ,便證不變性。項皆非負,總質量無限時也可用 Tonelli。總質量是 ,故零常返時恰為無限。這建立分析所需的全部測度假設,不只寫一條形式不變方程。
加權平方範數引理
零常返情形建基於以下引理,先就非週期鏈陳述。
引理 2.8.5
(無限不變測度下的趨零)
設 是可數 上不可約且非週期的鏈, 是不變測度,對每個 有 ,且 。則對所有 有 。
證明
(範數收縮、方差恆等式與平坦極限)
加權 Jensen、不變性及非負求和給出
各 行和合法:絕對期望不超過二階矩平方根,而 ,故該行二階矩受全局有限平方範數除以 控制。
固定目標狀態 ,設 ,分量是零至一的轉移概率。平方範數遞減至有限極限,所以每個固定 有
差額有精確方差表達式
對概率行展開平方可證方差恆等式;平方可積與非負求和給無限版本。若 可從同一 以 步到達,和式界住其平方差的一個固定正倍數,所以取值差趨零。
非週期性使任意兩狀態都有這種共同步數。參考狀態有限多個返回步數的最大公因數已為一,串接返回路徑使返回步數對加法封閉,因此它們的非負組合包含所有足夠大整數:選一長度,對其模數各餘類取得組合代表,再加該長度的倍數。有限餘類群中非負組合也產生反元素,故所有餘類皆出現。再接上參考狀態通往 的固定路徑,所有足夠大的共同長度皆有正概率。因此每對 都有 。
選一子序列使 收斂至 ,有界性保證可取得。其他每個座標也沿此子序列趨同一 。對任意有限 ,
有限集遞增窮盡無限不變質量,故 。每個子序列的純量極限都是零,所以整個序列在每個座標趨零,不只是 Cesàro 結論。
證明透視
無限不變質量為何迫使零
證明先把不等式變成恆等式,再把恆等式變成極限;每個假設各有一個用途。
- 不變性用了兩次:在收縮 中透過 ,以及在方差恆等式中,那裏 對 不變。 有限使起始範數 有限。
- 關鍵一步是方差恆等式。範數 遞減且有下界,所以任何固定 步的範數下降都趨零;恆等式把這個趨零的下降轉化為:凡可從同一狀態以 步到達的兩個狀態, 在其上漸近相等。
- 非週期性為每對狀態提供這樣的共同步數,於是平坦性擴展至整個 。
- 無限質量只在最後使用。取值為 的平坦輪廓,在有限集 上的平方範數約為 ;它要一直不超過 ,只能 。
論證以緊緻性收結:每個子序列都有進一步的子序列具平坦極限,每個這樣的極限都是零,所以整個序列逐點趨零。這補上由平均到逐點的缺失步驟,毋須更新或 Tauberian 黑箱。
把引理用於回返循環測度,就證非週期零常返情形。無限質量這一假設不能刪去,兩狀態鏈即可說明。
反例模式
有限不變質量留下非零的平坦極限
聲稱:對任何具不變測度的不可約非週期鏈,都有 。取 , 的每個元素都是 。則 不變,總質量有限,為 ;而對 ,。證明的每一步都成立: 是常數,所以範數下降為零, 恰好平坦,。失效的是最後一步,因為 並不迫使 。所以聲稱錯誤。修正後的敘述需要 ;質量有限時,平坦極限就是平穩概率 ,此處為 ,即正常返情形的極限。
循環類消除週期障礙
證明
(循環類、質量平衡與逐類耦合)
從 到同一狀態的兩條路徑長度,其差是 倍數:接同一條返回 路徑,便成兩個返回步數。因此標籤定義良好,每步使類前進一,某條返回路徑中全部 類都會出現。 限在任一類不可約,因同類間路徑長度為 倍數;其返回步數除以 後最大公因數一,故非週期。
對任意不變測度,非負求和及一步類前進給
類只有有限多個,所以總質量無限時每類都無限。限制測度對 不變,逐類用加權範數引理。由 推至 ,先走 步,再按所得狀態平均趨零概率;概率加權可數和由有界收斂交換極限。這證所有週期的零常返趨零。
平穩概率則由同一等式得 ,限制 的平穩概率是該類上的 。先前非週期正常返耦合定理可用於此不可約非週期限制。其已展開的證明是:獨立乘積鏈有不變概率,由共同長度路徑不可約,再由已證平穩判準常返,因此幾乎必然到固定對角狀態;相遇後用相同轉移,尚未相遇的概率界住全變差。這裏引用的是已證平穩判準,不是外部更新極限定理。
由 開始, 步後在 上形成概率混合;每個混合起點在 下皆收斂至該類 ,全變差距離至多一,所以平均亦收斂。其他類在這些時刻概率為零,證明循環極限並完成兩定理。
例題詳解
例題 2.8.6
(暫態有偏遊走)
整數線最近鄰遊走向右概率 ,奇數步返回概率零,第 步為 。二項冪級數 給返回零的期望次數二,故暫態,各轉移概率趨零。整個到訪和有限,比單項趨零更強。
例題 2.8.7
(返回常返但概率仍趨零)
簡單對稱整數遊走的返回母函數為 , 增至一時發散,非負單調收斂使返回和無限,故常返。計數測度不變且無限。週期二,而 在任一奇偶類不可約非週期,計數質量亦無限,所以已證引理給轉移概率趨零。平穩遞推使座標在整條整數線仿射,不存在非零非負可和解,故沒有平穩概率。這是零常返,不是暫態。
例題 2.8.8
(狀態權重不等的週期極限)
以概率 到 、 到 ,兩者必回 。類是 、,週期二,平穩向量 。由 ,偶數時刻點質量在 ,奇數時刻在 的分佈為 ,恰是相容類平穩權重的兩倍,其他類零。乘二才能使子序列極限總質量為一。
概念視角代數
在譜中看見週期
對這個有限鏈,循環極限就是一個譜分解。矩陣 的特徵值為 ;對應 與 的右特徵向量為 和 ,左特徵向量為 和 ,並已正規化使 。因此當 時,
第二項正是兩個類之間的交替。對任何週期為 的不可約有限鏈,Perron–Frobenius 定理指出:模為一的特徵值恰為各個 次單位根,而且每個都是單重的。
常見錯誤
不變測度與不變概率須分清。證明中的無限質量導致逐點零極限,不能寫個無限分母便歸一化。
常見錯誤
(把單項趨零讀成到訪總和有限)
概率趨零不表示總到訪次數期望有限,非負發散級數的項可趨零:對稱整數遊走有 ,但返回和無限,遊走常返。暫態是關於總和的敘述,不是關於單項的敘述。
常見錯誤
(把 Cesàro 極限升格為普通極限)
Cesàro 收斂不能無額外理由推出普通極限。在上面的週期例子中, 的平均收斂至 ,各項卻在 與 之間交替。零常返情形中,加權方差證明正提供所欠的理由。
常見錯誤
(不指定餘類便取週期極限)
正常返週期鏈若不指定餘類便對 取極限,會混合不相容支集,也會遺失因子 。沿 的正確極限,在相容類上是 ,在其他地方是零。
總結
暫態趨零來自有限總到訪;零常返趨零來自不變測度收縮,以及無限質量上不可能有非零平坦有限範數極限。循環類處理週期,正常返子序列則收斂至相容類內正規化平穩概率。
練習
快速檢查
(暫態狀態返回概率 ,從 擊中它的概率 。求從 期望總到訪,並解釋轉移概率趨零。)
先計算由該狀態本身出發的到訪次數。
解答 · 答案
由該狀態開始的平均次數 ,乘擊中概率得 。它等於非負轉移概率和,有限故每項趨零。
快速檢查
(確定性三狀態有向環,求平穩概率及由固定狀態出發的三個餘類極限。)
每個循環類都只有一個狀態。
解答
平穩分佈 ,週期三。模三餘零、一、二的時刻,分佈分別是對應後繼環狀態的點質量,等於各單點循環類平穩權重的三倍。
快速檢查
(無限測度各分量正且有限,某序列平方範數至多 ,沿子序列所有座標趨同一 ,證 。總質量有限時有何不同?)
先在有限集上處理。
解答
每個有限 由有限和收斂得 ,窮盡使 任意大,故 。總質量有限時,非零常數也有有限平方範數,此界不能迫使其為零。
快速檢查
(用對稱整數遊走及返回母函數,解釋逐點轉移極限零為何不蘊含暫態。)
令 增至一。
解答
在 發散,所以期望返回次數無限而常返;無限測度論證仍使各轉移概率趨零。級數總和與單項極限回答不同問題。