From Markov Chains to the M/M/1 Queue

While I was learning about queueing systems, I was presented with the M/M/1 queue and its formulas. I knew that the M/M/1 queue came from Markov chains, and that the M stood for a Markovian process, and I knew a little about Markov chains too — but the connection between them was never clear.

I spent some time learning about it, and this article is the result. We will go from the introduction of Markov chains all the way to the derivation of the M/M/1 queue.

Introduction to Markov Chains

We will take one example of a service center and build up on that.

In our example, let us assume that in each time frame (say 1 minute) there is a probability that a new customer will show up, and a probability that one customer service call will be completed. (Bernoulli processes.)

And suppose our service center only has 5 computers, so we can only have that many customers at a time. It can be represented as below. Each circle is a state showing how many customers we have in our system right now. We have 6 states because that's all we can have with 5 computers; there can be either 0 customers at any time, or one, or two, and so on up to five customers.

A six-state Markov chain for the service center, with p-prime arcs forward, q-prime arcs back, and r-prime self loops

It also shows how we can move from one state to another.

We can only move from state to if a new customer arrived and no customer left in that time. From our known probabilities, the probability of that happening is

Similarly, we can only move from state to state if a customer finished and no new one arrived at that time. So the probability of that happening is

And to stay in the same state, either someone has to come and another one has to go, or no one can come or go. So the probability of that happening is the probability of one leaving and one coming, plus the probability of no one coming and no one going:

Summing all of these probabilities results in 1.

This is the Markov chain that models our service center.

With all this said, let us cover some terminology, and then we will connect it back to this example.

Analysis of a Markov Chain

What makes the above model a Markov chain? It qualifies as a Markov chain because it does not depend on the past.

You can be completely blind about your past and about how you reached your current state. All you know is that you can either go to the next state with some probability, or go back, or stay where you are.

What it is saying is that the conditional probability of being in state given that we are in state is the same as the conditional probability of being in given the complete path from to . This shows that all the information about your previous states is useless, and that all that determines your probability of being in the next state is your current state.

Now, we can also define the probability that you go from state to state in steps as

Initially we are at state . In steps we can be in any state to (given that we have states). The probability of being in state in steps is , and the probability of moving from that state to is . Doing that for every possible , we get .

That's the recursive formula for , with base case

If the process starts in state , then after zero moves it remains in state with probability 1. Therefore the probability of being in any different state after zero moves is 0.

We can also define it the other way around:

This is just the other representation of the previous result: the probability of going from to in the next move, and then the summation over all the paths that reach from .

We will use the results above to solve a simple example. Suppose we have a Markov chain with two states, and , with the following transition probabilities.

A two-state Markov chain with transition probabilities 0.5, 0.5, 0.2 and 0.8

The transition probability matrix is

Let denote the probability of being in state after steps, given that the process started in state .

The transition probabilities for different values of are illustrated in the following table:

For example, to calculate , we consider all possible paths that start in state and return to state after two steps. There are two such paths:

Therefore,

Similarly, the other two-step transition probabilities can be calculated by considering all possible paths of length two.

We observe a remarkable pattern: as increases, the transition probabilities converge to fixed values. In particular,

Thus, regardless of whether the process starts in state or state , the probability of being in state approaches , while the probability of being in state approaches .

These limiting probabilities are called the stationary probabilities, denoted by .

This observation raises a natural question.

Does this convergence occur for every Markov chain? In other words, is it always true that

for every pair of states and , where the limiting probability is independent of the initial state ?

It depends. It depends on the Markov chain. If all recurrent states belong to a single recurrent class, and this class is not periodic, then the transition probabilities converge to a limiting distribution, under the usual finite-state assumptions.

We will not discuss recurrent states, recurrent classes, or periodicity in detail here, but these concepts are not too difficult to understand.

If the transition probabilities converge, we can derive equations for the limiting probabilities.

We already know:

Taking the limit as , we obtain

Since as , we have

Therefore,

These equations give us one equation for each state . In addition, the probabilities must satisfy the normalization condition

since the total probability of being in any state must equal 1.

