To the Bedrock
Flow & Queuing

Appendix: M/M/1 Derivation

The M/M/1 result W = 1 / (μ − λ) is not postulated. It follows from two distributional choices, a Markov chain argument, and a single counting identity. This appendix traces that path from first principles. Equations are numbered for cross-reference; text references link back to the relevant formula.

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

Before deriving the steady-state distribution, a subtlety deserves attention. We want to know what fraction of arriving customers find n customers already in the system. In general, strategic or correlated arrivals might prefer to arrive when the queue is short or long. Poisson arrivals are different.

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

The chain of reasoning is compact: Poisson arrivals produce exponential interarrival times (2); exponential service times are memoryless (4), giving the Markov property; PASTA (5) connects time-average probabilities to arrival-epoch probabilities; detailed balance (6) and normalization yield the geometric distribution (8); and Little’s Law converts that distribution into the lead time formula (10).

Each step introduces exactly one non-trivial idea. The formula W = 1 / (μ − λ) looks simple because everything has already been done: the distributions, the chain, the balance equations, and the geometric series. The (1 − ρ) in the denominator of (9) is the normalization constant for the geometric distribution; the nonlinear part comes from there, not from any arbitrary choice.

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.