# Queueing Theory - 2.4 Continuous-Time Markov Chains

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

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

* **連續時間的馬可夫鍊 (Continuous-Time Markov Chains, CTMC)**，是一個擁有可數的狀態空間的隨機過程 $\{X(t), t \geq 0\}$，並且擁有以下特性：
* 每當馬可夫鍊進入一個狀態 $i$，他待在這個狀態的時間會遵守一個參數是 $v_i$ 的指數分佈（並且這個時間分佈是跟過去的時間分佈互相獨立的）
* 從狀態 $i$ 轉移到狀態 $j$ ($j \neq i$) 的機率是 $p_{ij}$
* 在 CTMC 中，只用一步要從自己轉移回自己是不可能的
* **The Markov property**
$$
Pr\{X(t+s) = j | X(t) = i, X(u), 0 \leq u < t\} = Pr\{X(t+s) = j | X(t) = i\}
$$
* 如果**現在**的系統狀態是 $X(t)$，則**未來**時間點的狀態 $X(t+s)$ 是與**過去** $X(u)$ 無關的（跟 DTMC 的概念相同，只是表記方式不一樣）
* **C-K Equation**
$$
p_{ij}(u, s) = \sum_{\forall r}p_{ir}(u,t)p_{rj}(t,s), \quad 0 \leq u < t < s
$$
* 白話文：在 $u$ 時間點時是在 $i$，而到 $s$ 時間點是在 $j$ 的機率，會跟把 $[u, s]$ 這段時間切成兩半（切點在時間點 $t$，當時的狀態是 $r$），先走一半再走剩下一半，所有可能路徑的加總，就是在時間區間 $[u, s]$ 期間從狀態 $i$ 轉移到狀態 $j$ 的機率
* 但是這樣寫不夠精確，在 CTMC 中，我們要強調的是轉移機率對上時間的**變化率**（也就是微分值），因此我們需要改寫上式
* 令 $s = t + \Delta t$ 代入上式中，並且減掉 $p_{ij}(u,t)$，然後再**對 $t$ 偏微分**，這樣就是在計算「固定時間起點，轉移機率對時間終點的時間變化率」，這樣的 C-K equation 叫作 **Forward C-K equation**
$$
p_{ij}(u, t + \Delta t) - p_{ij}(u,t) = \sum_{\forall r}p_{ir}(u,t)p_{rj}(t,t + \Delta t) - p_{ij}(u,t) \\
= -\big(1 - p_{jj}(t, t + \Delta t)\big)p_{ij}(u,t) + \sum_{r \neq j}p_{ir}(u,t)p_{rj}(t,t + \Delta t)
$$
* 在 $\sum$ 當中， $p_{ij}(u, t)p_{jj}(t, t + \Delta t)$ 這項和後面的減去 $p_{ij}(u, t)$ 有共通項，所以可以提出來，提出來之後 $\sum$ 裏面就要除去 $r = j$ 的那一項
* $1 - p_{jj}(t, t + \Delta t)$ 的物理意義就是「在 $\Delta t$ 時間內絕對會從狀態 $j$ 轉移出去到別的狀態的機率」
* $\sum_{r \neq j}p_{ir}(u,t)p_{rj}(t,t + \Delta t)$ 的物理意義就是「在 $\Delta t$ 時間內從別的狀態轉移進入狀態 $j$ 的機率」
* 站在狀態 $j$ 的觀點來看，前面這項是離開自己的機率，因為離開自己是損耗，所以帶負號；而後面這項是進入自己的機率，因為進入自己是收穫，所以帶正號（什麼東西的損耗/收穫？）
$$
\frac{\partial p_{ij}(u, t)}{\partial t} = -v_j(t)p_{ij}(u, t) + \sum_{r \neq j}p_{ir}(u, t)q_{rj}(t) \\
\text{where } v_j(t) = \lim\limits_{\Delta t \to 0} \frac{1 - p_{jj}(t, t + \Delta t)}{\Delta t}, \; q_{ij}(t) = \lim\limits_{\Delta t \to 0} \frac{p_{ij}(t, t + \Delta t)}{\Delta t}
$$
* $v_j(t)$ 的物理意義就是「從狀態 $j$ 離開的速率」
* $q_{ij}(t)$ 的物理意義就是「從狀態 $i$ 進入狀態 $j$ 的速率」
* 令 $u = u + \Delta u$ 代入上式中，並且減掉 $p_{ij}(u,t)$，然後再**對 $u$ 偏微分**，這樣就是在計算「固定時間終點，轉移機率對時間起點的時間變化率」，這樣的 C-K equation 叫作 **Backward C-K equation**
* 推導看[這裡](https://hackmd.io/KzHnNESwRKW-Hn5wg3X_ng?view#Backword-C-K-Equation-for-CTMC)

:::success
**Theorem 2.15** Let $p_i(t)$ be the probability that the system is in state $i$ at time $t$, let $\textbf{p}(t)$ be the vector $(p_0(t), p_1(t), ...)$, and let $\textbf{p}^{'}(t)$ be the vector of its derivatives. Then
$$
\textbf{p}^{'}(t) = \textbf{p}(t)\textbf{Q}
$$
In component form, this is
$$
p_j^{'}(t) = -v_j(t)p_j(t) + \sum_{r \neq j}p_r(t)q_{rj}(t)
$$
:::

* 上方推導中的 $v_i(t)$ 其實是可以用 $q_{ij}(t)$ 來表示的，只要窮舉出所有離開 $i$ 之後抵達的狀態，然後把轉移速率加總就好了
$$v_i(t) = \sum_{j \neq i}q_{ij}(t)$$
* 令 $u = 0$ 且 $p_i(0)$ 是時間點 0 時停留在狀態 $i$ 的機率，我們可以代換掉原本的 C-K equation 中所有的 $u$，讓變數只剩下 $t$ 一個，這樣偏微分方程就可以寫成常微分方程了
$$
p_j(t) = \sum_{\forall i}p_i(0)p_{ij}(0, t) \Rightarrow \frac{dp_j(t)}{dt} = \sum_{\forall i}p_i(0)\frac{dp_{ij}(0,t)}{dt} \\
\frac{\partial p_{ij}(u, t)}{\partial t} = -v_j(t)p_{ij}(u, t) + \sum_{r \neq j}p_{ir}(u, t)q_{rj}(t) \\
\Rightarrow \frac{dp_{ij}(0, t)}{dt} = -v_j(t)p_{ij}(0, t) + \sum_{r \neq j}p_{ir}(0, t)q_{rj}(t)
$$
* 將最後的這個常微分方程乘上 $p_i(0)$ ，再沿著所有的 $i$ 加總，並將式子中可以用上方等式代換掉的東西都代換掉，將會得到化簡後的微分方程
$$
\frac{dp_j(t)}{dt} = -v_j(t)p_j(t) + \sum_{r \neq j}p_r(t)q_{rj}(t)
$$
* $p_j(t)$ 的部份寫成向量形式便是 $\textbf{p}(t) \triangleq [p_0(t), p_1(t), ...]$
* 將上式寫成矩陣相乘的形式，可得
$$
\textbf{p}^{'}(t) = \textbf{p}(t)\textbf{Q}(t)
$$
其中 $\textbf{Q}(t)$ 被稱為 **Intensity matrix**，其內容物為
$$
\textbf{Q}(t) =
\begin{bmatrix}
-v_0(t) & q_{01}(t) & \dots \\
q_{10}(t) & -v_1(t) & q_{12}(t) \\
q_{20}(t) & \dots & \ddots \\
\vdots & \dots & \vdots
\end{bmatrix}
$$
* 如果 $\textbf{Q}(t) = \textbf{Q}$ ，也就是 intensity matrix 的值不是隨時間變動的函數，而是一個定值的話，那麼這個 CTMC 就會是齊次的 CTMC，上式就可以再改寫為
$$
\textbf{p}^{'}(t) = \textbf{p}(t)\textbf{Q}
$$
而這條式子就是 CTMC 版本的 stationary equation

:::success
**Theorem 2.16** For a continuous-time Markov chain, if the embedded discrete-time chain is irreducible and positive recurrent, then there is a unique solution to the stationary equations
$$
\textbf{0} = \textbf{pQ} \text{ and } \sum_j p_j = 1,
$$
where $\textbf{0}$ is a vector of zeros $(0, 0, ...)$. Furthermore, if the mean holding times in all states are bounded ($v_i > 0$ for all $i$), the chain has a limiting probability distribution equal to the stationary distribution.
:::