# Birth-Death Processes


在了解 [Markov Chain](/K5BCWNpnQGii-DjMMuHnCQ) 的定義及其性質之後，這一節要介紹一種 continuous-time Markovian Chain: Birth-Death Processes。

在 Birth-Death Processes 中，state $n$ 只會跳到 state $n-1$ 或者 state $n+1$（state $0$ 只能跳到 state $1$），$n$ 代表 population in the system。

Transition rate 可表示為:

$$\begin{cases} \lambda_n,\ n \to n+1 \newline \mu_n,\ n \to n-1\end{cases}$$

所謂 Birth 就代表有一個 arrival($\lambda$ 對應的箭頭)，使整個系統的 size 增加 1，而從一個 birth 到下一個 birth 發生的間隔時間為 exponential random variable。

所謂 Death 就代表一個 departure($\mu$ 對應的箭頭)，也就是一個 customer 被 server 服務完而離開這個系統，系統的 size 減少 1，而兩個 Death(departure) 之間的時間長度也會是一個 exponential random variable。

由 Birth-Death Processes 延伸，包括日後會學到的 $M/M/1, M/M/1/2$ 等等各式各樣的 queue，這些 queue 都是以 Birth-Death Processes 為基礎，差別只在於 Server 的數量（影響到 service rate($\mu$)）以及 System Capacity 的不同（影響到 blocking probability & effective arrival rate($\lambda_{eff}$)）。

:::info
分析各種 queue 的第一步就是搞清楚 state transition，畫出各個 state 之間的 arrival & departure(service) rate（如 Figure 2.1），然後運用下面會介紹的 Balanced Equations 求出 steady state probability($p_n$) ，有了 steady state probability($p_n$) 就可以進一步分析 queue 的各種 metrics，像是 average system size $L$，以及 average waiting time $W$ 等等。
:::

因為 Birth-Death Processes 屬於 continuous-time Markov Chain，因此我們可以寫出它的 generator matrix：

$$Q = \begin{bmatrix}
-\lambda_0 & \lambda_0 & 0 & 0 & 0 &\cdots \\
\mu_1 & -(\lambda_1 + \mu_1) & \lambda_1 & 0 & 0 & \dots \\
0 & \lambda_2 & -(\lambda_2+\mu_2) & \lambda_2 & 0 &\cdots \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
\end{bmatrix}$$

當 state space 是有限的時候，可用

$$\begin{cases} PQ = 0 \\ Pe = 1\end{cases}$$

來求 steady state probability。

而 $PQ = 0$ 的式子經過整理其實就是 Global Balanced Equations。

## Global Balanced Equations

首先寫出 $PQ = 0$：

$$\begin{cases}
0 = -p_{n}(\lambda_{n} + \mu_n) + p_{n-1}\lambda_{n-1} + p_{n+1}\mu_{n+1}, n \gt 0\\
0 = -p_0\lambda_0 + p_1 \mu_1, n = 0
\end{cases}$$

移項：

$$\begin{cases}
p_{n}(\lambda_{n} + \mu_n) = p_{n-1}\lambda_{n-1} + p_{n+1}\mu_{n+1}, n \gt 0\\
p_0\lambda_0 = p_1 \mu_1, n = 0
\end{cases}$$

:::info
Global Balanced Equations 的意義為：在 Steady state，對一個 $p_n$ 來說要達到 Flow Balance，就是流進 $p_n$ 的 flow(右式)要和流出(左式)相等（見上面 Fig 2.1，注意**箭頭的流向**）。
:::

將第一式移項，我們可以將 $p_{n+1}$ 表示為：

$$p_{n+1} = \frac{\lambda_{n} + \mu_n}{\mu_{n+1}}p_{n} - \frac{\lambda_{n-1}}{\mu_{n+1}}p_{n-1}$$

將第二式移項，我們可以將 $p_{1}$ 表示為：

$$p_1 = \frac{\lambda_0}{\mu_1} p_0$$

如此一來我們可以由 $p_0, p_1, p_2$ 開始，不斷往上疊代，代換出 $p_3, p_4,\cdots$，下面以 $p_2$ 為例：

$$\begin{aligned}
p_{2} &= \frac{\lambda_{1} + \mu_1}{\mu_{2}}p_{1} - \frac{\lambda_{0}}{\mu_{2}}p_{0} \newline
&= \frac{\lambda_{1} + \mu_1}{\mu_{2}} \cdot \frac{\lambda_0}{\mu_1} p_0 - \frac{\lambda_{0}}{\mu_{2}}p_{0} \newline
&= \frac{\lambda_1 \lambda_0}{\mu_2 \mu_1} \cdot p_0
\end{aligned}$$

在代換的過程中我們會發現其規律，$p_n$ 可以被表示成：

$$p_n = \frac{\lambda_{n-1}\lambda_{n-2}\cdot\cdot\cdot\lambda_{0}}{\mu_n\mu_{n-1}\cdot\cdot\cdot\mu_1} \cdot p_0$$

## Detailed Balanced Equations


