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