A discrete-time single-server queue

Many queues can be modeled as discrete-time Markov chains. Here, the state is the length of the queue, and fluctuations in arrivals and service give the random evolution from one time period to the next. Here is a diagram of a queue.

Figure: arrivals occur from the left and are stored in a buffer. Jobs or customers are represented as rectangles. A server is represented by a circle, which processes the jobs, and they then depart on the right-hand side.

Here is a simple discrete-time model. Suppose that at each time step there is probability \lambda of one arrival and no departure, and, if the queue is not empty, probability \mu of one departure and no arrival. Otherwise, the queue remains unchanged at the next time step.

The transition probabilities of this Markov chain are as follows:

\displaystyle \text{for } x > 0,\qquad P_{xy} = \left\{ \begin{array}{ll} \lambda, & \text{for } y = x+1, \\ \mu, & \text{for } y = x-1, \\ 1-\lambda-\mu, & \text{for } y = x, \\ 0, & \text{otherwise}, \end{array} \right. \qquad \text{and} \qquad P_{0y} = \left\{ \begin{array}{ll} \lambda, & \text{for } y = 1, \\ 1-\lambda, & \text{for } y = 0, \\ 0, & \text{otherwise}. \end{array} \right.

Another way to represent the Markov chain is as follows.

Figure: the different states are drawn as circles, and arrows connect the non-trivial transitions.

Here are a couple of simple questions that we will answer:

  1. Will the queue always empty?
  2. Does the queue stay bounded?
  3. If it does, how long does it spend in each state?

You can probably guess part of the answer: clearly, if \lambda > \mu, then the queue is more likely to increase than decrease. So we do not expect the queue to stay bounded. However, if \mu > \lambda, we should expect the queue to empty frequently. We now work towards formalizing this, although for brevity we will not provide many proofs.

Leave a comment