上頁　1│2│3│4│5　次頁

馬可夫鏈的簡介 （第 4 頁）

姜祖恕

 

首頁 | 搜尋

．原載於數學傳播第九卷第三期
．作者當時任職於中研院數學所
•對外搜尋關鍵字
 
四、各種狀態的分類──馬可夫鏈中基本的定理

定義2：
兩個狀態 x,y 中，我們說從 x 可以到達 y 如果 $P_x(T_y < \infty)>0$。

這個定義是說從 x 開始，若有可能在有限的時間到達 y 的話，就叫做從 x 可以到達 y。 我們用符號 $x \rightarrow y$ 表示。顯然的 $x \rightarrow y$ 和 $\sum^{\infty} _{n=1}P^n(x,y)>0$ 是等價的。

在數學的工作中一件最基本也是最重要之一的就是把看似複雜的研究對象加以分類，並藉由此分類加強對現象的了解。在看似雜亂無章的馬可夫鏈中我們如何分類呢？ 以下我們就要討論對某一特定的馬可夫鏈之狀態空間加以分類。我們先做以下之定義：

定義3：
一個狀態 y 稱之為輪迴的，如果 $P_y(T_y < \infty)=1$。 若 $P_y(T_y < \infty)<1$，則此狀態就叫做短暫的。

按照以上之定義，我們知道若一個馬可夫鏈從一個輪迴狀態 y 開始，那麼它遲早會再回到 y， 但從一個短暫狀態開始則它有可能永遠不會再回到自己！有了以上的概念後， 我們很自然的會想到「幾次」的概念；也就是說我們會想知道回到 y 究竟會有幾次！ 我們用符號 N(y) 來表示。若用嚴格的數學符號表示，則

\begin{displaymath} N(y)=\left\{ n \geq 1, X_n=y \right\} \end{displaymath}

下面這個定理描述了輪迴與短暫這兩種不同狀態完全不同的性質。

定理2：
  1. 設 y 為短暫狀態。則 $P_x(N_y < \infty)=1$。
  2. 設 y 為輪迴狀態。則 $P_y(N_y = \infty)=1$。

這個定理描述了兩種不同狀態的完全不同之處。若從一個輪迴狀態 y 開始， 則這個馬可夫鏈再回到自己的次數一定是無窮多次，但不論從何狀態開始，跑到了一個短暫 的次數一定是有限的。事實上這很容易想像，因為若從一個輪迴狀態開始，則它一定會回到自己， 但一回到自己，用馬可夫鏈的定義，它又相當於從自己開始，所以又會再回來， 反覆如此當然$N_y=\infty$了！對於短暫態我們也可以類似的推論，不過請讀者自己揣摩。 若想做更精細一點的估計我們可以考慮對到達一個短暫狀態的平均次數。 令G(x,y)表示從x開始而到達y的平均次數，則

