# Discrete-time queue (Geo/Geo/1)

Queueing theory is generally introduced in the continuous-time setting, with the fundamental ${M/M/1}$ queue for which many analytical results may be obtained with relatively straightforward computations, due largely to the memoryless property of the exponential distribution. In the next few posts I will analyze the discrete-time analog of this model; namely, a single-server queue with *geomentric* interarrival and service times.

Suppose customers arrive to a queue according to a Bernoulli process; that is, at each time ${n=1,2,\ldots}$, a customer arrives with probability ${p_\lambda}$, independent of past or future arrivals. The probability that a customer finishes service at time ${n+1}$, conditioned on that customer having been in service at time ${n}$, is ${p_\mu}$. Let ${\{A_m : m=1,2,\ldots\}}$ be the arrival process and ${\{D_m : m=1,2,\ldots\}}$ the departure process. The interarrival times are ${T_m:=A_m-A_{m-1}}$, with ${A_0\equiv 0}$. Conditioned on ${A_{m-1}=i}$, we have ${\mathbb P(A_m=i+j)=\mathbb P(T_m=j)=(1-p_\lambda)^{j-1}p_{\lambda}}$, and so by independence of arrivals, the ${T_m}$ are i.i.d. ${\mathsf{Geo}(p_\lambda)}$ random variables. A similar argument shows that the service times are i.i.d. ${\mathsf{Geo}(p_\mu)}$ random variables.

Let ${\{Z_n:n=0,1,2,\ldots\}}$ be the number of customers in the system at time ${n}$, after arrivals and before departures. It follows from the memoryless property of the geometric distribution that ${Z_n}$ is a Markov chain; that is, for any nonnegative integers ${n}$, ${i}$, and ${j}$ and any ${E\in\sigma\left(\bigcup_{k=0}^n Z_k\right)}$, we have

$\displaystyle \mathbb P(Z_{n+1} = j\mid Z_n=i, E) = \mathbb P(Z_{n+1}=j\mid Z_n=i).$

At each time ${n}$, at most one customer can arrive and at most one customer can depart. It follows that ${Z_n}$ is a birth-death chain, with transition probabilities given by

$\displaystyle p(i,j) = \begin{cases} 1-p_\lambda,& i=j=0\\ p_\lambda,& i=0, j=1\\ p_\mu(1-p_\lambda),& j=i-1\\ p_\lambda(1-p_\mu),& j=i+1, i>0\\ p_\lambda p_\mu + (1-p_\lambda)(1-p_\mu),& i=j>0. \end{cases}$

Suppose ${\nu}$ is an invariant measure for the transition matrix ${P}$, that is ${\nu = \nu P}$. Assume WLOG that ${\nu_0=1}$, then ${\nu_1 = \frac{p_\lambda}{p_\mu(1-p_\lambda)}}$ and

$\displaystyle \nu_n = \left(\frac{p_\lambda(1-p_\mu)}{p_\mu(1-p_\lambda)}\right)\nu_{n-1},\ n\geqslant2.$

By inspection, this recurrence has solution

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

Now, ${\{Z_n\}}$ is positive recurrent iff ${\sum_{n=0}^\infty \nu_n<\infty}$, which is true precisely when

$\displaystyle p_\lambda(1-p_\mu)

The offered load to the system is then

$\displaystyle \rho := \frac{p_\lambda(1-p_\mu)}{p_\mu(1-p_\lambda)}.$

Assuming ${\rho<1}$, let ${C=\sum_{n=0}^\infty \nu_n}$ and define ${\pi=C^{-1}\nu}$. By construction, ${\pi = \pi P}$ and ${\sum_{n=0}^\infty \pi_n=1}$, so that ${\pi}$ is the (unique) stationary distribution of ${\{Z_n\}}$. A straightforward computation yields

\displaystyle \begin{aligned} \pi_0 &= \frac{p_\mu-p_\lambda}{p_\mu}\\ \pi_n &= \rho^{n-1}\left(\frac{p_\lambda(1-\rho)}{p_\mu}\right),\ n\geqslant1. \end{aligned}

The limiting mean number of customers in the system ${L}$ is given by

\displaystyle \begin{aligned} L &= \sum_{n=1}^\infty n\pi_n\\ &= \left(\frac{p_\lambda(1-\rho)}{p_\mu}\right)\sum_{n=1}^\infty n\rho^{n-1}\\ &= \frac{p_\lambda}{p_\mu(1-\rho)}. \end{aligned}

Invoking Little’s Law, we compute the mean sojourn time of customers by

$\displaystyle W = \frac L{p_\lambda} = \frac1{p_\mu(1-\rho)}.$