# Queueing Theory - 2.3 Discrete-Time Markov Chains

contributed by <[`kaeteyaruyo`](https://github.com/kaeteyaruyo)>

###### tags: `Queueing Theory`

* 在這個小節，我們要介紹一種模型，符合這種模型的系統，在不同的時間點會在一個離散的狀態集合中的不同狀態間轉移，這種模型叫作**馬可夫鍊 (Markov chain)**
> Figure 2.3 一個有 4 個狀態的馬可夫鍊
* 上圖展示了一個有 4 個狀態的馬可夫鍊。箭頭代表不同狀態之間的可能轉移方向。如果現在系統的狀態在 1，那下一個時間點他可能會轉移回到自己，或是轉移到狀態 2，其他狀態也以此類推
* 在排隊系統當中，系統的狀態常常被定義為現在系統當中的等待人數，在這樣的定義下，狀態集合就會屬於一個非負整數的空間（0, 1, 2, ...）
* **離散時間的馬可夫鍊 (Discrete-Time Markov Chains, DTMC)**，其狀態轉換只會發生在離散的時間點（例如：整數時間的時候）
* $X_n$: 系統在時間點 $n$ 時的狀態，且 $n = 0,1,2,...$
* **The Markov property**
$$
Pr\{X_{n+1} = j | X_0 = i_0, X_1 = i_1, ..., X_n = i_n\} = Pr\{X_{n+1} = j | X_n = i_n\}
$$
* 如果**現在**的系統狀態是 $X_n$，則**未來**時間點的狀態 $X_{n+1}$ 是與**過去**（$X_0, ..., X_{n-1}$）無關的（下一秒系統會變怎樣只跟這一秒有關）
* $Pr\{X_{n+1} = j | X_n = i_n\}$ 又被稱作 **（單步）轉移機率 (the (single-step) transition probability)**
* 如果這個馬可夫鍊是**齊次的 (homogeneous)**， 則
$$
p_{ij} \equiv Pr\{X_{n+1} = j | X_n = i\}
$$
* 也就是說，在任意時間點上的轉移機率都是一樣的（例如：$X_1$ 到 $X_2$ 的機率和 $X_5$ 到 $X_6$ 的機率一樣），叫作 $p_{ij}$
* 把所有的 $p_{ij}$ 蒐集起來，可以組成**單步轉移矩陣 (single-step transition matrix)** $\textbf{P}$，且 $\textbf{P} \triangleq [p_{ij}]_{n \times n}$
* $\textbf{P}$ 是一個隨機矩陣 (stochastic matrix)，他的每一列相加會是 1，因為同一列的數字代表從該狀態轉移到其他所有狀態的機率值，相加當然要等於 1（但沒有說每一行加起來也要是 1）
* 注意這裡的「單步」並不表示每一次的轉移中間經過了一樣長的時間。在排隊系統中，我們可能會把每次有顧客到來的時間點都視為一步的轉移，但顧客並不一定是等間隔時間到來的
* 一個齊次的馬可夫鍊轉移 $m$ 次的機率則可以定義為
$$
p_{ij}^{(m)} \equiv Pr\{X_{n+m} = j | X_n = i\}
$$
* 也就是說，從任意時間點開始往後 $m$ 步，機率都會是一樣的
* 把所有的 $p_{ij}^{(m)}$ 蒐集起來，可以組成**m 步轉移矩陣 (m-step transition matrix)** $\textbf{P}^{(m)}$，且 $\textbf{P}^{(m)} \triangleq [p_{ij}^{(m)}]_{n \times n}\text{, }\textbf{P}^{(m)} = \textbf{P}\cdot\textbf{P} ... \textbf{P} = \textbf{P}^m$
* **C-K equation for DTMC**
$$
p_{ij}(m, n) \triangleq Pr\{X_n = j | X_m = i\} = \sum_{\forall k \in X_t} p_{ik}(m, q)p_{kj}(q, n)
$$
* C-K equation 可以證明為什麼離散時間的齊次馬可夫鍊其轉移矩陣會是單步轉移矩陣的連乘積
$$
\begin{align}
Pr\{X_n = j | X_m = i\} &= \sum_{\forall k \in X_t} Pr\{X_n = j, X_q = k | X_m = i\}, \quad (m < q < n) \\
&= \sum_{\forall k \in X_t} Pr\{X_q = k | X_m = i\} Pr\{X_n = j | X_q = k, X_m = i\} \\
&= \sum_{\forall k \in X_t} Pr\{X_q = k | X_m = i\} Pr\{X_n = j | X_q = k\}
\end{align}
$$
* 想像一個有限狀態機，假設時間點 $m$ 時在 $i$ 這個狀態，時間點 $n$ 時在 $j$ 這個狀態，要從 $i$ 轉移到 $j$， 可能有很多種路徑可以走
* 在從 $i$ 轉移到 $j$ 的過程中，一定會經過某一個時間點 $q$， 假設在時間點 $q$ 時的狀態是 $k$， 則從 $i$ 轉移到 $j$ 的路徑就可以用「先從 $i$ 轉移到 $k$， 再從 $k$ 轉移到 $j$」這樣的路徑來描述
* 把所有「先從 $i$ 轉移到 $k$， 再從 $k$ 轉移到 $j$」的機率加總，就是從 $i$ 轉移到 $j$ 的機率了
* 在上方推導中的第二行，由於馬可夫鍊在任意時間點的轉移機率都只跟當下的狀態有關，跟之前的狀態無關，所以可以直接把 $X_m = i$ 的條件刪掉，機率值是不變的
* 最後我們發現，從時間點 $m$ 到時間點 $n$， 從狀態 $i$ 轉移到狀態 $j$ 的機率，就剛好是矩陣乘法的定義式
* 而在齊次馬可夫鍊的情況下，任意時間點上的單步轉移機率都是一樣的，因此多步轉移的轉移機率，就是單步轉移機率矩陣多次連乘的乘積
* C-K equation 的一個應用在於，我們常常會把一個馬可夫鍊經過 $m$ 步後會停在某個狀態 $j$ 的機率記成 $\pi_j^{(m)}$，那就會等於「先走 $m-1$ 步看會停在哪個狀態，再從該狀態走到 $j$」的所有可能的機率加總
$$
\pi_j^{(m)} \equiv Pr\{X_m = j\} \Rightarrow \pi_j^{(m)} = \sum_i \pi_i^{(m-1)p_{ij}}
$$
* 寫成矩陣形式的話就是
$$
\boldsymbol{\pi}^{(m)} = \boldsymbol{\pi}^{(m-1)} \textbf{P} = \boldsymbol{\pi}^{(m-2)} \textbf{P} \cdot \textbf{P} = ... = \boldsymbol{\pi}^{(0)} \textbf{P}^m
$$
其中 $\boldsymbol{\pi}^{(0)}$ 就是馬可夫鍊的**初始狀態分佈 (initial state distribution)**

## 2.3.1 Properties of Markov Chains

* 如果存在一個 $n \geq 0$ 使得 $p_{ij}^{(n)} > 0$，則我們說狀態 $j$ 是（從狀態 $i$）**可通達的 (accessible)** ($i \rightarrow j$)
* 如果狀態 $i$ 可以到狀態 $j$，狀態 $j$ 也可以到狀態 $i$，那我們說這兩個狀態是**可連通的 (communicate)** ($i \leftrightarrow j$)
* 一個馬可夫鍊當中的所有狀態，可以根據他們和其他狀態之間是否可連通，被分成數個**連通類別 (communication classes)**
:::warning
如果把馬可夫鍊視為有向圖，communication classes 等同於圖論中的強連通元件嗎？
:::
* 如果一個馬可夫鍊中所有的狀態都屬於同一個 communication classes， 則稱這個馬可夫鍊是**不可分解的 (irreducible)**
* 如果從狀態 $j$ 出發，走好幾步之後可以回到自己，則我們把這個環的長度稱為狀態 $j$ 的**周期 (period)**
* 數學定義： $period = GCD\Big(\{m | p_{jj}^{(m)} > 0\}\Big)$
* 但這不代表從狀態 $j$ 出發走了 period 步就一定回到自己
* 例如：有一個狀態，走第一條路徑可以用兩步繞回自己，但走另一條路徑卻要三步才能繞回自己，那他的 period 就會是 $GCD(3, 2) = 1$。但是很顯然只走一步的話，是沒辦法從這個狀態繞回自己的
* 如果有一個狀態的 period 是 1 的話，我們說該狀態是 **aperiodic**
* 如果一個馬可夫鍊中的每一個狀態都是 aperiodic，則稱該馬可夫鍊是 **aperiodic chain**
* 從狀態 $j$ 出發後可以在 $n$ 步以內回到自己的機率被表示為 $f_{jj}^{(n)}$
* 而從狀態 $j$ 出發後有辦法回到自己的機率（不論走幾步，但一定是第一次回來）則表示為 $f_{jj} = \sum_{n=1}^{\infty}f_{jj}^{(n)}$
* 如果一個狀態走出去之後必定可以回到自己，則稱這個狀態為 **recurrent** state，反之就是 **transient** state
* 當狀態 $j$ 的 $f_{jj} = 1$，則為 recurrent
* 當狀態 $j$ 的 $f_{jj} < 1$，則為 transient
* 對於 recurrent state，可以計算**平均回歸時間 (mean recurrence time)**
* $m_{jj} = \sum_{n=1}^{\infty}nf_{jj}^{(n)}$，也就是 $f_{jj}$ 的期望值
* 如果 $m_{jj} < \infty$ （會收斂），則稱狀態 $j$ 是 **positive recurrent**
* 如果一個馬可夫鍊中的每一個狀態都是 positive recurrent，則稱該馬可夫鍊是 **positive recurrent chain**
* 如果 $m_{jj} = \infty$ （會發散），則稱狀態 $j$ 是 **null recurrent**
* 在狀態數量有無限個的馬可夫鍊中，有可能會有一定回得到自己，但是平均回歸時間卻是無限大的狀態
* 對於 transient state 來說，因為有些狀況永遠都無法回到自己，所以計算 $m_{jj}$ 是沒有意義的
* 範例說明 (Example 2.7)
* State 0: transient
* State 1, 2: positive recurrent, period = 2
* State 3, 4, 5: positive recurrent, aperiodic
* 可以發現在同一個 communication class 中，只要有一個人是 positive recurrent，則其他人一定也都是，而且 period 會一樣長

## 2.3.2 Long-Run Behavior

* 我們常常會把一個馬可夫鍊經過 $m$ 步後會停在某個狀態 $j$ 的機率記成 $\pi_j^{(m)}$，如果把這個 $m$ 拉到 $\infty$ 的話，我們就把 $\pi_j^{(\infty)}$ 稱為該馬可夫鍊的**長期行為 (long-run behavior)**
* 相較之下，如果 $m$ 是一個不是那麼大的有限數字，那就稱 $\pi_j^{(m)}$ 為該馬可夫鍊的暫時行為 (transient behavior)
* 令 $\{Y_n, n \in I\}$ 為一個馬可夫鍊，該馬可夫鍊的狀態集合為 $S$，並且初始機率向量 $\pi^{(0)} = \Big(\pi_j^{(0)}, j \in S\Big)$。如果<span style="color: red">不管選擇什麼樣的 $\pi^{(0)}$ </span>，都能滿足
$$
\lim\limits_{n \to \infty} Pr\{Y_n = j\} = \lim\limits_{n \to \infty} \pi_j^{(n)} = \pi_j \text{, } j \in S
$$
則我們稱向量 $\pi = (\pi_j, j \in S)$ 為該馬可夫鍊的 **limiting (or steady-state) distribution**
* 白話文：不管從什麼狀態開始，走足夠多步數後停留在任意狀態的機率分佈都是定值的話（就是說不管起始狀態如何、不管走幾步，最後看到的 $\pi^{(n)}$ 都長得一樣），這個馬可夫鍊就是**有穩定態 (steady state) 的馬可夫鍊**，這時候的 $\pi^{(n)}$ 稱作他的**穩定態分佈 (steady-state distribution)**
* 但如果每次要檢查一個馬可夫鍊有沒有穩定態都要窮舉出所有的 $\pi^{(0)}$ 來做檢查，那根本是不可能的事，所以我們需要別的方法來檢驗一個馬可夫鍊到底有沒有穩定態
* 如果一個馬可夫鍊有穩定態， 則 $\lim\limits_{n \to \infty} p_{ij}^{(n)} = \pi_j$ （limiting 就是取極限的意思）
$$
\begin{align}
\pi_j &= \lim\limits_{n \to \infty} \pi_j^{(n)} \\
&= \lim\limits_{n \to \infty} \sum_{\forall i}\pi_i^{(0)}p_{ij}^{(n)} = \sum_{\forall i}\pi_i^{(0)}\lim\limits_{n \to \infty}p_{ij}^{(n)}\\
&= \pi_k^{(0)}\lim\limits_{n \to \infty}p_{kj}^{(n)} (\text{Let } \pi^{(0)} = (0,0,...,1,0,...,0)) \\
&= \lim\limits_{n \to \infty}p_{kj}^{(n)} = \lim\limits_{n \to \infty}p_{ij}^{(n)}
\end{align}
$$
* 白話文：如果一個馬可夫鍊有 steady state 的話，把他的轉移矩陣連乘 $n$ 次，當 $n$ 夠大時，會發現這個矩陣的每個 column 會有一樣的極限值（也就是每一個 row 都長得一樣）
* 給定一個 DTMC，如果他擁有 $\lim\limits_{n \to \infty}p_{ij}^{(n)} = \pi_j \Rightarrow \lim\limits_{n \to \infty}\pi_{j}^{(n)} = \pi_j$ 的現象，則可以推斷他會具有 steady state。
$$
\begin{align}
\lim\limits_{n \to \infty} \pi_j^{(n)} &= \lim\limits_{n \to \infty} \sum_{\forall i}\pi_i^{(0)}p_{ij}^{(n)} \\
&= \sum_{\forall i}\pi_i^{(0)}\lim\limits_{n \to \infty}p_{ij}^{(n)}\\
&= \sum_{\forall i}\pi_i^{(0)}\pi_{j} \\
&= \pi_j
\end{align}
$$
* 白話文：在不知道一個 DTMC 有沒有 steady state 的情況下，可以檢查他的每個 column 在連乘的無窮多次的情況下，會不會收斂到相同的值。如果會，就表示他有 steady state。
* $\sum_{\forall i}\pi_i^{(0)}$ 的部份，無論在哪個時間點加總都是 $1$ (因為這是機率分佈的值，機率值加總要是 1)
* 如果我們已經知道一個 DTMC 是有 steady state 的，那我們要怎麼求他的 limiting distribution $\pi_j$ 呢？
* 我們可以從以下角度下去思考
* $\boldsymbol{\pi}^{(m)} = \boldsymbol{\pi}^{(m-1)}\textbf{P}$ ：馬可夫鍊在時間點 $m$ 時的狀態，是透過時間點 $m - 1$ 時的狀態乘上轉移矩陣一次算出來的
* $\lim\limits_{m \to \infty} \boldsymbol{\pi}^{(m)} = \lim\limits_{m \to \infty} \boldsymbol{\pi}^{(m-1)}\textbf{P} \Rightarrow \boldsymbol{\pi} = \boldsymbol{\pi} \textbf{P}$ ：當一個 DTMC 是有 steady state 的時候，他的狀態分佈在達到穩定時就算再多乘一次轉移矩陣，也不會有任何的變化
* 根據這個條件，再加上狀態分佈無論何時加總都要為 1，合併起來可以列出一個馬可夫鍊的 **stationary equations**
$$
\begin{cases}
\boldsymbol{\pi} = \boldsymbol{\pi} \textbf{P} \\
\sum_{\forall j} \pi_j = 1 \end{cases}
$$
而解出來的答案就叫作 stationary distribution (solution)
* 在已經確定一個 DTMC 有 steady state 的前提下，則他的 limiting distribution 必定會是 stationary equations 的解
* **但是！！一個 DTMC 的 stationary equations 有解，並不一定保證他就是該 DTMC 的 limiting distribution！** 也就是說， stationary equations 有解是比較簡單的一件事（而且這個解還可能不只一個），而要找到 limiting distribution（也就是要滿足有 steady state 的條件）是比較困難的
* 如果一個 DTMC 的 limiting distribution 存在，則這個 limiting distribution 一定會是 stationary equations 的**唯一解**

:::success
**Theorem 2.13** An **irreducible** (1) and **positive recurrent** (2) discrete-time Markov chain has a unique solution to the stationary equations $$\pi = \pi P \text{ and } \sum_j \pi_j = 1$$ namely, $\pi_j = \frac{1}{m_{jj}}$. Furthermore, if the chain is **aperiodic** (3), the limiting probability distribution exists and is equal to the stationary distribution.
:::
* 白話文
* 如果一個 DTMC 滿足 (1) 和 (2)，則他會有 stationary distribution，而且 $\pi_j$ 為 mean recurrence time 的倒數
* 如果如果一個 DTMC 滿足 (1), (2) 和 (3)，則他的 limiting distribution 存在且跟 stationary distribution 相同
* 綜合以上觀察，我們可以從兩個角度來解讀 $\pi_j$ 的物理意義
* 對於任何的 DTMC， $\pi_j$ 都可以代表長期來看 DTMC 停留在狀態 $j$ 的時間比例，因此才會 $\pi_j = \frac{1}{m_jj}$
* 對於滿足 (1), (2), (3) 的 DTMC，也就是有 steady state 的 DTMC 來說，則可以更進一步解釋成他的 limiting probability

## 2.3.3 Ergodicity

* 有一個隨機過程 $\{X(t), t \geq 0\}$，其中 $X_i(t)$ 就是 $\{X(t), t \geq 0\}$ 的第 $i$ 個 realization (experiment)
* 第 0 個 realization $X_0(t)$ 的**時間平均 (time average)** 可以記作
$$
\overline{x_T^k} = \frac{1}{T}\int_0^T[x_0(t)]^kdt
$$
意思是在某個時間區間內，這個隨機過程的狀態值平均而言是多少，如上圖左
* $T$: 這個時間平均的觀察區間
* $k$: $x_0(t)$ 的次方數，乘 $k$ 次方的值被稱作 $k$-th moment
* $\int_0^T[x_0(t)]^kdt$: 算這個隨機變數在 $[0, T]$ 區間內的面積
* 在 $t$ 時間點的 **Ensemble average** 則是
$$
E[X(t)]^k = \lim\limits_{n \to \infty} \frac{\sum_{i=0}^{n-1}[X_i(t)]^k}{n} = m_k(t)
$$
意思就是我重複做好多次實驗，在給定的 $t$ 時間點平均的狀態值會是多少，如上圖右
* 一個隨機過程如果滿足
$$
\lim\limits_{T \to \infty} \overline{x_T^k} = \lim\limits_{t \to \infty} m_k(t) = \overline{x^k} < \infty
$$
則我們說他對於他的 $k$-th moment 是**遍歷的 (ergodic)**
* 白話文：當你實驗觀察的區間拉的很長，算出來的 time average，和在這個實驗的很後段，拉出他的 ensemble average 來看，這兩個值會收斂到一樣的值的話，那就說他對這個 $k$ 值有 ergodicity
* 如果對於任意的 $k$-th moment 都有以上的現象，那就稱為 **fully ergodic**
* 不同 DTMC 的 long-run behavior 和他們的物理意義
* 嚴謹度的差異： stationary 有唯一解 < ergodic < limiting
* Stationary equation 有唯一解
* 此時 $\pi_j$ 的物理意義就是長期來看馬可夫鍊處於狀態 $j$ 的時間比例
* Ergodic
* 在 Stationary equation 有唯一解的情況下，將初始狀態設定成 $\pi^{(0)} = \pi$，就會有 ergodicity
* DTMC 運作非常久之後，ensemble average 和 time average 一樣
* 有 Stationary 的性質（不管走幾步，抵達各狀態的機率值都一樣）（？？？）
* Limiting
* 不可以挑剔初始狀態，只要時間過很久，抵達各狀態的機率值要一樣
* Limiting 不一定會有 stationary，可能在不同步數的時候機率值會不一樣，但是長遠來看是有穩定值的
* 一個 irreducible 而且 positive recurrent 的 DTMC 不一定是 stationary
* $\pi^{(n)} = \pi \quad \text{ for all } n$
* 必須要把起始的狀態設定成 stationary vector（$\pi^{(0)} = \pi$） 才會有 stationary（見 Example 2.13）