Markov Chain

Markov Processes

不管是 discrete(

$X(t),t=0,1,2,\cdots$) or continuous parameter time(

$X(t),t>0$) 的 Stochastic Process，只要滿足以下式子，即可稱為一個 Markov Process：

$$P(X(t_n)\le x_n|X(t_1)=x_1,...,X(t_{n-1})=x_{n-1})=P(X(t_n)\le x_n|X(t_{n-1})=x_{n-1})$$

a Stochastic Process is best defined as a family of random variables,

$\{X(t),t\in T\}$, defined over some index set or parameter space

$T$. The set

$T$ is sometimes also called the time range, and

$X(t)$ denotes the state of the process at time t.

在日後的課程中我們會學到 Birth-Death Processes，而 Birth-Death Process 即具有 Markovian property，也就是滿足上式的定義。

而這個學期我們會學到的大部分 Queue 都是以 Birth-Death Process 為基礎，故在 Queueing Theory 中，我們可以使用 discrete-time Markov Chain 或者 continuous-time Markov Process 來分析 各種 Queue 的 long term behavior。

Long-tern Behavior of Markov Chain

定義名詞

以下說明不會著重在詳細數學證明，而是僅在邏輯層面上做整理，釐清各個 distribution （長期來說）的關係。

對 Markov Chian 來說，觀察 long-term behavior 有三種，第一是 stationary distribution，第二是 limiting distribution，第三是 ergodicity。

首先定義 Communicating Classes，我們說 state i & j communicate 代表雙方都一定可以經過 state transition 到達對方的 state，而若整個 Markov Chain 的 state 都互相 communicate，我們說這個 Markov Chain 是 irreducible。

接著定義 Recurrence & Transience，Recurrence & Transience 代表一個 state 回到自己的可能性。定義如下:

let

$f_{jj}=\sum _{n=1}^{\mathrm{\infty }}{f}_{jj}^n$, where

$f_{jj}^n$ 代表從 state j 開始經過 n 個 transitions 回到 state j 的機率。若

$f_{jj}=1$，我們說 j 是 recurrent state，若

$j_{jj}<1$，我們說 j 是 transient state。

transient 簡單來說就是對 state j 而言，長期來說，從 state j 跑去別的 state 然後不回來是必然，Markov Chain 在跑的過程中經過 state j 的次數的期望值會是 finite。

反之 recurrent 代表長久來看是一定會回來的，經過 state j 的次數的期望值會是 infinite。

當 state i 的

$f_{jj}=1$(recurrent state)，即可定義

$m_{jj}=\sum _{n=1}^{\mathrm{\infty }}n{f}_{jj}^n$，

$m_{jj}$代表state j 回到自己的平均 transitions 數，也稱為 mean recurrence time。

若

$m_{jj}<\mathrm{\infty }$，我們說state j 為 positive recurrent，也就是我們會在一定數量的 transitions 內回到自己。若

$m_{jj}=\mathrm{\infty }$，我們說 state j 為 null recurrent，代表有機率回到自己這個 state，但是不知道需要多久。

而 period 為從state j 開始回到自己的 transition 數(可能有很多個)的最大公因數(GCD)，若為1 稱為 aperiodic，反之稱為 periodic。

我們說一組互相 communicate 的 state 為一個 Communicating Class，若這個Communicating Class 中的 state 都無法到達任何外界的 state（也就是說繞來繞去都在這個 Communicating Class 中），稱為 closed Communicating Class，反之稱為 open。

若將這個 closed 概念類比到一個 state，則稱這個state 為 absorbing state，代表一旦 Markov Chain 進入這個state，就無法再出來了。（從 state diagram 來看，一個簡單的例子就是只有一個單向箭頭進入的 node）

一個 Markov Chain 可能會具有多個 Communicating Class，每個 class 中的 state 都互相communicate，但是不和其他 class communicate，而同一個 Communicating Class 當中的 state 以下幾項性質都會相同: period, transient / null recurrent / positive recurrent。

因為同個 Communicating Class 中的 state 會有相同性質，所以我們藉由觀察其中一個 state，看這個 state 是否為 positive recurrent 還是 null recurrent 或 transient，就知道整個 Communicating Class 具有怎樣的性質。

Stationary Distribution

當一個 Communicating Class 是 positive recurrent，就有 unique 的 stationary probability distribution：

$$\pi =({\pi }_1,{\pi }_2,{\pi }_3,...,{\pi }_n)=(\frac{1}{{\mu }_1},\frac{1}{{\mu }_2},...,\frac{1}{{\mu }_n})$$