對$p_{n-1}, p_{n}$ 的中間的flow來說，跨到左邊跟跨到右邊（注意**箭頭的流向**） In the long term 會平衡（記得教授上課時說的例子：教授在上課期間內，從黑板左側走到右側，以及從右側走到左側的次數會差不多，最多差一次）:

$$\begin{cases}
p_{n-1}\lambda_{n-1} = p_n\mu_n \\
p_n = \frac{\lambda_{n-1}}{\mu_n}\cdot p_{n-1}
\end{cases}$$

繼續代換（將 $p_{n-1}$ 用 $p_{n-2}$ 表示，以此類推）即可得到下式 $p_n = \frac{\lambda_{n-1}\lambda_{n-2}\cdot\cdot\cdot\lambda_{0}} {\mu_n\mu_{n-1}\cdot\cdot\cdot\mu_1} \cdot p_0$

不論是 Global or Detailed，最後推導出來的結果都一樣：In steady state(In the long term)

$$p_n = \frac{\lambda_{n-1}\lambda_{n-2}\cdot\cdot\cdot\lambda_{0}}{\mu_n\mu_{n-1}\cdot\cdot\cdot\mu_1} \cdot p_0$$

## Steady State Probability

求解 $p_n$ 有三種方法可以用:

1. Iterative
2. Generating Funtions
3. Recurrence Fromulas

以下用 $M/M/1$ queue 來示範上述三種方法。

> [image source](http://programmingpaul.blogspot.com/2013/04/queueing-theorymm1-model.html)

### Iterative

已知：

$$p_n =\frac{\lambda_{n-1}\lambda_{n-2}\cdot\cdot\cdot\lambda_{0}}{\mu_n\mu_{n-1}\cdot\cdot\cdot\mu_1} \cdot p_0 = (\frac{\lambda}{\mu})^np_0 = \rho^n p_0$$

利用機率合為一求解 $p_0$：

$$\begin{align} &\sum_0^{\infty} p_n = \sum_0^{\infty}\rho^np_0 = p_0\sum_0^{\infty}\rho^n = 1 \\ &\Rightarrow p_0 = \frac{1}{\sum_0^{\infty} \rho^n} = 1 - \rho\ (\ given \ \rho \lt 1)\\ &\therefore p_n = p_0 \rho^n = (1 - \rho) \rho^n \end{align}$$

### Generating Functions

定義 [generating function](https://en.wikipedia.org/wiki/Generating_function) $P(z)$：

$$P(z) = \sum_0^{\infty}p_n\cdot z^n$$

寫出 Global Balance Equation：

$$\begin{cases} p_n(\lambda + \mu) = p_{n+1}\cdot\mu + p_{n-1}\cdot\lambda \\ p_1 = \rho p_0 \end{cases}$$

先對第一式做整理：
$$p_{n+1} = p_n (1+\rho) - p_{n-1} \cdot \rho$$

同乘上 $z^n$：

$$p_{n+1}z^{n} =(1+\rho)p_{n}z^{n} - \rho p_{n-1} z^{n}$$

把 $z$ 做 sum 起來：
$$\sum_{n=1}^{\infty} p_{n+1}z^{n} = \sum_{n=1}^{\infty} (1+\rho)p_{n}z^{n} - \sum_{n=1}^{\infty} \rho p_{n-1} z^{n}$$

調整 $z$ 的項次使之和 $p$ 一致：

$$\begin{aligned} z^{-1}\sum_{n=1}^{\infty}p_{n+1}z^{n+1}
&=(1+\rho)\sum_{n=1}^{\infty}p_{n}z^{n} - z\rho\sum_{n=1}^{\infty}p_{n-1}z^{n-1} \\
\end{aligned}$$

將 sigma 項換回 generating function，可得：
$$z^{-1}(P(z) - p_0 - p_1z) = (1+\rho)(P(z) - p_0) - z\rho P(z)$$

代入第二式（$p_1 = \rho p_0$）：
$$z^{-1}(P(z) - (1+\rho z)p_0) = (1+\rho)(P(z) - p_0) - z\rho P(z)$$

經過一場混戰，對式子做整理後可得：
$$P(z) = \frac{p_0}{1 - z \rho}$$

$z = 1$ 代入，可得：
$$\begin{align} &P(1) = \sum p_n\cdot 1^n = 1 = \frac{p_0}{1 - \rho}, \therefore p_0 = 1 - \rho \\ &\therefore P(z) = \frac{1 - \rho}{1 - z \rho} = \sum_0^{\infty} (1-\rho)\rho^n \cdot z^n = \sum_0^{\infty} p_n\cdot z^n \\ &\therefore p_n = (1-\rho)\rho^n \end{align}$$

:::info
NOTE: 當 $z = 1$ 時，$\frac{d}{dz} P(z)$就是 system size 的期望值 $L = \sum n p_n$
:::

### Recurrence Formulas

$$p_{n+1} = p_n (1+\rho) - p_{n-1} \cdot \rho, n \gt 1$$

用公式解遞迴（公式解以及其推導請參考離散數學相關課程及教材），base case 為 $p_1 = \rho p_0$，以及$\sum p_n = 1$