To the Bedrock
Flow & Queuing

Appendix: M/M/1 Derivation

This appendix derives W = 1 / (μ − λ) from the arrival and service distributions, a Markov chain, and Little's Law. Equations are numbered, with links from the text for cross-reference.

The two M's in M/M/1 name the distributions: the first for Markovian (Poisson) arrivals, the second for Markovian (exponential) service times. The 1 designates a single server. The model also assumes independent arrivals and service times, an infinite waiting room, no lost arrivals, a work-conserving single server, and stability: λ < μ. Each assumption does specific work in the argument.

The arrival process

A homogeneous Poisson process has stationary independent increments: counts in disjoint time intervals are independent, and the distribution of a count depends only on the interval length. In any interval of length t, the number of arrivals N(t) follows the Poisson distribution with mean λt, for t ≥ 0 and λ > 0.

(1)

A direct consequence of (1) is that the waiting times between successive arrivals, the interarrival gaps, follow the exponential distribution. If arrivals are Poisson with rate λ, the time until the next arrival has probability density:

(2)

The mean interarrival time under (2) is 1 / λ.

Poisson arrivals on a time axis and the exponential interarrival distribution Arrival process t t₁ Interarrival time distribution: Eq. (2) t f_T(t)
Top: a realisation of a Poisson arrival process on a time axis; ticks mark arrivals and the gap t1 is one interarrival interval. Bottom: the exponential density (2) that governs those gaps; the density is highest near zero because short interarrival times are the most probable.

Service times and the memoryless property

Service times in M/M/1 also follow the exponential distribution, with rate parameter μ and mean 1 / μ:

(3)

The exponential distribution is the only continuous distribution that is memoryless. If a service has already lasted time s, the remaining service time has the same distribution as if service had just started:

(4)
Exponential service time density and the shifted residual-time density Original density Residual time after conditioning s f_S(s) s₀ u f_R(u) R = S - s₀ | S > s₀
Left: the original exponential density from (3), with the tail after s0 highlighted. Right: after conditioning on survival past s0, shifting the remaining time back to zero gives the same exponential density for the residual variable R. That is the memoryless property (4).

The memoryless property (4) is essential for what follows. Because the server’s remaining workload at any moment is independent of how long it has been working, the system’s future evolution depends only on the current number of customers in the system, not on any history. That is precisely the Markov property.

PASTA: Poisson arrivals see time averages

An arriving customer may see a different queue from the one observed at an arbitrary time. Strategic or correlated arrivals can favour times when queues are short or long. Poisson arrivals have a useful property here.

PASTA (Poisson Arrivals See Time Averages) is the theorem that the fraction of Poisson arrivals who find the system in state n equals the long-run fraction of time the system spends in state n. Let πn be the steady-state probability of n customers in the system, and Pa(n) the probability an arriving customer finds n:

(5)

PASTA (5) is what makes the steady-state probabilities we derive next directly interpretable as arrival-epoch state probabilities. Waiting-time quantities still follow from the service discipline and the state seen by an arrival. Without PASTA we would need a separate calculation for what arriving customers see.

The birth-death chain

With Poisson arrivals and exponential service times, the system state, the number of customers present (including any in service), evolves as a continuous-time Markov chain. From state n the next event is either an arrival (at rate λ, moving to n + 1) or a service completion (at rate μ, moving to n − 1, provided n > 0). Chains where transitions move only one step up or one step down are called birth-death chains.

Birth-death Markov chain: states 0, 1, 2, 3, … connected by forward transitions at rate λ and backward transitions at rate μ 0 1 2 3 … λ λ λ μ μ μ
The birth-death chain for M/M/1. Each state is the number of customers in the system. Forward transitions (arrivals at rate λ) move the chain up by one; backward transitions (service completions at rate μ) move it down by one. State 0 has no backward transition.

Balance equations

In steady state the probability of being in each state does not change over time. For a birth-death chain this requires that the rate of probability flow across any cut between adjacent states must balance in both directions. This is the detailed balance condition:

(6)

Rearranging (6) gives a one-step recursion. Writing ρ = λ / μ:

(7)

Steady-state distribution

To find π0, apply the normalization condition: probabilities must sum to one. Substituting the recursion (7):

∑n=0∞ πn  =  π0 ∑n=0∞ ρn  =  π0 / (1 − ρ)  =  1,   so   π0 = 1 − ρ.

(The geometric series converges only when ρ < 1, which is the stability condition λ < μ. When ρ ≥ 1, arrivals outpace service and the queue grows without bound.)

(8)

Thus the time-average state distribution is geometric. By PASTA (5), this is also the state distribution seen at Poisson arrival epochs.

From distribution to L, W, and Wq

With the distribution (8) in hand, compute the average number of customers in the system by weighting each state by its probability:

L  =  ∑n=0∞ n πn  =  (1 − ρ) ∑n=0∞ nρn  =  (1 − ρ) · ρ / (1 − ρ)2. The final step uses the standard identity ∑ nρn = ρ / (1 − ρ)2.

(9)

Little’s Law, L = λW, then gives average lead time immediately:

(10)

The denominator μ − λ collapses toward zero as λ approaches μ, producing the hyperbolic growth described in Flow and Waiting.

The time spent waiting in queue (excluding service) follows by subtracting the mean service time:

(11)

The nonlinear growth in total time appears entirely in the queueing component: W = Wq + 1 / μ, while the mean service time remains fixed.

The formula in context

Poisson arrivals give exponential interarrival times (2). Together with memoryless service times (4), they give the Markov property. Detailed balance (6) and normalization yield the geometric distribution (8), which PASTA (5) also relates to arriving customers. Little’s Law then gives lead time (10).

The (1 − ρ) in the denominator of (9) comes from normalizing the geometric distribution. It accounts for the nonlinear growth as utilization rises.

Return to Flow and Waiting to see how the formula is used, or to Explore to vary the parameters interactively.

References

  • Kleinrock, L. (1975). Queueing Systems, Volume 1: Theory. Wiley. Chapters 2–3.
  • Wolff, R. W. (1982). Poisson Arrivals See Time Averages. Operations Research, 30(2), 223–231.
  • Gross, D., & Harris, C. M. (1998). Fundamentals of Queueing Theory (3rd ed.). Wiley. Chapter 2.
  • Little, J. D. C. (1961). A Proof for the Queuing Formula: L = λW. Operations Research, 9(3), 383–387.