# Discrete “M/M/1” queue

Consider a queueing system with one server, interarrival distribution ${\mathsf{Geo}\left(\lambda\right)}$, and service distribution ${\mathsf{Geo}\left(\mu\right)}$, where ${0<\lambda<\mu}$. This is the discrete analog of the ${M/M/1}$ queue. What can we say about its limiting behavior?

Let ${X_n}$ be the number of customers in the system at time ${n}$, then ${X=\{X_n:n=0,1,2,\ldots\}}$ is a Markov chain with transition probabilities

\displaystyle \begin{aligned} P_{0,1} &= 1\\ P_{n-1,n} &= \frac{\mu(1-\lambda)}{\lambda+\mu-\lambda\mu},\ n\geqslant1\\ P_{n,n} &= \frac{\lambda\mu}{\lambda+\mu-\lambda\mu},\ n\geqslant1\\ P_{n,n+1} &= \frac{\lambda(1-\mu)}{\lambda+\mu-\lambda\mu},\ n\geqslant1. \end{aligned}

Suppose ${\nu}$ is an invariant measure for ${P}$, that is, ${\nu P=\nu}$. A stationary distribution ${\pi}$ exists for ${X}$ iff ${V:=\sum_{n=0}^\infty \nu_n<\infty}$, in which case ${\pi=\nu/V}$. Assume WLOG that ${\nu_0=1}$, then the global balance equations are

\displaystyle \begin{aligned} \nu_0 &= \frac{\mu(1-\lambda)}{\lambda+\mu-\lambda\mu}\nu_1\\ \left(\frac{\lambda+\mu-2\lambda\mu}{\lambda+\mu-\lambda\mu}\right)\nu_1 &= \nu_0 + \left(\frac{\lambda(1-\mu)}{\lambda+\mu-\lambda\mu} \right)\nu_2\\ \left(\frac{\lambda+\mu-2\lambda\mu}{\lambda+\mu-\lambda\mu}\right)\nu_n &= \left(\frac{\mu(1-\lambda)}{\lambda+\mu-\lambda\mu} \right)\nu_{n-1}+\left(\frac{\lambda(1-\mu)}{\lambda+\mu-\lambda\mu} \right)\nu_{n+1},\ n\geqslant2.\\ \end{aligned}

It follows that

\displaystyle \begin{aligned} \nu_0 &= 1,\\ \nu_1 &= \frac{\lambda+\mu+\lambda\mu}{\mu(1-\lambda)},\\ \nu_{n+1} &= \left(\frac{\lambda+\mu-2\mu}{\mu(1-\lambda)}\right)\nu_n - \frac{\lambda(1-\mu)}{\mu(1-\lambda}\nu_{n-1},\ n\geqslant2. \end{aligned}

Let ${G(z) = \sum_{n=0}^\infty \nu_n z^n}$ be the generating function of ${\{\nu_n\}}$, then multiplying the recurrence by ${z^n}$ and summing over ${n}$ yields

$\displaystyle \sum_{n=2}^\infty \nu_{n+1}z^n = \left(\frac{\lambda+\mu-2\mu}{\mu(1-\lambda)}\right) \sum_{n=2}^\infty \nu_n z_n - \frac{\lambda(1-\mu)}{\mu(1-\lambda} \sum_{n=2}^\infty \nu_{n-1}z^n,$

so that

$\displaystyle \frac1z\left( G(z) - \nu_0 - \nu_1z - \nu_2z^2 \right) = \left(\frac{\lambda+\mu-2\mu}{\mu(1-\lambda)}\right)\left(G(z)-\nu_0-\nu_1z \right) -\left(\frac{\lambda(1-\mu)}{\mu(1-\lambda} \sum_{n=2}^\infty \nu_{n-1}z^n\right)\left(G(z)-\nu_0\right).$

Solving for ${G(z)}$, we have

$\displaystyle G(z) = \frac{\mu (1-\lambda-z)}{\mu(\lambda-1) +\lambda(1-\mu)z},$

from which it follows that

$\displaystyle \nu_n = \left(\frac{\lambda(1-\mu)}{\mu(1-\lambda)}\right)^n\left(\frac{\lambda+\mu-\lambda\mu}{\lambda(1-\mu)}\right),n\geqslant 2.$

We compute

\displaystyle \begin{aligned} \sum_{n=0}^\infty \nu_n &= \nu_0 + \nu_1 + \sum_{n=2}^\infty \nu_n\\ &= 1 + \frac{\lambda+\mu+\lambda\mu}{\mu(1-\lambda)} + \left(\frac{\lambda+\mu+\lambda\mu}{\mu(1-\lambda)}\right)\sum_{n=2}^\infty \left(\frac{\lambda(1-\mu)}{\mu(1-\lambda)}\right)^n\\ &= 1 + \frac{\lambda+\mu+\lambda\mu}{\mu(1-\lambda)} + \left(\frac{\lambda+\mu+\lambda\mu}{\mu(1-\lambda)}\right) + \frac{(1-\mu)(\lambda+\mu-\lambda\mu)^2}{(1-\lambda)(\mu-\lambda)\mu}\\ &= \frac{\mu(3-\mu)+\lambda(1-\mu(3-\mu))}{\mu-\lambda}, \end{aligned}

and hence

\displaystyle \begin{aligned} \pi_0 &= \frac{\mu-\lambda}{\mu(3-\mu)+\lambda(1-\mu(3-\mu))}\\ \pi_1 &= \frac{(\mu-\lambda)(\lambda+\mu-\lambda\mu)}{\mu(1-\lambda)(\mu(3-\mu)+\lambda(1-\mu(3-\mu)))}\\ \pi_n &= \left(\frac{(\mu-\lambda)(\lambda+\mu-\lambda\mu)}{\mu(1-\lambda)(\mu(3-\mu)+\lambda(1-\mu(3-\mu)))}\right)\left(\frac{\lambda(1-\mu)}{\mu(1-\lambda)}\right)^n,\ n\geqslant 2 \end{aligned}