其中

${\mu }_i$ 為 state i 的 expected return time。

若整個 Markov Chain 為 irreuducible，代表只有一個 Communicating Class，也就是說這個 Markov Chain具有唯一解的 Stationary Distribution。

若 Communicating Class 為 null recurrent 或者 transient，則沒有 stationary distribution。

我們說一個 process 是 stationary 代表 independent of time，但是若將 initial state（Markov Chain 的起始點）對 long-term behavior 的影響考慮進來，就是以下要介紹的limiting distribution。

補充：

下面定理可以幫助我們在已知為 irreducible, aperiodic 時判斷一個 Markov Chain 是否為 positive recurrent:

若一個 Markov Chain 為 irreducible, aperiodic，若存在一個 nonnegative solution 滿足

$\sum _{j=0}^{\mathrm{\infty }}{p}_{ij}{x}_j\le x_i-1(i\ne 0)$ such that

$\sum _{j=0}^{\mathrm{\infty }}{P}_{0j}{x}_j<\mathrm{\infty }$，則這個 Markov Chain 為 positive recurrent。

Limiting Distribution

當一個 Communicating Class 為 positive recurrent 且 aperiodic，我們說 limiting distribution exists，且會和 stationary distribution 相等。

代表 initial state 的影響 in the long run 來看已不存在，顯示了 lack of memory 的性質。

將沒有影響這件事寫成數學式：

$\underset{m\to \mathrm{\infty }}{lim}{P}_{ij}^m={\pi }_j$，代表 in the long run，此 process 會在 state j 的機率，這個機率和 starting state i 沒有關係。矩陣

$P$ 可寫成如下:

$$P=\left[\begin{array}{ccccc}{\pi }_0& {\pi }_1& {\pi }_2& \dots & {\pi }_n\\ {\pi }_0& {\pi }_1& {\pi }_2& \dots & {\pi }_n\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ {\pi }_0& {\pi }_1& {\pi }_2& \dots & {\pi }_n\end{array}\right]$$

where

${\pi }_j=\frac{1}{{\mu }_j}$

若為 null recurrent 或 transient，則

$\underset{m\to \mathrm{\infty }}{lim}{P}_{ij}^m=0$

若一個 Markov Chain 有多個 Communicating Class，

$P$ 的每個橫軸(index

$i$)就對應state

$i$ 所在的Communicating Class 的 limiting distribution。

Ergodicity

Limiting distribution 觀察的是 state 在很久以後的一個時間點 n 的表現，而 Ergodicity 觀察的是在一段很長的時間裡面，state 的平均表現怎麼樣。

我們說一個 process 具有 Ergodicity ，代表對於所有 moment，都具有 Time Average = Ensemble Average 這個性質，也就是

$${\int }_0^T\frac{(X_0(t){)}^n}{T}dt=E[X(t{)}^n],foralln$$

代表這個 process 的 moments are independent of time（但是不一定和 initial state 無關）。也代表 process 的 moments 都有極限（finite）。

當具有 ergodicity ，就具有以下性質，定義

$V_j(n)=$ total number of visits to state j up to time n，給定一個 irreducible 的 Markov Chain：

若為 positive recurrent & irreducible 則

$\frac{V_j(n)}{n}=\frac{1}{{\mu }_j}$（almost surely）

若為 null recurrent 或者 transient 則

$\frac{V_j(n)}{n}=0$ （almost surely）

總結

當一個 Markov Chain 是 irreducible 且 positive recurrent 時就會有 stationary distribution，如果今天再加上 all moments are finite 這個條件，就會是 ergodic，如果再加上是 aperiodic 就會具有 limiting distribution。

所以說，stationary, ergodic, limiting distribution 這三個條件的強度（需要的條件數量）為：limiting distribution > ergodic > stationary。

我們可以根據上述的定理以及性質，判斷 Markov Chain 具有哪些性質（irreducible / positive recurrent, …），即可知道 Limiting Distribution / stationary distribution 等等存不存在，接著即可用

$\pi =\pi P,\pi Q=0,\pi e=1$ 來求解（看是 discrete / continuous）。

在本課程中探討的 Markovian Queue 幾乎都會是有解的（要不然你們就沒辦法算

$L,W,...$，考試就不用考了），不過了解上述分析，對於日後若研究有要用到 Markovian Queue 相關分析時會有幫助。

Discrete-time Markov Chain

若說

$\{X_n\}$若滿足：

