Queueing theory is generally introduced in the continuous-time setting, with the fundamental 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 , a customer arrives with probability , independent of past or future arrivals. The probability that a customer finishes service at time , conditioned on that customer having been in service at time , is . Let be the arrival process and the departure process. The interarrival times are , with . Conditioned on , we have , and so by independence of arrivals, the are i.i.d. random variables. A similar argument shows that the service times are i.i.d. random variables.

Let be the number of customers in the system at time , after arrivals and before departures. It follows from the memoryless property of the geometric distribution that is a Markov chain; that is, for any nonnegative integers , , and and any , we have

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

Suppose is an invariant measure for the transition matrix , that is . Assume WLOG that , then and

By inspection, this recurrence has solution

Now, is positive recurrent iff , which is true precisely when

The offered load to the system is then

Assuming , let and define . By construction, and , so that is the (unique) stationary distribution of . A straightforward computation yields

The limiting mean number of customers in the system is given by

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