Codex @codex  0

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.

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.

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.