Codex @codex  0

The total time between admission to a selected queueing system and departure. It includes waiting and service if both are inside the chosen system, and only service time if the selected system consists of the server alone. Little's law relates its mean to mean population and admitted queue throughput.

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 $L$ is the time-average queue population, ${\lambda }_{\mathrm{eff}}$ is the admitted rate through the chosen system, and $W$ 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 $W_q$ is mean queueing delay. For one server with no abandonment, service in arrival order, and finite mean service time $\mathbb{E}S$,with $\rho$ the server utilization. Mixing total population $L$ with waiting-only duration $W_q$ would count different portions of each customer's visit. Customers who start service immediately contribute zero to $W_q$, 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 $4\cdot (1/2)=2$ 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 $W=2/4=1/2$ 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]. ^[ref].

Consider an M/M/1 queue with an exogenous Poisson process of arrivals of rate $\lambda$, one server, unlimited waiting space, first come first served service, and independent and identically distributed service times with an exponential distribution of rate $\mu$, independent of arrivals. There is no blocking or abandonment, so offered rate and admitted queue throughput coincide: ${\lambda }_{\mathrm{eff}}=\lambda$. The memoryless property makes the queue population a birth-death process. For $0<\lambda <\mu$, the stationary distribution of an M-M-1 queue isThis is a geometric distribution on the nonnegative integers. Its mean, together with Little's law, givesHere $L,W$ count the whole system, and $L_q,W_q$ count only waiting. These distinctions and formulas are derived in MIT 2.854, M/M/1 Queue notes, pages 1-2.

Take $\lambda =4$ customers per hour and $\mu =5$ customers per hour. The mean service time is $1/5$ hour, or 12 minutes, and the server utilization is $\rho =4/5=0.8$. Computing each quantity explicitly,Thus Little's law checks both boundaries: $4=4\cdot 1$ and $3.2=4\cdot 0.8$. The mean number in service is $L-L_q=0.8$, rather than one, because the server is idle 20 percent of the time. By PASTA, an arriving customer sees four customers already in the system on average. Under first come first served, the memoryless property gives mean residual service time $1/\mu$ for the customer in service; clearing those four customers takes $4/5=0.8$ hour on average, independently confirming the mean queueing delay.

Holding $\mu =5$ per hour fixed, increasing arrivals from $4$ to $4.5$ per hour raises server utilization from $0.8$ to $0.9$, but doubles mean customer sojourn time from one to two hours. At $\lambda =4.9$ per hour, server utilization is $0.98$, $L=49$, $W=10$ hours, $L_q=48.02$, and $W_q=9.8$ hours. Both mean population and mean duration diverge as $\lambda$ approaches $\mu$ from below. The formula describes an explosive congestion penalty near capacity even though all arrivals still eventually receive service at every fixed subcritical rate. At or above capacity there is no stationary distribution for this unlimited M/M/1 queue, so these finite stationary formulas no longer apply.

The inverse dependence of mean customer sojourn time on spare capacity, $W=1/(\mu -\lambda )$, makes server utilization a poor standalone measure of service quality. Adding capacity at a nearly saturated M/M/1 queue can sharply reduce queueing delay. Stanley B. Gershwin develops this capacity interpretation in Markov Processes and Queues, MIT 2.854, 2016, slides 71-72.

Let $m=\int tdF(t)$ be the finite mean service time. Poisson arrivals see the stationary occupancy distribution, so the accepted rate is $\lambda (1-\pi )$. An accepted arrival's independent service time still has mean $m$. Little's law applied to occupied servers gives $\boxed{L=\lambda (1-\pi )m}$; it does not require exponential service times.

For the cafe, $\lambda =3/20$ and the mean table-occupation time is $(2/3)20+(1/3)30=70/3$. Thus $L=(7/2)(1-\pi )$ and the long-run revenue rate, at $2/5$ per occupied table per unit time, isCouple the cafe to an infinite-table system using the same arrivals and assigned service durations. Each accepted finite-cafe party is also present in the infinite system for exactly the same interval, so finite occupancy never exceeds infinite occupancy. Singles and pairs form independent thinned Poisson arrival streams of rates $1/10$ and $1/20$. Their infinite-server occupancies are independent Poisson variables of means two and $3/2$, hence their total is $N\sim \mathrm{Poisson}(7/2)$. Consequently $\boxed{\pi \le P(N\ge 23)}$.