$$P(X(t_n)=x_n|X(t_1)=x_1,...,X(t_{n-1})=x_{n-1})=P(X(t_n)=x_n|X(t_{n-1})=x_{n-1})$$

我們稱之為一個 discrete Markov Chain，

$X(t_i)=k$ 為此 Markov Chain 在

$t=i$ 時的 state（

$k$）。

$p_{ij}$ 為從 state

$i$ 跳到 state

$j$ 的機率（transition probability）：

$$p_{ij}=Pr(X_{n+1}=j|X_n=i)$$

假設一個 Markov Chain 的 state space

$S=\{1,2,\cdots ,n\}$，將所有 transition probability 結合起來可以寫成一個矩陣

$P$(transition probability matrix)：

$$P=\left[\begin{array}{ccccc}{p}_{11}& p_{12}& p_{13}& \dots & p_{1n}\\ p_{21}& p_{22}& p_{23}& \dots & p_{2n}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ p_{n1}& p_{n2}& p_{n3}& \dots & p_{nn}\end{array}\right]$$

$P^m$ 即代表此 Markov Chain 做

$m$ 次 transition 的 probability matrix，其中

$p_{ij}^m$ 代表經過

$m$ step 後從 state

$i$ 跳到 state

$j$ 的機率：

$$p_{ij}^m=P(X_{n+m}=j|X_n=i)=\sum _r{p}_{ir}^{m-k}{p}_{rj}^k,for0<k<m$$

Markov Chain 的 state 會隨著時間而變化，而長期來說，如果這個 Markov Chain long-term behavior 是穩定的，我們就可以求出其 steady state probability，也就是説讓這個 Markov Chain 跑一段時間後，我們對其經過的 state 的歷史進行觀察，可以看出其處於各個不同的 state 的機率分別是多少。

我們稱「處於各個不同的 state 的機率」為 Markov Chain 的 steady state probability。

令 steady state probability

$\pi =({\pi }_1,{\pi }_2,\cdots ,{\pi }_n)$，代表 Markov Chain 長期來說在 state

$1$, state

$2$，以此類推，的機率。

$\pi$ 可由以下公式解聯立方程式求出：