Thus, by solving this system of equations, we can determine the steady-state probabilities .

Birth-Death Process

We will now finally return to our old customer service example and give it a name. This kind of process is called a birth-death process.

It is simple: either there can be one birth and we move to the next state, one death and we move to the previous state, or we stay in our current state.

A general birth-death chain with birth probabilities p_i forward and death probabilities q_i backward

Let us analyse this birth-death process, since it will be used directly for our M/M/1 queue.

First, let us pick one section of this chain:

Two neighbouring states i and i+1, with p_i going forward and q_i+1 coming back

If the process runs long enough and reaches a steady state (birth-death processes satisfy the conditions on recurrent states and periodicity mentioned earlier), there must be a balance between the flow into and out of each state.

Why? It balances out. For example, if is smaller and is greater (just like in a stable queue), then we are more likely to find ourselves in state than in state :

The probability of a transition from state to state is

Similarly, the probability of a transition from state to state is

Now we can see that, in the first case, is greater but is smaller. In the second case, is smaller but is greater.

These balance out, and we get

Therefore,

We can simplify our model further by assuming that and for all states. Thus,

Rearranging, we get

Therefore,

and

So, in general, letting

we get

We know that the sum of all steady-state probabilities must equal :

Substituting the expressions above, we obtain

Therefore,

where the denominator is the sum of a geometric series.

The M/M/1 Queue

For an M/M/1 queue, we suppose that the queue length is infinite. That is, we let .

For a stable queue we have , and therefore

We know that the sum of a geometric series is

Therefore,

Recall that . Substituting , we obtain

Now, in an M/M/1 queue, both the arrival process and the service process are assumed to be Poisson processes. Equivalently, the interarrival times and service times follow exponential distributions.

For an exponential distribution with rate , the probability density function (PDF) is

The cumulative distribution function (CDF) is

The hazard rate is defined as

Here, the hazard rate represents the instantaneous rate at which the event occurs, given that it has not occurred before time .

For the exponential distribution, we obtain

Thus the hazard rate is constant. This is exactly the memoryless property of the exponential distribution: the probability of an event occurring within the next time interval does not depend on how long we have already waited.

Therefore, if arrivals follow a Poisson process with rate arrivals per unit time, then over a small interval the probability of an arrival is

Similarly, if the service process completes services at rate per unit time, then the probability of a departure is

and so , since the cancels.

With these probabilities, we get something like this. From state , at time , we can reach state , or , or state .

From state n at time t, the chain reaches n+1, n, or n-1 at time t plus delta t

And in a more general view:

The M/M/1 chain with probability flow pi_n lambda delta t forward and pi_n mu delta t backward

Finally, it's time to derive the other queue parameters.

where is the expected number of customers in the system.

where is the average time a customer spends in the system.

From Little's law, .

where is the average time a customer spends waiting in the queue.

where is the expected number of customers waiting in the queue.

Why just the M/M/1 queue? Why not others?

If you look at what we did, we used the memoryless property of the exponential distribution to define the probabilities of the birth-death process.

That property is really what made the whole thing work. Because the hazard rate is constant, every jump has a fixed probability, no matter how long the system had already been sitting in its current state.

So the method is not tied to M/M/1 at all. As long as the process stays Markovian, we can reuse it.

Take the M/M/3 queue, where we have 3 servers instead of 1:

The M/M/3 chain, where the departure rate grows as mu, 2 mu, 3 mu and then saturates at 3 mu

The only thing that changed is the backward probability. With more than one server, more than one customer can be served at a time, so departures get faster until every server is busy.

In state , the number of busy servers is , so the total departure rate is

The local balance equation between neighbouring states is the same one we derived before, just with in place of a constant :

Starting at state zero,

In general,

Now take away the exponential service time.

If the hazard rate is not constant — which is true for any general distribution — then we can't simply know whether a customer will arrive or finish just from the condition of our queue. The probability that the current service finishes in the next instant now depends on how long that service has already been running.

At that point you need a different tool. For example, in this video, he used a triangle method. (I am plugging this video here to suggest that you should watch it, it is a good talk on this subject)