Birth-Death Processes

在了解 Markov Chain 的定義及其性質之後，這一節要介紹一種 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{array}{l}{\lambda }_n,n\to n+1\\ {\mu }_n,n\to n-1\end{array}$$

所謂 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}$)）。

分析各種 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=\left[\begin{array}{cccccc}-{\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 \\ ⋮& ⋮& ⋮& \ddots & ⋮\end{array}\right]$$

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

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

來求 steady state probability。

而

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

Global Balanced Equations

首先寫出

$PQ=0$：

$$\{\begin{array}{l}0=-p_n({\lambda }_n+{\mu }_n)+p_{n-1}{\lambda }_{n-1}+p_{n+1}{\mu }_{n+1},n>0\\ 0=-p_0{\lambda }_0+p_1{\mu }_1,n=0\end{array}$$

移項：

$$\{\begin{array}{l}{p}_n({\lambda }_n+{\mu }_n)=p_{n-1}{\lambda }_{n-1}+p_{n+1}{\mu }_{n+1},n>0\\ p_0{\lambda }_0=p_1{\mu }_1,n=0\end{array}$$

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{array}{rl}{p}_2& =\frac{{\lambda }_1+{\mu }_1}{{\mu }_2}{p}_1-\frac{{\lambda }_0}{{\mu }_2}{p}_0\\ & =\frac{{\lambda }_1+{\mu }_1}{{\mu }_2}\cdot \frac{{\lambda }_0}{{\mu }_1}{p}_0-\frac{{\lambda }_0}{{\mu }_2}{p}_0\\ & =\frac{{\lambda }_1{\lambda }_0}{{\mu }_2{\mu }_1}\cdot p_0\end{array}$$

在代換的過程中我們會發現其規律，

$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{array}{l}{p}_{n-1}{\lambda }_{n-1}=p_n{\mu }_n\\ p_n=\frac{{\lambda }_{n-1}}{{\mu }_n}\cdot p_{n-1}\end{array}$$

繼續代換（將

$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

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 }{)}^n{p}_0={\rho }^n{p}_0$$

利用機率合為一求解

$p_0$：

$$\begin{array}{rl}& \sum _0^{\mathrm{\infty }}{p}_n=\sum _0^{\mathrm{\infty }}{\rho }^n{p}_0=p_0\sum _0^{\mathrm{\infty }}{\rho }^n=1\\ & \Rightarrow p_0=\frac{1}{\sum _0^{\mathrm{\infty }}{\rho }^n}=1-\rho (given\rho <1)\\ & \therefore p_n=p_0{\rho }^n=(1-\rho ){\rho }^n\end{array}$$

Generating Functions

定義 generating function

$P(z)$：

$$P(z)=\sum _0^{\mathrm{\infty }}{p}_n\cdot z^n$$

寫出 Global Balance Equation：

$$\{\begin{array}{l}{p}_n(\lambda +\mu )=p_{n+1}\cdot \mu +p_{n-1}\cdot \lambda \\ p_1=\rho p_0\end{array}$$

先對第一式做整理：

$$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}^{\mathrm{\infty }}{p}_{n+1}{z}^n=\sum _{n=1}^{\mathrm{\infty }}(1+\rho )p_n{z}^n-\sum _{n=1}^{\mathrm{\infty }}\rho p_{n-1}{z}^n$$

調整

$z$ 的項次使之和

$p$ 一致：

$$\begin{array}{rl}{z}^{-1}\sum _{n=1}^{\mathrm{\infty }}{p}_{n+1}{z}^{n+1}& =(1+\rho )\sum _{n=1}^{\mathrm{\infty }}{p}_n{z}^n-z\rho \sum _{n=1}^{\mathrm{\infty }}{p}_{n-1}{z}^{n-1}\end{array}$$

將 sigma 項換回 generating function，可得：

$$z^{-1}(P(z)-p_0-p_{1}z)=(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{array}{rl}& 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^{\mathrm{\infty }}(1-\rho ){\rho }^n\cdot z^n=\sum _0^{\mathrm{\infty }}{p}_n\cdot z^n\\ & \therefore p_n=(1-\rho ){\rho }^n\end{array}$$

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>1$$

用公式解遞迴（公式解以及其推導請參考離散數學相關課程及教材），base case 為

$p_1=\rho p_0$，以及

$\sum p_n=1$