$$\{\begin{array}{l}\pi P=\pi \\ \pi e=1\end{array}$$

where

$e=(1,1,\cdots ,1)$，其中第一式的意義為：steady state 的機率是穩定的，就算再多經過一次 transition 也不會改變。第二式的意義為機率合為

$1$。

Continuous-time Markov Chain

在 Continuous-time Markov Process中，系統處於每一個 state 的時間都是一個 exponential random variable。

和 Discrete-time Markov Chain 類似，假設 state space

$S=(1,2,3,\cdots ,n)$，我們定義 transition matrix

$Q$，我們稱

$Q$ 為 generator matix：

$$Q=\left[\begin{array}{ccccc}-q_{11}& q_{12}& q_{13}& \dots & q_{1n}\\ q_{21}& -q_{22}& q_{23}& \dots & q_{2n}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ q_{n1}& q_{n2}& q_{n3}& \dots & -q_{nn}\end{array}\right]$$

其中

$q_{ij}\mathrm{\Delta }t$ 為此 Markov Process(Chain) 在

$(t,t+\mathrm{\Delta }t)$ 內從 state

$i$ 跳到 state

$j$ 的機率。

$-q_{ii}=q_i=-\sum _{j\ne i}{q}_{ij}$，代表

$Q$ matrix 的每一個 row 的 sum 都是

$0$。關於

$-q_{ii}$ 的意義請見下方連立方程式的說明。

給定一個 state transition diagram，寫出

$Q$ 的步驟就是先把非對角線的

$q_{ij}$ 通通填完，最後利用 row sum

$=0$ 將對角線填上。

令 steady state probability matrix

$P=(p_1,p_2,\cdots ,p_n)$，

$e=(1,1,1,\cdots ,1)$，可由下式求出 steady state probability：

$$\{\begin{array}{l}PQ=0\\ Pe=1\end{array}$$

其中第一式代表的意義為：對於任一一個 state

$i$ 而言，從自己跳出去到別的 state

$j\ne i$ 的機率的總和，會和其他人跳進來的機率總和相等（系統達到穩定、平衡的狀態），至於為何會相等，可以直觀來解釋：因為若不相等，跳進來的不等於跳出去的，那麼 state probability 就還會變動。

將跳出去等於跳進來這件事寫成數學式：

$$p_i(-q_{ii})=p_i\sum _{j\ne i}{q}_{ij}=\sum _{j\ne i}{p}_j{q}_{ji}$$

其中

$\sum _{j\ne i}{q}_{ij}=-q_{ii}$ 可解釋為何

$Q$ matrix 要如此定義（row sum = 0）。

Embedded Markov Chain

• wiki definition of Embedded Markov Chain
• Difference between embedded chain and continuous-time Markov chain

image source

若 Continuous-time Markov Chain 觀察的角度是錄影，那麼 Embedded Markov Chain 就是在照相（只是照很多張而已）。

If we observe the system state right after a state transition in continuous-time Markov Chain. Let

$X_n$ be the

$n$-th observed state, then

$\{X_n,n=1,2,3,\dots \}$ is called embedded Markov Chain(a discrete-time Markov Chain).

在一個 continuous-parameter 的 Markov Chain 中，只觀察系統 state 變化的時刻（就是在照相），觀察的結果為一個 discrete-parameter 的 Markov Chain，我們稱之為 Embedded Markov Chain。

而我們在照相完之後，會有很多照片，分析這些照片代表的意義，就可以定義 transition probability

$p_{ij}$。

$p_{ij}$ 代表的意義為，從 state i 要跳到 state j 的機率，可寫成

$$\frac{q_{ij}}{\sum _{k\ne i}{q}_{ik}}$$

也就是從state i 跳到 j 的機率除以所有從 state i 出去（到除了 state j 以外的 state）的機率的總和。（這裡的

$q_{ij}$ 和 continuous-time Markov Chain 裡的是一樣的定義）

每個 state 的 holding time 會是一個 exponential r.v.，其期望值(mean holding time)為

$$\frac{1}{\sum _{k\ne i}{q}_{ik}}=\frac{1}{q_i}$$

以 Birth-Death Processes 為例，其

$p_{ij}$ 可表示成

$$p_{ij}=\{\begin{array}{l}\frac{{\lambda }_i}{{\lambda }_i+{\mu }_i},ifj=i+1\\ \frac{{\mu }_i}{{\lambda }_i+{\mu }_i},ifj=i-1\\ 1,ifi=0,j=1\\ 0,else\end{array}$$,

將所有

$p_{ij}$ 綜合起來寫成矩陣

$P$，即可用聯立方程式求解 steady state probability

$\pi =({\pi }_1,{\pi }_2,...,{\pi }_n)$：

$$\{\begin{array}{l}\pi P=\pi \\ \pi e=1\end{array}$$

where

$e=(1,1,...,1)$

若一個 coninuous-time Markov Chain 的 Embedded Markov Chain 為 irreducible 且 positive recurrent，我們就說這個 continuous-time Markov Chain 也是 irreducible 且 positive recurrent。

至於要判斷是否具有 stationary solution, limiting distribution, ergodicity 的話，會需要知道是否為 aperiodic。

判斷 aperiodic 的方法為：判斷其 Embedded Markov Chain 的 mean holding time 是否為bounded，若是，就如同這個 Continuous-time Markov Chain 為 aperiodic 一樣。

Embedded Markov Chain & Continuous-time Markov Chain

在理解 Embedded Markov Chain & Continuous-time Markov Chain 各自的定義以及如何求解之後，我們來比較他們兩個之間的異同以及其關聯性。

$P_i$ 是 Continuous-time Markov Chain 求出來的解，而

${\pi }_i$ 是 Embedded Markov Chain 求出來的解，他們各自代表的意義如下：

${\pi }_i$ : represents the ratio of visit state

$i$ among all state

$P_i$: represents the time ratio that system stays at state

$i$ in a long term observation period.

Embedded Markov Chain 就像是在對系統進行拍照，而 Continuous-time Markov Chain就像是在對系統進行錄影，兩者所得出的結果

$\pi$,

$P$ 的值理所當然會不一樣，因為觀察角度不同，至於要用哪個角度觀察，會因觀察的需求不同而定。

兩者之間的關係可以透過下式得到:

$$P_i=\frac{m_i{\pi }_i}{\sum _j{m}_j{\pi }_j}$$

where

$m_i$ is the mean holding time at state i

因為

$m_i$ 代表是在 state

$i$ 的平均停留時間，結合上面對於

${\pi }_i$ 和

$P_i$ 所代表的意義的說明，上式的意義就很直觀明瞭了（時間 x 比例 = 時間比例，time x ratio = time ratio）

A Simple Example

Consider an

$M/M/1/3$ queue with arrival rate

$\lambda$ and service rate

$\mu$.

1. Please write down the generator matrix

   $Q$ for its continuous time Markov Chain, which represents its system size(the number of customers in the system). (4%)
   answer

   $Q=\left(\begin{array}{cccc}-\lambda & \lambda & 0& 0\\ \mu & -(\lambda +\mu )& \lambda & 0\\ 0& \mu & -(\lambda +\mu )& \lambda \\ 0& 0& \mu & -\mu \end{array}\right)$

2. Please then solve its steady-state probability

   $p_n$ for
   $n=0,1,2,3$ using the generator matrix obtained in 1. (6%)
   answer

   let

   $P=(p_0,p_1,p_2,p_3),e=(1,1,1,1),\rho =\frac{\lambda }{\mu }$
   solve:

   $$\{\begin{array}{l}PQ=0\\ Qe=1\end{array}⟹\{\begin{array}{l}{p}_1=\rho \cdot p_0\\ p_2={\rho }^2{p}_0\\ p_3={\rho }^3{p}_0\\ p_0=(1+\rho +{\rho }^2+{\rho }^3{)}^{-1}\end{array}$$

3. Derive the embedded Markov chain of this

   $M/M/1/3$ queue and obtain its steady state probability
   ${\pi }_n$ for
   $n=0,1,2,3$. (6%)
   answer

   The transition matrix

   $$P=\left(\begin{array}{cccc}0& 1& 0& 0\\ \frac{\mu }{\lambda +\mu }& 0& \frac{\lambda }{\lambda +\mu }& 0\\ 0& \frac{\mu }{\lambda +\mu }& 0& \frac{\lambda }{\lambda +\mu }\\ 0& 0& 1& 0\end{array}\right)$$

   let

   $\pi =({\pi }_0,{\pi }_1,{\pi }_2,{\pi }_3),e=(1,1,1,1),\rho =\frac{\lambda }{\mu }$
   solve:

   $$\{\begin{array}{l}\pi P=\pi \\ \pi e=1\end{array}⟹\{\begin{array}{l}{\pi }_0=\frac{{\mu }^2}{2{\mu }^2+2{\lambda }^2+2\lambda \mu }\\ {\pi }_1=\frac{\mu (\lambda +\mu )}{2{\mu }^2+2{\lambda }^2+2\lambda \mu }\\ {\pi }_2=\frac{\lambda (\lambda +\mu )}{2{\mu }^2+2{\lambda }^2+2\lambda \mu }\\ {\pi }_3=\frac{{\lambda }^2}{2{\mu }^2+2{\lambda }^2+2\lambda \mu }\end{array}$$

4. Please determine the mean holding time for state 0,1,2, and 3.(4%)

   answer

   let

   $m_i$ denote the mean holding time for state

   $i$.

   $$\{\begin{array}{l}{m}_0=\frac{1}{\lambda }\\ m_1=\frac{1}{\lambda +\mu }\\ m_2=\frac{1}{\lambda +\mu }\\ m_3=\frac{1}{\mu }\end{array}$$

5. Use the results of

   ${\pi }_n$ in 3. and the mean holding time in 4. to derive the formula for the steady-state probability
   $p_n$.(Hint: the results should be the same as in 2.)(6%)
   answer

   Use
   

   $$p_i=\frac{m_i{\pi }_i}{\sum _{i=0}^4{m}_j{\pi }_j}$$

   Compute
   

   $$\begin{array}{rl}{p}_0& =\frac{m_0{\pi }_0}{\sum _{i=0}^4{m}_j{\pi }_j}\\ & =\frac{{\mu }^2\frac{1}{\lambda }}{{\mu }^2\cdot \frac{1}{\lambda }+\mu (\lambda +\mu )\cdot \frac{1}{\lambda +\mu }+\lambda (\lambda +\mu )\cdot \frac{1}{\lambda +\mu }+{\lambda }^2\cdot \frac{1}{\mu }}\\ & =\frac{1}{1+\frac{\lambda }{\mu }+(\frac{\lambda }{\mu }{)}^2+(\frac{\lambda }{\mu }{)}^3}\\ & =\frac{1}{1+\rho +{\rho }^2+{\rho }^3}\end{array}$$

   then

   $p_1,p_2,p_3$ 可如法炮製，一場混戰之後會發現，結果和 2. 的結果相同。（NOTE: 同學在考試時不可以寫如法炮製，要實際算出來）

Reference

• Useful Markov Chain Math Note