Here , so detailed balance gives
Consequently
The series converges for every , so this defines the unique invariant distribution.
By the PASTA property, an arrival joins with probability . In equilibrium the accepted-arrival rate must also equal the departure rate. Departures occur at rate precisely when the queue is nonempty, hence
The required joining probability is therefore
Poisson arrivals see time averages Created 2026-09-24 Updated 2026-10-14
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 for the state immediately before time .
For a state set , let count offered arrivals by time and let be their times. With a positive finite constant arrival rate, the PASTA equality is
almost 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 . 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 . 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 is admitted with conditional probability , using fresh randomness independent of that state, the accepted fraction is , where 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 , 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].
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 are
To 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 .
Queueing theory Created 2026-09-24 Updated 2026-10-14
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.
Three nodes have integer link capacities . Calls between a node pair use either its direct link or the two-link alternative. With unrestricted instantaneous rearrangement of existing calls, counts are feasible exactly when , and . Necessity follows by counting calls crossing each node cut. For sufficiency, the inequalities allow at most one count to exceed its direct-link capacity. Divert precisely that excess to the other two links; the same inequalities ensure capacity there. The counts thus have the same feasible set as a fixed routing loss network with one virtual resource at each node, capacity equal to the sum of its two incident physical-link capacities, and each call using its two endpoint resources. With independent Poisson processes for arrivals and independent routing-independent exponential distributions for holding times, this gives the usual product-form stationary distribution of a loss network and exact Poisson arrivals see time averages blocking probabilities.
In a one-operator closed migration process representing a finite-line switchboard, let count calls waiting for or receiving the operator's connection service and let count connected calls. At a stationary distribution, the expected drift of is , and that of is . Poisson arrivals see time averages identifies the full-state probability with . Thus the accepted arrival rate, operator throughput and completed-call rate coincide. This is a useful independent check on the product-form stationary distribution of a closed migration process.