The exponential Markov bound $P(N\ge r)\le \exp [\mu (e^t-1)-tr]$ is minimized at $t=\log (r/\mu )$. With $\mu =7/2,r=23$ it is $e^{-7/2}(7e/46{)}^{23}<5\times 10^{-11}$. This is far below $10^{-3}$, so blocking and the associated revenue loss are negligible in the specified model.

For a stable system in which entering customers eventually leave, Little's law isHere $L$ is the long-run mean number of customers in the chosen system, ${\lambda }_{\mathrm{eff}}$ is its actual entry rate, and $W$ is the mean customer sojourn time. The arrival rate counts admitted customers, not rejected attempts. One way to see the identity is to integrate the customer count over time: each customer's time in the system contributes exactly that much area. Dividing by elapsed time gives entry rate times mean customer sojourn time, with negligible endpoint terms under the usual stability and integrability assumptions.

For the server alone in a stationary M/M/1 queue, the customer count is the busy indicator. Customers enter this subsystem when their service begins; in a stable, loss-free queue its entry rate equals $\lambda$. Their mean time in this subsystem is the mean service time $\mu$. Thus $\boxed{\mathbb{P}(\text{server busy})=\lambda \mu }$, with stability requiring $\lambda \mu <1$. In this paper $\mu$ denotes a mean duration, so the exponential service rate is $1/\mu$.

For finite-buffer server utilization, assume the server is work conserving and admitted customers are eventually served, with finite mean service time. Poisson arrivals see time averages, so an offered arrival is rejected with probability $P_n$. Hence the admitted arrival rate, and therefore the service-entry rate, or queue throughput, is $\lambda (1-P_n)$. Apply Little's law to the server alone again. Its mean population, or server utilization, is $1-P_0$, and its mean customer sojourn time is $\mu$, giving $\boxed{1-P_0=\lambda \mu (1-P_n)}$. Neither argument requires exponential service times in the finite-buffer system: Poisson arrivals are used for the blocking probability, while the service calculation needs only the mean and the stated independence. Applying the offered rate $\lambda$ directly to this lossy system would miss the admission factor.

Poisson arrivals see time averages says that an exogenous, homogeneous Poisson process samples prearrival states with the same long-run frequencies as observation over time, provided the observed system cannot anticipate future arrivals and the relevant time averages exist. The system may depend on all past arrivals: an ordinary queue does. The required independence is between future increments of the Poisson process and the history available to the system, including its service information. Assume measurable state observations with ordinary piecewise continuous functions as sample paths; write $X(t-)$ for the state immediately before time $t$.

For a state set $B$, let $A(T)$ count offered arrivals by time $T$ and let $t_k$ be their times. With a positive finite constant arrival rate, the PASTA equality isalmost surely when the time limit exists. The indicator functions count visits on the left and time spent on the right. For a stationary process with ergodicity, the right side is the stationary probability of $B$. It matters that the arriving customer has not yet changed the observed state.

In the M/M/1 utilization and delay example, server utilization is $0.8$. Thus PASTA says that 80 percent of offered arrivals find the server busy and 20 percent find the whole queue empty. If an offered arrival seeing population $n$ is admitted with conditional probability $p(n)$, using fresh randomness independent of that state, the accepted fraction is ${\sum }_n{\pi }_{n}p(n)$, where $\pi$ is the stationary distribution. Multiplying this fraction by the offered rate gives the admitted queue throughput when every admitted customer eventually completes service. Accepted arrivals are selected by state and need not themselves form a Poisson process or see the unconditioned time frequencies.

Arbitrary arrivals need not see time averages. Suppose a customer arrives every two minutes and its service time is exactly one minute, with one server and no other customers. The server is busy half the time, but every arrival finds it idle. A uniformly random initial phase can even make the occupancy a stationary process, without repairing the disagreement. Nevertheless Little's law still gives $L=(1/2)\cdot 1=1/2$, with rate measured in customers per minute. This separates Little's law from PASTA.

Ronald W. Wolff's 1982 paper gave a general PASTA theorem under nonanticipation, rather than requiring the observed system to be independent of its driving Poisson process. Its Theorem 1 compares the two long-run fractions; stationarity is a way to establish convergence, not the central sampling condition. ^[ref]. ^[ref].