\begin{displaymath} G(x,y)= \left\{ \begin{array}{l} P_x(T_y < \infty) \\ 1-P_y(T_y< \infty) \end{array}\right. \end{displaymath}

不過這件事實我們現在不去理會它的證明，以後也不會用到，僅僅作為參考而已。

簡單了解兩種不同的狀態後，我們可以準備談分類的問題了！首先，我們在狀態中定義一種等價的關係。

定理3：
對於兩個不同的狀態x及y，我們說x及y是等價的，如果 $P_x(T_y < \infty)=P_y(T_x < \infty)=1$。

換句話說，x和y是等價的意思就是從x開始，遲早會到達y的，反之亦然。 這個定義看似要求很多，但由下面這個定理就知道事實上不難：

定理4：
設 x 為輪迴狀態。則 x 和 y 等價若且唯若 y 也是輪迴狀態同時 $x \rightarrow y$。

至於這個定理的證明我們就不去深究了！但這個定理大大簡化了證明 x 和 y 是等價的條件。第一：一個輪迴狀態絕對不會和一個短暫狀態等價。第二：兩個輪迴狀態之是否等價端視 $P_x(T_y < \infty)$ 是否大於 0 而定。我們不再需要考慮 $P_x(T_y < \infty)$ 是否為 1 了！

定理5：
一個狀態空間的子集合 C 稱為封閉的如果 $P(x,y)=0 \forall x \in C, y \not\in C$。如果 $x \rightarrow y \forall x,y \in C$，則稱 C 為不可約的。

有了以上這些定義，我們現在可以對狀態空間做一個最簡單粗淺的分類：以 SR 表示輪迴狀態所成的集合，以 ST 表示短暫狀態的集合。

定理6：
狀態空間 S 可寫成 $S=S_R \cup S_T$，而 SR 可寫成有限或無限多個彼此分離的封閉不可約集合。

這個定理告訴我們一個馬可夫鏈的行為。倘若我們從某一個封閉不可分的集合中的一個輪迴狀態開始，則馬可夫鏈永遠停留在此一集合中，同時會到達此集合中任何一個狀態無窮多次。 若從某一短暫狀態開始，則此馬可夫鏈可能永遠停留在 ST 中也可能跑到某一個封閉不可約的集合中而陷於其中永遠出不來了！

這個定理的證明非常容易，僅僅用定義四把所有輪迴狀態與其等價的歸成一個集合， 然後用定理3證明其為一封閉不可約的集合即可，大概三言兩語就可把這個定理證明出來了！

有了這些簡單的分類後，我們再回頭看看以前的例子，試試能否用這些術語更清楚的描述一下問題的性質。 我們首先看衍生鏈：我們可想像狀態空間 $S= \{ 0,1,2,\cdots \cdots \}$，這個模型最重要的目的當然是決定在這個模型下， 細胞會不會一定絕種，也就是說 $P_1(T_{ \{0\} } < \infty)$ 是否為 1？（此處 p1 表示第 0 代的細胞數為 1。） 若 $P_1(T_{ \{0\} } < \infty)=1$，則表示這種細胞分裂方式最後會導致細胞絕種而 $P_1(T_{ \{0\} } < \infty) < 1$ 則表示不一定會絕種，若我們假設第 0 代有 n 個細胞，討論的方式和第 0 代只有一個細胞完全一樣， 因為 $P_n(T_{ \{0\} } < \infty) = P^n_1(T_{ \{0\} } < \infty)$。 在這個例子中，0 是很特殊的狀態，首先，因為 P(0,0)=1，所以 0 是一個輪迴狀態。其次因為所有的 k > 0， $P_k(T_{ \{0\} } < \infty) > 0$（除了在最極端且無意義的情況下，所以除了 0 以外任何一狀態皆為短暫的(定理3)）這個問題現在變成了從一個短暫狀態開始， 到底是不是一定會碰到 0？如果答案是肯定的，則此細胞最後會歸於無有， 但如果是否定的，則為除了 0 以外全是短暫狀態，所以最後細胞個數可能會趨近無窮大。 這是個很有趣的現象，可以稱為二一律，不是 0 就是 $\infty$，限於篇幅， 我們不解這個問題了，但這個問題的答案我們述之如下：如果 a 表示平均一個細胞所分裂的個數， 則 $P_1(T_{ \{0\} } < \infty)=1$ 如果 a < 1，反之若 a>1， 則 $P_1(T_{ \{0\} } < \infty) < 1$。也就是說如果一個細胞平均有超過一個以上的後代， 則有可能細胞數會趨近 $\infty$，反之若一個細胞平均有不及一個的後代，則一定會絕種。證明這件事不容易但看起來這個答案倒是頗為合理的。

我們再看看例一。不過我們假設 Xn 可取負值，表示賭徒負債的情況。在這樣的情形下，狀態空間 $S = \{ \cdots -n,-n+1 \cdots -1,0,1,2,\cdots n, \cdots \}$ 為所有的整數。 為了使情況簡化，我們假設 P(x,x+1)=P(x,x-1) $={\frac{1}{2}}$。很顯然的， 所有的 $x,y,P_x(T_y < \infty)>0$，所以 S 整個是一個封閉不可約的集合。 問題是 0 是短暫狀態亦或是輪迴狀態？若 0 是短暫的，則所有的狀態皆是短暫的， 若 0 是輪迴的，則所有的狀態皆是輪迴的(定理3)。這個例子又稱為隨機漫步， 因為我們可以想像一個人站在一條直線上，有一半的機會他會向左跨一步，也有一半的機會他會向右跨一步。 我們想知道這個人最後會去那裡？是 +$\infty$ 或 -$\infty$？還是留在線上左右搖擺不定？ 同樣的道理我們可以考慮一個人站在平面上的格子點上，每次他可以向前， 後，左，右，各以 $\frac{1}{4}$ 的機會移動一步。甚至在更高的 3 維、4 維……以上的空間格子點， 向他的鄰近各點以相同的機率移動，問題是這個人最後會去那裡？ 無論這個人是站在幾維的空間中，他從任一點開始，任何一點都有可能到達，所以所有的狀態或皆為短暫的或皆為輪迴的。 最簡單的問題就是 0（原點）究竟是短暫的或是輪迴的？這個問題的答案是在一、二維時， 原點是輪迴的但在三維以上的空間時，則原點是短暫的。讀者也許會奇怪為什麼會有如此奇怪的答案， 事實上這和數學分析中的很多結果有密切的關係，希望有興趣的讀者自己去討論這個問題， 我們會發現到數學中很多出發點完全不同的領域卻有完全相似的結果。 回到隨機漫步中去看看這樣的結果究竟是什麼意思呢？ 在一、二維中，隨機漫步的人是左右搖擺不定的，忽左忽右，忽上忽下，每一個格子點他都得去， 同時得去無窮多次。但在三維或更高的空間中，隨機漫步的人會愈來愈遠離原點，最後會跑到無窮遠去（雖然不沿著固定的方向）。

了解以上這些概念後，我們可說對馬可夫鏈的分類有了粗略的認識。但對於定理2， 這樣一個「粗」的結果數學家是不會滿意的！為什麼說它「粗」呢？因為就一個輪迴狀態來說，定理2只告訴了我們 $N_y=\infty$，也就是到達 y 的次數是無窮多次，但我們不知道何時到達， 或是隔多久才會到達一次，對嗎？所以雖然似乎定理2已經告訴我們不少消息， 但多事的數學家追著問這個問題：到底要隔多久一個馬可夫鏈從一個狀態才會回到自己去？ 也多虧了這個問題，我們對分類的問題才會有以下更精細的分類。

定義4：
一個輪迴狀態稱為真輪迴，如果平均回到自己的時間是有限的，否則稱之為虛輪迴。

注意以上這個「平均時間」的問題只適用於輪迴狀態，因為對於短暫狀態顯然平均回到自己的時間是$\infty$， 如果一個輪迴狀態 y 是虛的，則表示從 y 開始，雖然一定會再回到 y， 但平均起來要等無窮大的時間，所以我們以虛輪迴稱之。若令 m，表示從 y 開始， 平均要回到y的時間，則我們有以下的定理：

定理7：
設 C 為一封閉不可約同時由輪迴狀態所構成之集合且 $P(X_0 \in C)=1$ 則

\begin{displaymath} \lim_{n \rightarrow \infty} \frac{N^{(y)}_n}{n}= \frac{1}{m_y} \end{displaymath}

此處 N(y)n 表示一個馬可夫鏈在時間 n 以前到達 y 的次數， 這個定理的意思是說如果一個馬可夫鏈從和一個輪迴狀態 y 等價的狀態開始， 則平均到達 y 的次數是 $\frac{1}{m_y}$。若 $m_y=\infty$ 則 $\frac{N_n(y)}{n} \rightarrow 0$， 表示在這個馬可夫鏈的用動過程幾乎看不到 y。所以再這個意義下， 一個虛輪迴狀態和一個短暫狀態是有類似的性質。我們不難想像如果要考慮馬可夫鏈的極限行為（也就是當 n 很大時）時， 只有實輪迴狀態有作用，其餘的皆可以忽略！不過我們限於篇幅的關係不再繼續深究怎麼樣可以忽略其餘的狀態了。

   

上頁　1│2│3│4│5　次頁

 回頁首
 
（若有指正、疑問……，可以在此 留言 或 寫信 給我們。）
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯：吳俊融 ／ 校對：黃怡碧 ／ 繪圖：黃照洋 最後修改日期：5/31/2002