From BoykinWiki

EEL6507 Spring 2009, Lecture 11, Monday 2009/02/02 (Notes created by Dexiang Wang)

Pure Birth Process
Steady State of Birth-Death Process
M/M/I Queue

General derivative representation of birth-death process

$\begin{align} \frac{dP_k(t)}{dt}&=[\lambda_{k-1}P_{k-1}(t)+\mu_{k+1}P_{k+1}(t)]-(\lambda_{k}+\mu_{k})P_{k}(t)\\ &=Flow_{in}-Flow_{out} \end{align}$

Pure-birth process $(\mu_{k}=0,\ \lambda_{k}=\lambda)$

Now, the general derivative representation turns to be:

$\frac{dP_k\left(t\right)}{dt}=\lambda[P_{k-1}(t)-P_{k}(t)]$

By introducing Z-transform of $P_{k}\left(t\right)$

$P(z,t)=\sum_{k=0}^{\infin} P_{k}(t)z^k$

and applying Z-transform to both sides of above derivative equation, we have:

$\begin{align} \frac{\partial P(z,t)}{\partial t}&=\lambda(\sum_{k=0}^{\infin} z^k P_{k-1}(t)-P(z,t))\\ &=\lambda(\sum_{k=1}^{\infin} z^k P_{k-1}(t)-P(z,t)) \\ &=\lambda(z\sum_{k=1}^{\infin} z^{k-1} P_{k-1}(t)-P(z,t)) \\ &=\lambda(z-1)P(z,t) \end{align}$

Since $\lambda\left(z-1\right)$ is a constant with regard to $\ t$ , above equation becomes a first-order constant-coefficient derivative equation and its solution is:

$P(z,t)=Ae^{\lambda\left(z-1\right)t}$

We can obtain the value of $\ A$ by evaluating $P\left(z,t\right)$ at $\ z=1$ :

$\begin{align} A&=P\left(1,t\right)\\ &=\sum_k P_k(t) \\ &=1 \end{align}$

So

$P(z,t)=e^{\lambda\left(z-1\right)t}$

Without need to obtain $P_k\left(t\right)$ , we can easily find expectation of $K\left(t\right)$ as follow:

$\begin{align} <K(t)>&=\sum_{k=0}^{\infin}kP_k(t)\\ &=\frac{\partial P(z,t)}{\partial z}\big |_{z=1} \\ &=\lambda tP(z,t)\big |_{z=1}\\ &=\lambda t \end{align}$

This makes our common sense because average population at time $\ t$ should be the product of birth rate and total time.

Finally we want to obtain $\ P_k(t)$

Applying Taylor expansion onto $\ P(z,t)$ , we have:

$\begin{align} P(z,t)&=e^{\lambda(z-1)t}\\ &=e^{-\lambda t}e^{\lambda zt}\\ &=e^{-\lambda t}\sum_{k=0}^{\infin} \frac{(\lambda t)^k}{k!}z^k \end{align}$

hence,

$P_k(t)=e^{-\lambda t}\frac{(\lambda t)^k}{k!}$

which is called "Poisson distribution"

Equilibrium (steady state) birth-death process

Define: $\lim_{t\rightarrow \infin}P_k(t)=P_k$

Equilibrium property: $\lim_{t\rightarrow \infin}P_{k}'(t)=0$

So,

$\lim_{t\to \infin}\frac{dP_k(t)}{dt}=\lambda_{k-1}P_{k-1}+\mu_{k+1}P_{k+1}-(\lambda_k+\mu_k)P_k=0$ $\Rightarrow\ \lambda_{k-1}P_{k-1}-\mu_k P_k=\lambda_k P_k-\mu_{k+1}P_{k+1}$

Define $\ g_{k}=\lambda_k P_k-\mu_{k+1}P_{k+1}$ ,

hence we have:

$\ g_0=g_1=...=g_k=g=constant$

Consider the state "0", the flow-in probability should equal flow-out probability and hence $\ \lambda_0 P_0-\mu_1 P_1=g_0=0$

So,

$\ g_0=g_1=...=g_k=0$

and

$\ \lambda_{k}P_{k}-\mu_{k+1} P_{k+1}=0$ $\frac{\lambda_{k}}{\mu_{k+1}}=\frac{P_{k+1}}{P_{k}}$

Eventually we can obtain $\ P_n$ in the following way:

$\prod_{k=0}^{n-1} \frac{P_{k+1}}{P_{k}}=\frac{P_n}{P_0}=\prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}$ $\Rightarrow\ P_n=P_0 \prod_{k=0}^{n-1}\frac{\lambda_k}{\mu_{k+1}}$