Burke's theorem Created 2026-10-14 Updated 2026-11-05
In a stationary M/M/1 queue with independent Poisson arrivals of rate and exponential service times of rate , the departure counting process is a Poisson process of rate . Moreover, the departures before a fixed time are independent of the queue population . This independence concerns the past departures: future departures depend on whether the queue is currently empty.
The proof uses time reversal. The stationary Geometric distribution satisfies Detailed balance, , so the stationary queue population is a Reversible Markov chain. Departures in forward time are arrivals in reversed time. In the reversed chain the upward rate is again the constant , so those arrivals are an independent Poisson process, including independence of their future increments from the present queue population. Reversing time gives both assertions. Consequently, feeding the output of a stationary M/M/1 queue into another queue supplies Poisson input to that second queue. The claim depends on equilibrium; a queue started empty has no immediate departures even though arrivals have positive rate.
Elena Yudovina 2026-11-05
Elena Yudovina is a mathematician whose work includes the theory of stochastic networks. With Frank Kelly, she wrote Stochastic Networks by Frank Kelly and Elena Yudovina, connecting queueing theory, loss networks, congestion control and distributed optimization. The author's book page verifies the joint authorship and 2014 publication.[ref]
https://www.statslab.cam.ac.uk/~fpk1/BOOKS/sn.html. Author's book page: authors and publication record
A central question is how local service or routing rules affect an entire network. The book's M/M/1 queue illustrates the danger of operating near capacity: with arrival rate , service rate and , mean queue population is . Modest changes in load can therefore cause large changes in delay.[ref]
Stochastic Networks by Frank Kelly and Elena Yudovina. Section 2.1, M/M/1 equilibrium; overview of queueing, loss and congestion-control models
Mean busy period of an M-M-1 queue Created 2026-09-24 Updated 2026-11-05
The busy period of an M/M/1 queue starts with an arrival into an empty queue and ends the next time the queue becomes empty. Assume independent Poisson arrivals of rate and exponential service times of rate . If , its mean isOne derivation follows the family of customers generated during services. The initial customer's mean service time is ; during that service, the expected number of arrivals is . Each new arrival generates further arrivals during its own service. The expected total service time is therefore the nonnegative geometric series , which gives the formula. This argument can first be applied to finitely many generations and then justified by monotone convergence.
When , the busy period is finite almost surely but has infinite mean. When , it has probability of never ending; its extended mean is also infinite. Thus the divergence at critical load reflects a change in return behavior, not an infinite mean individual service time.
M/M/1 queue Created 2026-09-24 Updated 2026-11-05
An M/M/1 queue has a Poisson process of arrivals of rate , one server, independent exponential service times of rate , and unlimited waiting room. Arrivals are independent of service times. The two M symbols denote the memoryless arrival and service assumptions; the final one denotes the number of servers. Under a work-conserving service discipline, the queue population , including the customer in service, is a birth-death process with ratesThe server has no departure clock when the queue is empty. The traffic intensity is the server utilization in equilibrium when . Detailed balance then gives the Stationary distribution , whose mean is . For example, three arrivals per minute and four services per minute give and mean queue population three. Raising arrivals to per minute raises that mean to nineteen: operation near capacity amplifies congestion. These formulas count the customer being served as well as those waiting.[ref]
https://ocw.mit.edu/courses/2-854-introduction-to-manufacturing-systems-fall-2016/927056a1af54772a587fd84ad4951e71_MIT2_854F16_Mm1Queue.pdf. MIT 2.854 M/M/1 Queue notes, pages 1-2, system population and waiting population
M-M-1 queue with Bernoulli feedback Created 2026-09-24 Updated 2026-11-05
In an M-M-1 queue with Bernoulli feedback, external arrivals form a Poisson process of rate , service times are independent exponential random variables of rate , and each completed service independently returns its customer with probability . A returned customer immediately rejoins the same queue and requires a fresh service time. The queue population does not change at a feedback completion. Only completions that leave permanently produce downward jumps, at rate while the queue is nonempty.
For a continuously busy server, independent Bernoulli thinning of its Poisson completion clock gives an exponential time of rate until the next permanent departure. Thus the queue population has exactly the same birth-death process as an M/M/1 queue with service rate . It has a Stationary distribution precisely when ; its geometric parameter is then . This reduction describes the population and external departures, while individual customers can undergo several visits. For example, doubles the mean number of services needed per external customer from one to two.
M/M/1 utilization and delay 2026-10-14
Consider an M/M/1 queue with an exogenous Poisson process of arrivals of rate , one server, unlimited waiting space, first come first served service, and independent and identically distributed service times with an exponential distribution of rate , independent of arrivals. There is no blocking or abandonment, so offered rate and admitted queue throughput coincide: . The memoryless property makes the queue population a birth-death process. For , 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 count the whole system, and count only waiting. These distinctions and formulas are derived in MIT 2.854, M/M/1 Queue notes, pages 1-2.
Take customers per hour and customers per hour. The mean service time is hour, or 12 minutes, and the server utilization is . Computing each quantity explicitly,Thus Little's law checks both boundaries: and . The mean number in service is , 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 for the customer in service; clearing those four customers takes hour on average, independently confirming the mean queueing delay.
Holding per hour fixed, increasing arrivals from to per hour raises server utilization from to , but doubles mean customer sojourn time from one to two hours. At per hour, server utilization is , , hours, , and hours. Both mean population and mean duration diverge as approaches 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, , 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.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 31 3 a Solution Created 2026-10-03 Updated 2026-10-14
Let and measure payload in kilobytes. A unit-mean exponential payload requires an exponential service time of rate C. Headers remain until service is complete, so Q counts all unfinished packets, including the packet in service. Its process is an M/M/1 queue with birth rate lambda and death rate C whenever nonempty.
The detailed balance equations give , and normalization gives . In the stationary infinite-space approximation,For a noninteger positive threshold replace q by its ceiling. At capacity 1000 the requested tail estimate is ; literal exceedance of that capacity uses the adjacent integer threshold 1001. We compare the stated capacity-tail proxies consistently below.
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 30 1 b Solution Created 2026-10-03 Updated 2026-10-14
Let denote the clock position and the queue population, including any customer in service. By the memoryless property of the exponential distribution, the nonzero transition rates areSet . We claim thatwhere is the clock's stationary distribution from part (a). To check global balance for a continuous-time Markov chain, divide the incoming probability flux by . The clockwise contribution is . The arrival contribution, present only for , is . The service contribution is . Their sum is the outgoing rate .
The proposed probability distribution is normalized, so it is the equilibrium law. In particular, the clock position and queue population are independent random variables at any fixed equilibrium time, and the population has the geometric distribution of a stable M/M/1 queue. Independence of these two random variables does not assert independence of the two entire processes.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 32 1 Solution Created 2026-10-03 Updated 2026-10-14
For a stable system in which entering customers eventually leave, Little's law isHere is the long-run mean number of customers in the chosen system, is its actual entry rate, and 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 . Their mean time in this subsystem is the mean service time . Thus , with stability requiring . In this paper denotes a mean duration, so the exponential service rate is .
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 . Hence the admitted arrival rate, and therefore the service-entry rate, or queue throughput, is . Apply Little's law to the server alone again. Its mean population, or server utilization, is , and its mean customer sojourn time is , giving . 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 directly to this lossy system would miss the admission factor.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 213 1 i Solution Created 2026-10-03 Updated 2026-10-14
An open migration process is a continuous-time Markov chain recording the populations of finitely many colonies. Independent external Poisson processes bring individuals to colony at rate . When that colony contains individuals, a departure opportunity occurs at total rate , with . The departing individual moves to colony with probability , or leaves the system with probability . Routing choices and the clocks are independent. A return to the same colony does not change the state.
The word open means that the routing matrix is transient: every individual eventually leaves, or equivalently the spectral radius of is less than one. The traffic equations of an open migration process, with row-vector convention, give the total arrival rates:These rates include migrations as well as external arrivals. On the active colonies assume and the usual irreducible Markov chain condition. PutThe product form and its normalization condition areTo establish the product-form stationary distribution of an open migration process, first use its unnormalized weight . Its ratios satisfy . The incoming external arrivals into , divided by , contribute . Incoming exits contribute . Incoming migrations from to contribute . Terms involving an empty destination are zero. Thus the full incoming rate divided by isHere the traffic equations of an open migration process give the second equality, including . The right side is precisely the total outgoing rate. This proves global balance for a continuous-time Markov chain; pairwise detailed balance is not required for general routing.
For finite rates at each finite population, the continuous-time Markov chain is nonexplosive Markov chain: its total population is bounded over a finite time interval by the initial population plus the finitely many external arrivals, so it visits a finite set on which all jump rates are bounded. Consequently finite normalize the invariant weight to a stationary distribution. Under the stated irreducible Markov chain assumptions, this is the unique stationary distribution, and it is a positive recurrent Markov chain. Conversely, the unique invariant measure of an irreducible recurrent chain is proportional to , so a positive recurrent Markov chain requires its normalization to be finite. A sufficient condition is ; the series criterion itself is the exact condition. Colonies with have zero stationary population and can be removed from the active class.
For the single-server M/M/1 queue specialization, for , each stationary colony has the geometric distribution of an M/M/1 queue:The traffic equations of an open migration process do not involve the service rates, so the remain fixed during this service-capacity allocation in an open migration process. Write , and . A stationary allocation requires , with and . The Cauchy-Schwarz inequality givesEquality holds exactly when is proportional to . Hence, for positive arrival rates, the unique optimal service allocation and the minimum expected value of the total population areIf and some arrival rate is positive, no stable service allocation exists. Zero-arrival colonies need no service in their stationary empty class: allowing zero service there gives the same formula restricted to active colonies. If strictly positive service is demanded even at inactive colonies, the displayed minimum is an infimum approached as that unused allocation tends to zero. If all arrivals vanish, the stationary mean population is zero for every allocation that drains the initial population.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 4 26K a Solution Created 2026-09-24 Updated 2026-10-14
An M/M/1 queue has a Poisson arrival process of rate , independent exponential service times of rate , and one server, with an unlimited waiting room and the usual first-come-first-served discipline. Its number-in-system process is a continuous-time birth-death chain with and for . For , detailed balance givesThis sums to one and satisfies . The nonexplosive irreducible chain therefore has an invariant probability and is positive recurrent. Equivalently its negative drift above zero gives finite mean return cycles. Here queue length includes the customer in service.
In equilibrium, PASTA gives an arriving customer's number of predecessors the distribution . Conditional on predecessors, memoryless property makes its total waiting-plus-service time a sum of independent variables. Its Laplace transform isThereforeThis is the sojourn time including service, not just the time until service begins.
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 4 27K i Solution Created 2026-09-24 Updated 2026-10-14
An M/M/1 queue has Poisson process arrivals of rate , independent exponential service times of rate , and one server. The two letters indicate the memoryless property of the interarrival and service-time distributions. Its queue length is a birth-death process with birth rate and death rate away from zero. When , its normalized stationary distribution isthe powers quoted in the question form the corresponding unnormalized invariant measure.
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 4 27J a Solution Created 2026-09-24 Updated 2026-10-14
The queue length is an M/M/1 queue and hence a birth-death process with birth rate and death rate away from zero. The detailed-balance equations areWriting , they give . Since , this measure is summable and normalization yieldsThe existence of this invariant probability distribution for the irreducible nonexplosive chain proves positive recurrence.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 3 27J a Solution Created 2026-09-24 Updated 2026-10-14
In Kendall notation, the first two letters mean Poisson arrivals and exponential service times. An M/M/1 queue has arrival rate , one server of rate , and queue-length transitionsIt has a stationary distribution of an M-M-1 queue exactly whenand then
An M-M-infinity queue has infinitely many servers, so every customer begins service immediately. Its occupancy transitions areThe detailed balance for a birth-death process equations giveThus for every the stationary distribution of an M-M-infinity queue exists and isthe Poisson distribution of mean . The Burke theorem for an M-M-infinity queue states that in this stationary regime the departure process is a Poisson process of rate ; equivalently, time reversal turns departures into arrivals. The past departure process is also independent of the number in the system at the observation time.
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:
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.
Service-capacity allocation in an open migration process Created 2026-10-06 Updated 2026-11-05
Consider an open migration process whose colonies are M/M/1 queues with fixed positive traffic rates and service rates . Their mean queue populations are . Assume equal unit costs for capacity and a total rate budget .
Write and . The Cauchy-Schwarz inequality givesEquality holds exactly when is proportional to . Thus the unique optimum isFor traffic rates jobs per second and budget jobs per second, the spare rates are and service rates . The total mean population is . Equal spare rates instead give . The optimization allocates spare capacity rather than total capacity in square-root proportions; unequal capacity costs require a modified constraint.
Service time Created 2026-10-07 Updated 2026-11-05
A service time is the time needed to complete a customer's service requirement when a server works on that customer at the declared full capacity. If the required work is and capacity is , then . Its expected value is a duration. In an M/M/1 queue, the parameter of the exponential distribution has units of inverse time, and .
Under uninterrupted first come first served, the customer's time in service equals , while its customer sojourn time also includes the preceding queueing delay. Under processor sharing, elapsed time can be longer than because each customer receives only a fraction of the capacity. For example, two jobs arriving together, each requiring six work units, finish after four seconds on a three-unit-per-second sharing server; each has full-capacity service time two seconds.
A residual service time is the remaining full-capacity service duration. Service-time variability affects the Pollaczek-Khinchine mean formula, whereas Little's law needs the relevant finite means and consistent system boundaries rather than an exponential service distribution.