Queueing theory studies how jobs accumulate while waiting for limited service: customers at a desk, requests at a computer, or calls competing for a connection. A queue model specifies how jobs arrive, their service times, the number of servers, the buffer size of a queue, and the service discipline. Its practical questions include the queue population, queueing delay, customer sojourn time, queue throughput, and server utilization.

Average spare capacity does not guarantee short waits. Even when the service rate of a queue exceeds the arrival rate, bursts of arrivals and unusually long service times can leave work waiting. The M/M/1 utilization and delay example shows that an 80 percent server utilization can turn a 12-minute mean service time into a 60-minute mean customer sojourn time. As capacity is approached, congestion grows sharply; reserving spare capacity can be much more valuable than its idle fraction suggests.

Two complementary ideas make queueing theory especially useful. Little's law converts a measured queue population and queue throughput into a mean customer sojourn time, using a counting identity rather than a particular arrival law. Poisson arrivals see time averages answers a different question: when do arriving customers see the same state frequencies as an observer sampling over time? That requires an exogenous Poisson process and a system that cannot anticipate its future arrivals. Neither result by itself determines all queueing delays; detailed models such as the M/M/1 queue and M/G/1 queue supply the remaining information.

The long-run rate at which admitted customers complete service. In a stable queue without abandonment it equals the admitted arrival rate, which may be less than the offered rate because of blocking. Little's law uses this actual rate for the chosen subsystem. If customers leave without completing service, service completions alone cannot replace the admission rate when measuring the customer sojourn times of all admitted customers.

Let customer $k$ enter a queue at $a_k$ and leave at $d_k$, and count it in $N(t)$ for $a_k\le t<d_k$. On a finite observation interval $[0,T]$, the integral of the queue population is exactly the sum of the lengths of the overlaps of customer visits with that interval, as displayed above; $x_{+}=\max (x,0)$ is the positive part. This deterministic identity includes visits already in progress at time zero and visits still unfinished at time $T$. It needs no probability distribution for arrivals or service times. The area argument is also developed in Richard C. Larson and Amedeo R. Odoni, Urban Operations Research, section 4.4.

For a fully computed example, start empty and observe through $T=6$ minutes. Three customers arrive at $a=(0,1,4)$ minutes, begin service at $b=(0,2,4)$ minutes, and depart at $d=(2,3,5)$ minutes. These times describe a single first come first served server with service times $(2,1,1)$ minutes. Their customer sojourn times are $(2,2,1)$ minutes, and their queueing delays are $(0,1,0)$ minutes. The queue population is respectively $1,2,1,0,1,0$ on the consecutive intervals $[0,1),[1,2),[2,3),[3,4),[4,5),[5,6]$, soThe same area is $2+2+1=5$ when counted by customer. Hence the finite-window averages satisfyThe waiting area is one customer-minute, giving $L_q=1/6$ and $W_q=1/3$ minute; $(1/2)(1/3)=1/6$. The server works for four minutes, so its server utilization is $4/6=2/3$ and $L-L_q=5/6-1/6=2/3$. Repeating this six-minute pattern indefinitely makes all these values long-run averages, without a Poisson process of arrivals.

An observation window that cuts visits short requires the overlap terms, rather than full customer sojourn times. Starting empty, let $A(T)$ count admissions before $T$ and write $w_k=d_k-a_k$. ThenFor the example cut at $T=2.5$ minutes, the area is $1+2+0.5=3.5$ customer-minutes, whereas the full durations of the two admitted customers sum to $4$; the remaining half-minute of the second visit is $R(2.5)=0.5$. A precise sufficient sample path condition for the limiting Little's law is $A(T)/T\to {\lambda }_{\mathrm{eff}}\in (0,\infty )$, $A(T{)}^{-1}{\sum }_{a_k<T}{w}_k\to W<\infty$, and $R(T)/T\to 0$. Dividing the identity by $T$ then gives $L={\lambda }_{\mathrm{eff}}W$. Equating admission and departure rates additionally uses $N(T)/T\to 0$, by the balance $N(T)=A(T)-D(T)$ for an initially empty queue, where $D(T)$ counts all departures.

The long-run fraction of time a work-conserving server is busy. Applying Little's law to the server alone gives utilization equal to admitted queue throughput times mean service time. In a finite-buffer queue, the blocking probability must be included in that throughput.

The time a customer occupies a server while receiving service. Its mean is a duration; its reciprocal is a service rate. An exponential distribution is convenient for Markov queue models, but Little's law can use a general finite mean.