23_Apr_04.md

Note 23 - April 4

Review

$$ \begin{aligned} &\text{Birth rates: }\lambda_i = R_{i,i+1}\quad\quad i=0,1,\cdots\ &\text{Death rates: }\mu_i = R_{i,i-1}\quad\quad i=1,2,\cdots \end{aligned}\

R=\begin{pmatrix} -\lambda_0 & \lambda_0 \ \mu_1&-(\lambda_1+\mu_1)&\lambda_1 \ & \mu_2&-(\lambda_2+\mu_2)&\lambda_2 \ &&\mu_3&-(\lambda_3+\mu_3)&\lambda_3 \\ &&\quad\quad\quad\ddots&\quad\quad\quad\ddots&\quad\quad\quad\ddots \end{pmatrix}\ \Rightarrow \begin{aligned} &R_{ii} =-(\lambda_i+\mu_i) \quad i\geq 1 \ &R_{00} =\lambda_0 \end{aligned} $$

6. Continuous-Time Markov Chain (cont'd)

6.5. Birth and Death Processes (cont'd)

As we see, there are two main types of birth and death processes: queueing system and population model. THe key difference between them is that the birth rate in the queueing system is typically a constant (does not depend on the current state $i$), while the birth rate in population model increases as $i$ increases.

6.5.1. Stationary Distribution of a Birth and Death Process

$$ \begin{cases} \underline{\pi}\cdot R = \underline{0}\quad (1)\\ \underline{\pi}\cdot 1!!!!\perp = \underline1 \quad (2)\\ \end{cases} $$

$$ (\pi_0,\pi_1,\cdots) \cdot \begin{pmatrix} -\lambda_0 & \lambda_0 \\ \mu_1 & -(\lambda_1+\mu_1)&\lambda_1\\ &\mu_2 & -(\lambda_2+\mu_2)&\lambda_2\\\ && \quad\quad\ddots& \quad\quad\ddots& \quad\quad\ddots \end{pmatrix} $$

$$ (1) \Rightarrow \begin{aligned} &-\lambda_0\pi_0+\mu_1\pi_1 = 0 \Rightarrow\pi_1=\frac{\lambda_0}{\mu_1}\pi_0\ &\lambda_0\pi_0-(\lambda_1+\mu_1)\mu_1+\mu_2\pi_2 = 0

\end{aligned} $$ Add this to the first equation, we have $$ -\lambda_1\pi_1+\mu_2\pi_2 = 0 \Rightarrow\pi_2=\frac{\lambda_1}{\mu_2}\pi_1 $$

In general, adding the first $i$ equations, we have $$ -\lambda_0\pi_0+\mu_1\pi_1= 0 $$ $$ \lambda_0\pi_0-(\lambda_1+\mu_1)\pi_1+\mu_2\pi_2=0 $$ $$ \vdots $$ $$ \lambda_{i-2}\pi_{i-2}-(\lambda_{i-1}+\mu_{i-1}+\mu_i\pi_i)=0 $$ $$ -\lambda_{i-1}\pi_{i-1}+\mu_i\pi_i=0 $$ $$ \begin{aligned} \Rightarrow \pi_i &= \frac{\lambda_{i-1}}{\mu_i}\pi_{i-1}\ &=\cdots\ &=\frac{\lambda_0\lambda_1\cdots\lambda_{i-1}}{\mu_1\mu_2\cdots\mu_i}\pi_0 \end{aligned} $$

Use $(2)$ to normalize $$ 1=\sum_{n=0}^\infty \pi_n = (1+\sum_{n=1}^{\infty}\Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j} $$ $$ \begin{aligned} \Rightarrow &\pi_0=\frac{1}{1+\sum_{n=1}^\infty\Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j}}\ &\pi_i=\frac{\Pi_{j=1}^i\frac{\lambda_{j-1}}{\mu_j}}{1+\sum_{n=1}^\infty\Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j}} \end{aligned} $$

Thus, a stationary distribution exists(the MC is positive recurrent, assuming irreducible) if and only if $$ \sum_{n=1}^\infty\Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j } < \infty $$

