Little's law 2026-10-14
For a stable queue with finite long-run averages, a positive finite admitted rate, and negligible initial and terminal contributions after division by observation time, Little's law statesHere is the time-average queue population, is the admitted rate through the chosen system, and is the customer-average customer sojourn time inside that same boundary. Without abandonment, admitted rate equals completed-service queue throughput in this stable regime. It may differ from the offered arrival rate because of blocking. When customers abandon, count their admissions and exits too, and average their actual time inside; using only service completions would mismatch the population being measured.
For the waiting area alone the matching identity iswhere is mean queueing delay. For one server with no abandonment, service in arrival order, and finite mean service time ,with the server utilization. Mixing total population with waiting-only duration would count different portions of each customer's visit. Customers who start service immediately contribute zero to , and must still be included in that customer average.
The strength of Little's law is that it does not require a Poisson process, an exponential distribution of service times, or service in arrival order. The sample-path area identity for Little's law explains why: counting customer-time across time slices or across customer visits gives the same area. A sufficient probabilistic setting is repeated independent and identically distributed empty-to-empty cycles with finite positive mean cycle duration, finite positive mean customer count, and finite mean population area; the renewal-reward theorem then supplies the long-run averages. Stability alone does not guarantee finite mean queueing delay: the Pollaczek-Khinchine mean formula shows why a finite second moment of service time matters for that mean in an M/G/1 queue.
For example, suppose a service desk receives six requests per hour but admits only four; measured mean customer sojourn time of admitted requests is half an hour. Its mean queue population is customers. Multiplying the offered rate by that duration would incorrectly give three. Conversely, counting two customers on average and measuring admitted queue throughput of four per hour gives hour. This lets one estimate a hard-to-track duration from occupancy and completed-job counts.
John D. C. Little published a rigorous proof in 1961 under finite-mean, strict stationarity, and ergodicity assumptions on the arrival process. Those were assumptions of that proof, rather than a requirement that every useful form of the identity have random arrivals. [ref]
https://pubsonline.informs.org/doi/10.1287/opre.9.3.383. Little, A Proof for the Queuing Formula: L = λW, Operations Research 9(3), 383-387
. [ref]https://fisherp.scripts.mit.edu/wordpress/wp-content/uploads/2015/11/ContentServer.pdf. Original paper, opening statement
. Mean busy period of an M-M-infinity queue Created 2026-09-24 Updated 2026-11-05
Writing , the stationary empty probability is . Alternating idle periods of mean with busy periods and applying the renewal-reward theorem gives
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 207 3 a iii Solution Created 2026-10-03 Updated 2026-10-05
Dividing the expected occupation time of a continuous-time Markov chain by and letting givesFor this is also the almost-sure long-run time fraction, not just the limit of an expectation. The two-state continuous-time Markov chain is irreducible and positive recurrent. Alternatively, a regeneration cycle consists of a mean symptom-free holding time followed by a mean symptomatic holding time; the renewal-reward theorem gives . This agrees with the stationary distribution solving and .
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 3 27K Solution Created 2026-09-24 Updated 2026-09-29
A renewal-reward process consists of i.i.d. regenerative cycles , where is the th cycle length and is the reward accumulated during that cycle. If and , the renewal-reward theorem states that the cumulative reward satisfiesalmost surely, with the usual negligible-remainder condition for an unfinished cycle.
For the machine, let be its working lifetime after a repair. The next repair occurs at the first inspection following failure, so one repair-to-repair cycle has lengthwhile its working-time reward is . Since an exponential distribution of rate has mean ,By the tail-sum formula for the positive integer-valued variable ,Thereforeand the long-run proportion of time for which the machine is working is
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 3 27J c Solution Created 2026-09-24 Updated 2026-10-14
For an M/M/1 queue, the first service lasts on average . During it, the mean number of arrivals is , and each arrival initiates another statistically identical busy-period family. Thus, when ,so the mean busy period of an M-M-1 queue isFor the busy period is almost surely finite but has infinite mean, while for it is infinite with positive probability; in either case its expectation is infinite.
For an M-M-infinity queue, stationary occupancy is Poisson with mean , so the long-run probability of an empty system isThe process alternates between idle periods and busy periods. An idle period waits for the next Poisson arrival, so its mean is . The renewal-reward theorem, with reward equal to time spent empty, givesSolving yields the mean busy period of an M-M-infinity queue:
Pollaczek-Khinchine mean formula Created 2026-10-03 Updated 2026-11-05
For a stationary first come first served M/G/1 queue, take independent service times independent of the Poisson process of arrivals. Let , and . Then the mean queueing delay and mean queue population areTo see why the second moment appears, a completed service of length contributes triangular area under the residual service time curve. The renewal-reward theorem gives mean residual duration , counting zero while idle. Poisson arrivals see time averages and Little's law then give . Solving this identity proves the formula.[ref]
For the same mean , deterministic service has , while exponential service has , doubling the mean wait at fixed arrival rate. With minute and per minute, these waits are respectively and one minute. Stability alone does not guarantee finite mean delay: for positive and infinite second moment, the mean FCFS wait is infinite even when .
Renewal interval containing a fixed time Created 2026-09-24 Updated 2026-11-05
The renewal interval containing a fixed time has lengthThe interval is selected by a time rather than by its index. In a stationary renewal process with positive interarrival law and finite mean , its distribution is size-biased:The renewal-reward theorem explains this: give a cycle reward equal to its length when that length lies in , and zero otherwise. The long-run fraction of time spent in such cycles is exactly the displayed ratio. A longer cycle occupies more observation time and therefore has a higher chance of containing a typical observation.
If interarrivals are one or three time units with equal probabilities, an indexed cycle has probability of being long, but an equilibrium time falls in a long cycle with probability . The expected observed interval length is , compared with indexed mean two. This is an inspection effect, not a change to the underlying interarrival law. For a renewal process freshly started at zero, the exact finite-time distribution need not already equal the equilibrium size-biased law.
Stationary cycle occupation formula Created 2026-09-24 Updated 2026-11-05
For an irreducible positive recurrent Discrete-time Markov chain with Stationary distribution , fix a state and its positive first return . The Stationary cycle occupation formula isThe cycle includes the initial visit to and excludes the returning visit. Thus for the left side is exactly one, consistent with the ratio.
Successive return cycles are independent with the same law by the Strong Markov property. The renewal reward ratio gives the long-run visit fraction as expected cycle occupation divided by expected cycle length. Kac's lemma supplies , so the ergodic visit fraction gives the displayed identity. positive recurrence ensures the cycle length and all its occupation rewards are integrable.
For distinct , the Two-state excursion visit law gives the same expected occupation as , where and . ConsequentlyThis identity does not require reversibility: it follows from return-cycle occupation. It also does not require aperiodicity, since time averages still converge in a periodic positive recurrent chain.