動機
馬爾可夫(Markov)鏈記錄逐步變化的狀態,例如小型隊列的待處理任務數、圖上的位置,或有限狀態控制器的模式。其核心是條件獨立性:知道現在狀態後,已記錄的過去不再提供下一步的額外資訊。因此狀態必須包含足夠資訊;若控制器帶有隱藏計時器,只記錄可見模式而省略計時器,便可能失去馬爾可夫性。
長期行為有幾個不同問題:離開某狀態後會否返回?若必定返回,平均等多久?是否存在經一次轉移仍保持不變的概率分佈?常返性、正常返性及平穩性將這些問題連接起來,但不能互換。即使有限鏈有平穩分佈,從固定起點出發的分佈仍可永遠振盪。
本節由轉移矩陣及首步條件化出發,研究返回概率及有限狀態平衡,再用可數狀態的反例指出有限性的重要。全節以行向量表示分佈。
定義
定義 2.1.1
(時間齊次馬爾可夫鏈)
在有限或可數狀態空間 上,若對每個正概率的歷史都有
則 是轉移矩陣為 的時間齊次馬爾可夫鏈。各 ,且 。 步轉移矩陣為 ,故初始分佈 在第 步變為 。
對中間狀態條件化可得 。可數空間中各項非負,沒有條件收斂的抵消問題。任意隨機矩陣與初始分佈均可透過逐次抽取下一狀態構造一條鏈;等價地,其有限歷史概率為 ,彼此相容。
定義 2.1.2
(擊中、返回與互通)
對 ,令 。對單一狀態 ,首次返回為 ,空集的下確界定為 。若 ,稱 常返;否則稱暫態。常返狀態若 ,稱正常返;若期望無限,稱零常返。
若某個 使 ,稱 可由 到達。彼此可到達的狀態稱互通;所有狀態互通的鏈稱不可約。互通類若不能經一步轉移離開,稱閉類。對至少在某個時刻有正返回概率的狀態, 的週期是集合 的最大公因數。若此返回時刻集合為空,本節不賦予週期。有可能返回的不可約鏈,其狀態有相同週期;週期為一稱非週期。
定義 2.1.3
(平穩分佈)
概率行向量 若滿足 ,稱平穩分佈。由 開始,各時刻的一維分佈相同。由狀態 出發的極限分佈則要求 對各 收斂至指定概率向量,須另行證明其存在。
定理/命題
定理 2.1.4
(以期望到訪次數判斷常返性)
令 。則
因此,常返等價於返回概率級數發散,並非等價於平均返回時間無限。
定理 2.1.5
(有限不可約鏈的平衡與收斂)
有限不可約鏈有唯一平穩概率向量 ,各 ;所有狀態正常返,且 。若再假設非週期,則對所有 有 。即使有週期,平均轉移概率仍滿足
不可約是此處唯一性的充分條件,並非必要條件:可約鏈若只有一個閉的不可約類,仍可有集中於該類的唯一平穩分佈。在可數無限不可約鏈中,平穩概率分佈存在恰好等價於正常返,僅常返並不足夠。以下解釋有限情形;可數延伸另需可積性論證,此處不作完整證明。
概念視角結構
平穩性就是每個割集上的流量平衡
對概率向量 ,方程 等價於概率流在每個割集上平衡:對每個 ,
把 對 求和,再消去留在 內的流量,便得此恆等式;取 則重得第 條方程。選好割集可縮短計算:對只在相鄰整數之間移動的鏈, 與其餘狀態之間的割集直接給出 。
證明思路
兩條定理都建基於同一個工具:每次到訪固定狀態,鏈便重新開始,路徑因而分拆成互相獨立的遊程。
證明
(在返回時重新開始以計算到訪次數)
每次返回 ,鏈都可從 重新開始。擊中時刻的馬爾可夫性可將「該時刻等於整數 」的事件逐一分開,再用普通馬爾可夫性證明。因此,包括零時刻在內,至少到訪 次的概率為 。尾和為 ;當 時它等於 ,當 時為 。另一方面,單調收斂定理允許交換非負到訪和與期望,得到第一定理的概率級數。
證明
(回返循環、最大值原理與收縮)
正常返。 有限不可約鏈中,固定目標 。每個狀態都有一條正概率路徑通往 。狀態有限,故可選共同路徑長上界 ,以及各路徑概率的共同正下界 。尚未擊中時,往後 步內擊中的條件概率至少為 ,所以擊中時間尾部按長度 的區段受幾何級數控制。首步後同樣論證,便得 。有限性正用於取得共同正下界。
存在性。 在兩次到訪 之間,計算各狀態 的期望到訪次數,再除以 ,得到概率向量 。一個回返循環的起點與終點都是 ,因此各狀態的期望流入等於期望流出,得 。終端返回以前恰好到訪 一次,故 。
唯一性與正性。 若 ,在 取最大值的狀態,只能轉往同樣取最大值的狀態。不可約性將此值傳遍所有狀態,所以 的右零空間只包含常數向量。有限維矩陣的行秩等於列秩,故左零空間也是一維;歸一化後平穩向量唯一。某個正分量可沿正概率路徑到達任何狀態,由平穩性可知所有分量皆正。從任何其他狀態 重做回返循環構造,得到第 個分量為 的平穩向量;由唯一性它就是 ,所以對每個 都有 。
收斂。 有限不可約非週期鏈存在某個 ,使 各分量皆正。理由是返回路徑長的最大公因數為一,串接路徑可形成所有足夠大的長度,再接上狀態間的路徑。令 、。每行均包含共同質量 乘均勻分佈;移除共同部分,便知乘以 將兩個概率分佈的全變差距離縮小至至多 倍。重複後趨於 ,其餘步數不增加距離。有週期時,隨機矩陣的冪仍有界;Cesàro 平均消去單位圓上除 外的特徵值,而單特徵值 給出同一平穩極限。這證明平均收斂,並未宣稱普通收斂。
證明透視
有限性、不可約性與非週期性在哪裏用到
平衡定理的證明分四部分,每個假設都在可辨認的步驟中使用。
- 有限性用於共同界 與 ,由此得 。沒有它,每個狀態仍可到達 ,等待時間卻可能有無限均值,常見錯誤一節的對稱遊走正是如此。它亦再用於秩相等,以及在 有限時得到 。
- 不可約性用了三次:從每個狀態到達 、把調和函數 的最大值傳遍各狀態,以及使 的每個分量為正。
- 非週期性只在最後一部分使用,用來找到嚴格正的冪 。沒有它,只剩 Cesàro 平均的結論。
關鍵一步是回返循環構造。由 回到 的循環起點與終點相同,所以各狀態的期望流入與期望流出相抵, 是由計數而非解方程得到的。除以 需要 ,所以要先證明正常返。論證以唯一性收結:從每個狀態構造的循環向量都是同一個 ,於是單一狀態的 變成對所有狀態成立的 。
擊中概率為何選最小解
首步方程毋須預先假設最終擊中,而構造本身就指出哪一個解才是擊中概率。
命題 2.1.6
(擊中概率是最小解)
設 ,。則對 有 ,對 有 。若 滿足同樣的方程,則對每個 都有 。
證明
(有限時域遞增至擊中概率)
令 為截至第 步已到達 的概率,包括零時刻,故 。在 上保持為一,在外部則更新為
事件隨時域遞增,所以概率遞增至最終擊中概率;在非負和式取極限便得調和方程。若 是另一個非負解且邊界值為一,歸納給出各時域均有 ,故極限 。這證明最小性,並非任意加給代數系統的規則。
最小性並非技術細節:在無限空間中,單靠方程可以有許多解。
反例模式
單靠邊界值不能決定擊中概率
聲稱:擊中概率是首步方程在 上取一、取值於 的唯一解。考慮非負整數上每步由 移至 的確定性鏈,並取 。從正整數出發永不到零,故該處的擊中概率為零。然而對每個常數 ,令 、對 令 ,則對 有 ,這正是首步方程。所以有界方程組有無限多解。修正後的敘述就是上述命題:擊中概率是最小非負解,這裏即 ,而有限時域構造正選出它。
期望擊中時間也可安全地由有限時域生存概率相加:,容許值為無限。因此代數求出的均值候選,仍須用尾界或其他理由驗證有限性。無限空間中,各狀態都有路徑通往目標,並不提供等待時間的共同上界,尤其要小心。
例題詳解
例題 2.1.7
(兩個模式的真正極限分佈)
設
平穩方程給出 ,故 。兩狀態互通且各有自環,因此非週期。令 ,則 ,故 。這直接證明任意初始分佈均收斂。返回狀態 的平均時間是 步;一步自環也算返回,所以平均可以小於二。
例題 2.1.8
(有平穩分佈卻不收斂)
確定性交替鏈的矩陣是 ,平穩分佈為 。從狀態 出發,偶數時刻在狀態 的概率為 ,奇數時刻為 ,故沒有普通極限,週期為 。時間平均概率卻趨於 。若以平穩分佈開始,各時刻邊際概率都是 ,但相鄰狀態仍高度依賴。
例題 2.1.9
(首步方程與可約鏈的唯一平衡)
在 上令 吸收;由 或 以概率 到 ,以概率 到另一非零狀態。對 ,首步條件化給出
所以 。 時有 ,獨立驗證期望有限。非零狀態的平穩方程是 、,迫使兩者為零。因此可約鏈仍有唯一平穩分佈 。非零狀態暫態;吸收狀態正常返,返回時間為一。
常見錯誤
常見錯誤
(把均值方程當作均值有限的證明)
在 外寫下 ,並不證明 有限:若均值無限,方程只以空洞的 形式成立。尾界才補上所欠的理由,例如第三個例題中的 。
常見錯誤
(把平穩分佈讀成極限分佈)
存在滿足 的 ,並不表示從固定起點出發會收斂。交替鏈有 ,但 在 與 之間交替。普通收斂除有限不可約外還需要非週期性。
在可數無限空間中,有限定理的另一個假設會悄然失效,下例顯示失去的是甚麼。
反例模式
單有常返不足以給出平穩概率
聲稱:不可約常返鏈必有平穩概率分佈。取整數上的簡單對稱隨機遊走。它常返:,級數發散,所以第一定理給出 。它保持計數測度,這是總質量無限的不變測度。但平穩性要求 ,所以 是 的仿射函數;整條整數線上非負、非零的仿射序列不可能可和。因此沒有平穩概率,遊走是零常返。修正後的敘述要求正常返:不可約鏈有平穩概率恰好等價於正常返,而有限性保證了這一點。
總結
轉移矩陣冪描述有限時刻分佈,首步方程描述擊中問題,回返循環解釋平衡。有限不可約性保證正常返及唯一正平穩分佈;非週期性再保證從各起點出發的收斂。無限鏈還須檢查可和性及返回時間有限性,調和方程則須配合最小解條件。
練習
快速檢查
(求 的平穩分佈與平均返回時間。由各起點出發是否收斂?)
用兩個狀態之間的平衡方程。
解答 · 答案
平衡給出 ,故 ,平均返回時間為 及 。交叉轉移皆正,所以不可約;對角皆正,所以非週期,從而收斂。
快速檢查
(狀態 、 吸收;由 、 各以概率 移向相鄰整數。求由各內部狀態出發先到 而非 的概率,以及期望吸收時間。)
寫出首步方程,再檢查有限性。
解答
設 。由 、 得 。均值滿足 、、,故 。任一內部狀態下一步吸收的概率都是 ,生存尾為 ,故均值確實有限。
快速檢查
(給出有多個平穩分佈的可約鏈,列出全部平穩分佈,並解釋為何不違反不可約定理。)
兩個吸收狀態便足夠。
解答 · 答案
兩狀態上取 。兩者皆吸收,每個 ,,都是平穩分佈。它們不互通,不符合定理的不可約假設。
快速檢查
(若狀態的首次返回概率 ,求包括零時刻在內的期望總到訪次數,以及至少到訪三次的概率。)
每次返回都是成功概率為 的新試驗。
解答
期望總次數為 。至少三次到訪需要兩次成功返回,概率為 。此狀態仍屬暫態;期望總到訪有限,完全可以同時有不小的多次返回概率。