Example 6.5.1.1. M/M/S Queue (cont'd)

$$ \lambda_i = \lambda\quad\quad\mu_i=\begin{cases} i\mu\quad i\leq s \\ s\mu\quad i>s \end{cases} $$

$$ \begin{aligned} &\sum_{n=1}^\infty \Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j}\\ &= \underbrace{\frac{\lambda}{\mu}+\frac{\lambda}{\mu}\cdot\frac{\lambda}{2\mu}+\cdots+\frac{\lambda}{\mu}\frac{\lambda}{2\mu}\cdots\frac{\lambda}{s\mu} + \frac{\lambda}{\mu}\frac{\lambda}{2\mu}\cdots(\frac{\lambda}{s\mu})^2+\frac{\lambda}{\mu}\frac{\lambda}{2\mu}\cdots(\frac{\lambda}{s\mu})^3+\cdots}_{\text{geometric series with ration $\frac{\lambda}{s\mu}$}} \end{aligned} $$

$\Rightarrow$ The sum is finite if and only if $\lambda&lt;s\mu$

$\Rightarrow$ the process ${X(t)}{t\geq 0}$ is positive recurrent if and only if $\underbrace{\lambda}{\text{arrival rate}} < \underbrace{s\mu}_{\text{maximal (total) service rate}}$

Example 6.5.1.2. Population Model (with immigration)

$$ \lambda_i=i\lambda+\alpha\quad\quad\mu_i=i\mu $$

$$ \sum_{n=1}^\infty \Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j} = \sum_{n=1}^\infty\Pi_{j=1}^n\frac{(j-1)\lambda+\alpha}{j\mu} $$ $$ \lim_{j\rightarrow\infty}\frac{(j-1)\lambda+\alpha}{j\mu}=\frac{\lambda}{\mu} $$ If $\lambda&lt;\mu$, then $\quad\sum_{n=1}^\infty\Pi_{j=1}^n\frac{(j-1)\lambda+\alpha}{j\mu}&lt;\infty$ by ratio test.

If $\lambda&gt;\mu$, then $\quad\sum_{n=1}^\infty\Pi_{j=1}^n\frac{(j-1)\lambda+\alpha}{j\mu}=\infty$.

If $\lambda=\mu$, then $\quad\alpha \geq \lambda =\mu$, the ratio $\frac{(j-1)\lambda+\alpha}{j\mu}\geq 1$ for all $j$

$\Rightarrow$ the terms in the summation is non-decreasing

$\Rightarrow$ the $sum = \infty$

If $\lambda=\mu,\quad \alpha &lt;\lambda = \mu$：

Raabe-Duhamel's test: (not required content) $$ L:=\lim_{n\rightarrow\infty} n(\frac{a_n}{a_{n+1}}-1)\begin{cases} >1\quad\text{converge}\ <1\quad\text{diverge}\ =1\quad\text{inconclusive}\ \end{cases} $$

Here: $$ \begin{aligned} L&=\lim_{n\rightarrow\infty}n(\frac{n\mu}{(n-1)\lambda+\alpha})\ &=\lim_{n\rightarrow\infty}n(\frac{n\lambda-(n-1)\lambda-\alpha}{(n-1)\lambda+\alpha})\ &=\lim_{n\rightarrow\infty}n(\frac{\lambda-\alpha}{(n-1)\lambda+\alpha})\ &=\frac{\lambda-\alpha}{\lambda} <1 \end{aligned} $$ $\Rightarrow$ the sum $=\infty$

Conclusion

To sum up, the CTMC is positive recurrent if and only if $\lambda&lt;\mu$

Q: What happens if $\lambda_0=0$? (0 is absorbing)

A:

The chain is not irreducible; typically two classes:

• ${0}\quad\quad\quad\quad\quad$ positive recurrent
• ${1,2,\cdots}\quad \text{ }\text{ }\quad$transient

But the chain does not necessarily end up with being in state $0$, because it can also have $X(t)\rightarrow\infty$. Whether this is a possibility depends on the relation between ${\lambda_i}$ and ${\mu_i}$.