馬可夫鏈
可達性與互通類(accessibility and communicating classes)
看看狀態的網路,問一個簡單的地理問題:從這裡出發,鏈究竟能抵達哪些其他狀態?又有哪些狀態能反過來抵達你?依「誰能到誰」把狀態分類,是理解一條鏈結構時你要做的第一件事。這就像把一棟建築的房間分成幾群,群內可以自由走動。
若存在某個步數 n 使 P^(n)(i, j) 大於 0 —— 也就是有一條正機率的路徑由 i 通到 j —— 則稱狀態 j 從狀態 i 可達(記作 i 到 j)。若 i 與 j 彼此都可達(i 到 j「而且」j 到 i),則稱兩狀態互通。互通是一個等價關係:每個狀態與自身互通、互通是對稱的、且可遞移地串接起來。於是它把狀態空間切分為一個個互通類 —— 在類內鏈可以來回遊走,從任一成員自由抵達任一成員。
這些類揭示了動態的骨架。若一個類一旦進入就再也離不開(沒有箭頭逃往另一類),則稱它為閉的;否則為開的或暫態的。鏈可能會在暫態類間漂流一陣子,但最終會被困在某個閉類中,並永遠住在那裡。辨認出這些類、以及哪些是閉的,便能讓你一眼看出長期的活動將發生在何處。
狀態 A、B、C 有箭頭 A 到 B、B 到 A、B 到 C、C 到 C。則 A 與 B 互通(可走 A 到 B 與 B 到 A),形成一類 {A, B};C 自成一類 {C}。{C} 是閉的(沒有箭頭離開 C),近似吸收態;{A, B} 是開的,因為 B 漏向 C。長期下來:鏈最終停在 C。
互通類把狀態分成可自由混合的群;閉類正是鏈最終停留之處。
可達可以是單向的:i 可能到得了 j,而 j 到不了 i,於是它們並不互通。互通要求往返皆有可能(兩個方向都存在正機率路徑)。
又称
另见