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)<p_\mu(1-p_\lambda).

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)}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s