# Queueing Theory - 3.1 Birth-Death Processes

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

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

> Figure 3.1 Rate transition diagram for a birth death process.

* 第三章開始我們都只討論排隊系統的 steady state，不會有 steady state 的就沒有什麼探討價值了
* Birth-Death Processes 是 M/M/1 的通式，他的每一個狀態代表系統內還存有的事件數，每個時間區間會發生的狀態轉移就只有可能是 +1 （往後一個狀態）、 0 （維持在當前狀態）、 -1 （往前一個狀態）這三種可能性而已，如 Fig. 3.1 所示
* 在第 $n$ 個狀態往後一個狀態的**遷移率 (transition rate)** 是 $\lambda_n$
* 在第 $n$ 個狀態往前一個狀態的遷移率是 $\mu_n$，因為第 0 個狀態無法再往前遷移了，所以 $\mu_0 = 0$
* 依照這樣的規範，我們可以得知一個 birth-death process 的 intensity matrix $\textbf{Q}$（從某狀態變化到另一個狀態的速率矩陣）會有以下的規律
$$
q_{n, n+1} = \lambda_n, \; q_{n, n-1} = \mu_n, \; q_{r, j} = 0 \text{ if } |r - j| \geq 2 \\
v_n = \lambda_n + \mu_n, \; \mu_0 = 0
$$
也就是只有對角線和對角線上下的斜線內有數字，其他都是 0。看起來會像
$$
\textbf{Q} =
\begin{bmatrix}
-(\lambda_0 + \mu_0) & \lambda_0 & 0 & \dots \\
\mu_1 & -(\lambda_1 + \mu_1) & \lambda_1 & 0 \\
0 & \mu_2 & -(\lambda_2 + \mu_2) & \lambda_2 \\
\vdots & 0 & \mu_3 & \ddots
\end{bmatrix}
$$
* 我們想要知道 birth-death process 的穩定態會有什麼樣的分佈，因此可以透過 Theorem 2.13 和 Theorem 2.15 列出 stationary equation，然後求得 $p_n$ 在穩定態的數值
* **Birth-death process 是一個連續時間馬可夫鍊**，根據 Theorem 2.15，在穩定態時必須符合 $\textbf{p}^{'}(t) = \textbf{p}(t)\textbf{Q}$ 的等式，也就是
$$
0 = -v_n p_n + \sum_{r \neq n}p_r q_{rn}
$$
* 將上式代入實際的遷移率，會得到
$$
\begin{cases}
0 = -(\lambda_n + \mu_n)p_n + \lambda_{n-1}p_{n-1} + \mu_{n+1}p_{n+1}, \quad n \geq 1 \\
0 = -\lambda_0 p_0 + \mu_1 p_1, \quad n = 0
\end{cases}
$$
* 我們想要得到 $p_n$ 的通式，這個式子裏面不可以有未知項。因為 birth-death process 的 stationary equation 還算規律，可以簡單的用暴力法求得 $p_n$ 的通式
$$
\begin{align}
& \Rightarrow \begin{cases}
p_{n+1} = \frac{\lambda_n + \mu_n}{\mu_{n+1}}p_n - \frac{\lambda_{n-1}}{\mu_{n+1}}p_{n-1}, \quad n \geq 1 \\
p_1 = \frac{\lambda_0}{\mu_1}p_0, \quad n = 0 \\
\end{cases} \\
& \Rightarrow p_2 = \frac{\lambda_1 \lambda_0}{\mu_2 \mu_1}p_0, \; p_3 = \frac{\lambda_2 \lambda_1 \lambda_0}{\mu_3 \mu_2 \mu_1}p_0, \; \dots \\
& \Rightarrow p_n = p_0 \cdot \prod_{i=0}^{n} \frac{\lambda_{i-1}}{\mu_i} \tag{3.3}
\end{align}
$$
* 再加上 $\sum_{\forall n} p_n = 1$ 的 boundary condition，可以得知
$$
\begin{align}
& \sum_{\forall n} p_n = 1 \\
& \Rightarrow \Big( 1 + \sum_{n=1}^{\infty} \prod_{i=0}^{n} \frac{\lambda_{i-1}}{\mu_i}\Big)p_0 = 1 \\
& \Rightarrow p_0 = \Big( 1 + \sum_{n=1}^{\infty} \prod_{i=0}^{n} \frac{\lambda_{i-1}}{\mu_i}\Big)^{-1}
\end{align}
$$
將 $p_0$ 代回 $(3.3)$ 式，即可獲得 $p_n$ 的通式
* **注意！！** 等號右邊的分式，其**分母必須要收斂**才代表 $p_0$ 有解，否則這個系統就是無法達到 steady state 的系統
* 上述方法叫作**疊代法 (iterative method)**，僅適用在 stationary equation 較規律的 birth-death process 當中。面對 stationary equation 不規律的系統，疊代法會變得很難用，所以稍後在 M/M/1 系統當中，還會再另外介紹兩種方法來得到 $p_n$ 的通式
* 透過 Theorem 2.15 的方式列出 stationary equation 有時候很麻煩，我們可以改從 **flow balance** 的角度來看待 stationary equation（此時，又可以將其稱為 **balance equation**），如此一來在面對轉移行為不規則的系統時，也可以輕鬆的列出 stationary equation
> Figure 3.2 狀態之間的 Flow balance。切線處代表從狀態 $n$ 往右看的 flow balance 會牽涉到哪些 flow。
* 當我們僅關注一個狀態和他其中一邊（右邊或左邊）的鄰居之間的流量平衡時，所列出的式子叫作 **Local balance equation**
* 對於狀態 $n$ 來說，從自己**流出**到右邊鄰居的流量（是損耗，以負的流量表示）和從右邊鄰居**流入**自己的流量（是收入，以正的流量表示）需要達到平衡，因此往右看的 local balance equation 就是
$$
0 = -\lambda_n p_n + \mu_{n+1} p_{n+1}
$$
* 同理，往左邊看的 local balance equation 則是
$$
0 = -\mu_n p_n + \lambda_{n-1} p_{n-1}
$$
* 當我們不特別關注是往左邊還是往右邊看，只在乎對於某個狀態來說，總流入和總流出必須達到收支平衡，所列出的式子叫作 **Global balance equation**。以 Fig. 3.2 來說，狀態 $n$ 的 global balance equation 是
$$
0 = -(\lambda_n + \mu_n)p_n + \lambda_{n-1}p_{n-1} + \mu_{n+1} p_{n+1}
$$
* 在較複雜的系統當中，每一個狀態牽涉到的轉移（也就上圖中的有向邊）數量可能不規律。在面對這樣的系統時，使用 global balance equation 的觀點會比起使用 $\textbf{p}^{'}(t) = \textbf{p}(t)\textbf{Q}$ 的觀點還要容易列出系統的 stationary equation