Little's Law for the M/M/1 Queue

Population, Flow, and Time

Little’s law connects three different views of a queue: how many customers are present, how quickly customers arrive, and how long they stay. Its value is not limited to M/M/1 queues; it applies to stationary systems whenever customers’ residence intervals are counted consistently and the relevant means are finite. For an M/M/1 queue, it turns the stationary mean number in the system into mean time in the system, and the mean number waiting into mean waiting time.

Consider a queue in steady state on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(N(t)\) be the number of customers present at time \(t\), and suppose arrivals occur at a finite, positive long-run rate \(\lambda\). For each arrival, let \(W\) be that customer’s time in the system, from arrival until departure. A customer arriving at time \(s\) is present on the interval \([s,s+W)\). Write \(L=\mathbb{E}[N(0)]\), and let \(\mathbb{E}^0[W]\) denote the mean system time for an arrival, averaged over arrivals in steady state. The superscript \(0\) indicates this arrival-average, not an assumption about an arrival at a particular time seeing the time-stationary state.

Here stationarity means that shifting time does not change the joint distribution of the arrival process, customer residence times, and population process. The theorem does not require Poisson arrivals or independence between a customer’s residence time and the surrounding system. The arrival-average is essential: in general it need not equal an average taken at an arbitrary time.

Proof. Regard each arrival as carrying its residence time as a mark. For a time set \(A\) and a set \(B\) of possible residence times, let \(\nu(A,B)\) be the expected number of arrivals in \(A\) whose residence times belong to \(B\). For each fixed \(B\), stationarity makes \(\nu(A,B)\) invariant under translating \(A\). It is finite on bounded time intervals because the arrival intensity is finite. A translation-invariant measure on the real line that is finite on bounded intervals is a constant multiple of length: its value on an interval depends only on the interval’s length, additivity gives the value for rational lengths, and continuity of measures gives it for all lengths. Thus \(\nu(A,B)=c(B)|A|\). The constants \(c(B)\) define a measure on residence times, with total mass \(c(\text{all})=\lambda\). Normalize it by \(\lambda\); the resulting probability distribution is the arrival-average distribution, so \(c(B)=\lambda\mathbb{P}^0(W\in B)\).

At time \(0\), the population is the sum over arrivals at times \(s\) of the indicator that their residence interval contains \(0\). Apply the preceding intensity identity first to nonnegative simple functions of \(s\) and \(W\), then to their increasing limits. This is valid for the indicator below by monotone approximation, and uses only nonnegative terms, so it also holds if an expectation is infinite. We obtain

For a fixed residence time \(W=w\ge0\), the set of arrival times \(s\) satisfying \(s\le0<s+w\) has length \(w\); when \(w=0\), it is empty and has length \(0\). This proves the identity. For a subpopulation, apply the same argument to its entry times and the intervals during which each entrant belongs to that group. The intensity is then the group’s entry rate, not necessarily the system’s arrival rate. \(\square\)

Applying the Law to an M/M/1 Queue

An M/M/1 queue has Poisson arrivals at rate \(\lambda\), independent exponential service times at rate \(\mu\), one server, and no limit on the number who may wait. Assume \(\lambda>0\) and \(\mu>\lambda\), and consider its stationary regime. Define the traffic intensity \(\rho=\lambda/\mu\), so \(0<\rho<1\). Let \(N\) be the number in the system, \(L=\mathbb{E}[N]\) the mean number in the system, and \(L_q\) the mean number waiting, excluding any customer in service. Let \(W\) be an arrival’s time in the system and \(W_q\) the time from arrival until service begins. In \(W_q\), an arrival that starts service immediately contributes zero.

The stationary number-in-system probabilities, established in the earlier material on the M/M/1 queue, are \(\pi_n=(1-\rho)\rho^n\) for \(n\ge0\). They sum to one because \(0<\rho<1\) and the geometric series converges. We can use these probabilities to compute the two mean populations; Little’s law then gives the corresponding mean times.

Proof. Since \(\pi_n=(1-\rho)\rho^n\), the mean number in the system is

The series identity follows by differentiating \(\sum_{n=0}^{\infty}\rho^n=(1-\rho)^{-1}\) for \(0<\rho<1\) and multiplying by \(\rho\). If \(N=n\), the number waiting is \((n-1)^+=\max(n-1,0)\). Therefore

Every arrival enters the system, and the system residence interval is the customer’s time from arrival to departure. The queue residence interval lasts from arrival until service begins; its duration is zero when service begins immediately. Thus the law applies to both counts with the total arrival rate \(\lambda\): \(L=\lambda W\) and \(L_q=\lambda W_q\). The population expressions are finite since \(0<\rho<1\). The extended-mean identity in Little’s law therefore ensures that the corresponding arrival-average times are finite and equal to \(L/\lambda\) and \(L_q/\lambda\). Substituting \(\rho=\lambda/\mu\) gives \(W=\rho/[\lambda(1-\rho)]=1/(\mu-\lambda)\) and \(W_q=\rho^2/[\lambda(1-\rho)]=\lambda/[\mu(\mu-\lambda)]\). All four formulas follow. \(\square\)

The formulas separate two effects. The mean system time includes the time waiting and the time in service; the mean queueing time excludes service. In particular, their difference is the mean service time \(1/\mu\), as can also be checked directly from the expressions. This is a check on the decomposition, not a replacement for defining which customer intervals each quantity counts.

Using Little’s Law for a Subpopulation

The same argument works for customers counted only during part of their time in the system, but the entry rate and mean duration must refer to that same part. For the M/M/1 queue, all arrivals are eligible for the system count, so \(L=\lambda W\). For the queue count, it is convenient to assign every arrival a queue residence time, equal to zero if the customer goes straight into service. This convention makes the total arrival rate \(\lambda\) the correct rate in \(L_q=\lambda W_q\).

Alternatively, one may focus only on customers who actually spend positive time waiting. If only a fraction of arrivals enter that subpopulation, its entry rate is the total arrival rate multiplied by that fraction, and its mean duration is conditional on entering. The two ways of calculating agree when used consistently: average over all arrivals with zero assigned to nonentrants, or use the entry rate and the conditional mean duration for entrants.

Common Pitfalls and Interpretation

A common error is to multiply a subgroup’s conditional residence time by the overall arrival rate. For example, if half of arrivals wait and those who wait spend a mean of \(1\) hour waiting, the overall rate is \(\lambda=2\) arrivals per hour, but the rate entering the positive-wait subgroup is \(1\) per hour. The mean number in that subgroup is \(1(1)=1\), not \(2(1)=2\). Equivalently, if all arrivals are included, their average waiting time is \((1/2)(1)+(1/2)(0)=1/2\) hour, and \(2(1/2)=1\). In the M/M/1 formula \(L_q=\lambda W_q\), \(W_q\) is this all-arrivals average, including zero waits.

Another error is to confuse a stationary mean population with a statement about an individual customer. Little’s law relates averages; it does not provide the distribution of waiting times or sojourn times. Nor does the identity alone guarantee finite means: the M/M/1 formulas used here require \(\lambda<\mu\). At or above the stability threshold there is no stationary probability distribution of the geometric form used in the calculation, so these steady-state M/M/1 performance formulas do not apply.

Finally, the law requires a consistent count. If a customer is counted in \(N(t)\) throughout exactly the interval whose duration is called \(W\), then the identity matches those definitions. Counting customers only while waiting requires queue residence times, not total system times. If some arrivals are rejected or never enter a subgroup, use the subgroup’s entry rate with its conditional residence time, or use the total rate with zero duration assigned to arrivals that never enter.