EEL6507sp09L21

From BoykinWiki

Jump to: navigation, search

Contents


EEL6507 Spring 2009, Lecture 21, Friday 2009/02/27 (Notes created by Vishnu Vijayakumar)

  • Finish M / E_r / 1\!

M / Er / 1

State-transition-rate diagram for an r-stage erlangian markovian process (Image by Gustavo Vejarano)
State-transition-rate diagram for an r-stage erlangian markovian process (Image by Gustavo Vejarano)

The steady state probabilities for the different states are as follows:

P_k = 0\ \text{if}\ k<-1

Equating the probability flow in and out of the states,

\lambda P_{-1} = r \mu P_0\!

(\lambda + r \mu)P_k = \lambda P_{k-r}+r \mu P_{k+1} \forall k \ge 0

Note: P_{k-r}=0\ \text{if}\ k-r < -1\ \text{or}\ k < r-1


Let us define the Z-Transform as:

P(z) = \sum_{k=0}^\infty P_{k-1} z^k

Taking the Z-Transform on the above equations:

\begin{align} (\lambda + r\mu)(P(z)-P_{-1}) &= \lambda \sum_{k=0}^\infty P_{k-r-1}z^k + r\mu \sum_{k=1}^\infty P_k z^k\\ &= \lambda \sum_{k=0}^\infty P_{k-r-1}z^k + r\mu \frac{1}{z}\sum_{k=1}^\infty P_k z^{k+1}\\ &= \lambda \sum_{k=0}^\infty P_{k-r-1}z^k + r\mu \frac{1}{z}(P(z)-P_{-1}-P_0 z)\\ \end{align}
\sum_{k=0}^\infty P_{k-r-1}z^k = \underbrace{ P_{-r-1}z^0 + P_{-r}z+P_{1-r}z^2+\cdots+P_{r-2-r}z^{r-1} }_{=0}+P_{r-1-r}z^r + P_{r-r}z^{r+1}+\cdots

\begin{align} \ \Rightarrow \sum_{k=0}^\infty z^k &= z^r[P_{-1}+P_0z+P_1z^2+\cdots]\\ &= z^rP(z) \end{align}

\Rightarrow (\lambda +r\mu)[P(z)-P_{-1}] = \lambda z^r P(z) + r\mu (\frac{P(z)-P_{-1}-zP_0}{z})

\Rightarrow (\lambda +r\mu)P(z)-\lambda z^r P(z)-\frac{r\mu}{z} P(z) = (\lambda + r\mu)P_{-1}-\frac{r\mu}{z}(P_{-1}+P_0z)

\Rightarrow P(z) = \frac{(\lambda + r\mu)P_{-1}-\frac{r\mu}{z}(P_{-1}+P_0 z)}{(\lambda+r\mu)-\lambda z^r - \frac{r\mu}{z}}

Now, we can write P_0\! in terms of P_{-1}\!

λP − 1 = rμP0

P_0 = \frac{\lambda}{r\mu}P_{-1}

\Rightarrow P(z)= \frac{((\lambda +r\mu)z-r\mu (1+\frac{\lambda}{r\mu}z))}{(\lambda +r\mu)z-\lambda z^{r+1}-r\mu}

\color{Red} \Rightarrow P(z)= \frac{P_{-1}r\mu (z-1)}{(\lambda +r\mu)z-\lambda z^{r+1}-r\mu}

Now, we need to find P_{-1}\,\!.

We can find the value of P_{-1}\,\! using the fact that \lim_{z \to 1}P(z) = 1\ \Rightarrow \sum_{k=-1}^\infty P_k = 1

By L'Hospital's rule:

\begin{align} \lim_{z \to 1}P(z) &= \lim_{z \to 1} \frac{P_{-1}(r\mu)}{(\lambda + r\mu)-\lambda(r+1)z^r}\\ &= \frac{P_{-1}(r\mu)}{(\lambda + r\mu)-(r+1)\lambda} = \frac{P_{-1}r\mu}{r(\mu-\lambda)} = 1\\ &\Rightarrow P_{-1} = \frac{\mu-\lambda}{\mu} = 1 - \frac{\lambda}{\mu} \end{align}

If we define \rho = \frac{\lambda}{\mu}\!, P_{-1}=P[\text{empty}]=1-\rho\!

Substituting for P_{-1}\! in the equation for P(z)\!,

\begin{align} P(z) &= \frac{(1-\rho)r(z-1)}{(\rho +r)z-\rho z^{r+1}-r}\\ &= \frac{(1-\rho)r(z-1)}{\rho (z-z^{r+1})+r(z-1)}\\ &= \frac{(1-\rho)r}{\rho\frac{z-z^{r+1}}{z-1}+r}\\ &= \frac{(1-\rho)r}{-\rho\sum_{k=1}^r z^k +r} = \frac{(1-\rho)r}{r-\rho\sum_{k=1}^r z^k} \end{align}

\color{Red} \Rightarrow P_r(z) = \frac{(1-\rho)}{1-\frac{\rho}{r}\sum_{k=1}^{n}z^k}

If r = 1 (ie. for an M/M/1 service),

P_1(z) = \frac{1-\rho}{1-\rho z}\ \Rightarrow \ P_k = (1-\rho)\rho^k

If r = 2 (ie. 2-stage service),

P_2(z) = \frac{1-\rho}{1-\frac{\rho}{2}(z+z^2)}

Let Z_0\!, Z_1\! be the roots of the denominator.

\begin{align} P_2(z) &= \frac{1-\rho}{(1-\frac{z}{z_0})(1-\frac{z}{z_1})}\\ &= \frac{A_0 (1-\rho)}{1-\frac{z}{z_0}} + \frac{A_1 (1-\rho)}{1-\frac{z}{z_1}}\\ &= (1-\rho)\lbrack A_0 \sum_{k=0}^\infty z^k \frac{1}{z_0^k} + A_1 \sum_{k=0}^\infty z^k \frac{1}{z_1^k}\rbrack \end{align}

\Rightarrow P_{k-1} = (1-\rho)[A_0 \frac{1}{z_0^k}+A_1 \frac{1}{z_1^k}]

In general,

P_r(z) = \frac{1-\rho}{1-\frac{\rho}{r}(z+z^2+\cdots +z^r)}

Finding the roots of the denominator,

P_r(z) = \frac{1-\rho}{(1-\frac{z}{z_1})(1-\frac{z}{z_2})\cdots (1-\frac{z}{z_r})}

Using Partial Fractions,

\begin{align} P_r(z) &= (1-\rho) \sum_{i=1}^r \frac{A_i}{(1-\frac{z}{z_i})}\\ &= (1-\rho)\sum_{i=1}^r A_i \sum_{k=0}^\infty z^k \frac{1}{z_i^k}\\ \Rightarrow P_{k-1} &= (1-\rho)\sum_{i=1}^{r}A_i z_i^{-k}\\ \end{align}

Lecture Voice Recording

lecture_recording

Retrieved from "http://boykin.acis.ufl.edu/wiki/index.php/EEL6507sp09L21"