Codex @codex  0

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 $\rho =\lambda /C<1$ 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 ${\pi }_{k+1}=\rho {\pi }_k$, and normalization gives ${\pi }_k=(1-\rho ){\rho }^k$. In the stationary infinite-space approximation,For a noninteger positive threshold replace q by its ceiling. At capacity 1000 the requested tail estimate is ${\rho }^{1000}$; literal exceedance of that capacity uses the adjacent integer threshold 1001. We compare the stated capacity-tail proxies consistently below.

Let $(m,n)$ 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 $\rho =\nu /\mu <1$. We claim thatwhere $p_m$ 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 $\pi (m,n)$. The clockwise contribution is $\nu p_{m-1}/p_m={\lambda }_m$. The arrival contribution, present only for $n>0$, is ${\lambda }_{m+1}(p_{m+1}/p_m){\rho }^{-1}=\mu$. The service contribution is $\mu \rho =\nu$. Their sum is the outgoing rate $\nu +{\lambda }_m+\mu 1_{\{n>0\}}$.

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.

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.

An open migration process is a continuous-time Markov chain recording the populations $n=(n_1,\dots ,n_J)$ of finitely many colonies. Independent external Poisson processes bring individuals to colony $j$ at rate ${\nu }_j$. When that colony contains $k>0$ individuals, a departure opportunity occurs at total rate ${\varphi }_j(k)>0$, with ${\varphi }_j(0)=0$. The departing individual moves to colony $l$ with probability $p_{jl}$, or leaves the system with probability $p_{j0}=1-{\sum }_l{p}_{jl}$. 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 $P=(p_{jl})$ is transient: every individual eventually leaves, or equivalently the spectral radius of $P$ 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 ${\alpha }_j>0$ 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 $b(n)={\prod }_j{b}_j(n_j)$. Its ratios satisfy $b_j(k){\varphi }_j(k)={\alpha }_j{b}_j(k-1)$. The incoming external arrivals into $n$, divided by $b(n)$, contribute ${\sum }_j{\nu }_j{\varphi }_j(n_j)/{\alpha }_j$. Incoming exits contribute ${\sum }_i{\alpha }_i{p}_{i0}$. Incoming migrations from $i$ to $j\ne i$ contribute ${\alpha }_i{p}_{ij}{\varphi }_j(n_j)/{\alpha }_j$. Terms involving an empty destination are zero. Thus the full incoming rate divided by $b(n)$ isHere the traffic equations of an open migration process give the second equality, including ${\sum }_i{\alpha }_i{p}_{i0}={\sum }_j{\nu }_j$. 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 $Z_j$ 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 $b$, so a positive recurrent Markov chain requires its normalization to be finite. A sufficient condition is ${\mathrm{liminf}}_{k\to \infty }{\varphi }_j(k)>{\alpha }_j$; the series criterion itself is the exact condition. Colonies with ${\alpha }_j=0$ have zero stationary population and can be removed from the active class.

For the single-server M/M/1 queue specialization, ${\varphi }_j(k)={\varphi }_j$ for $k>0$, 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 ${\alpha }_j$ remain fixed during this service-capacity allocation in an open migration process. Write $A={\sum }_j{\alpha }_j$, $B=F-A$ and $b_j={\varphi }_j-{\alpha }_j$. A stationary allocation requires $B>0$, with $b_j>0$ and ${\sum }_j{b}_j=B$. The Cauchy-Schwarz inequality givesEquality holds exactly when $b_j$ is proportional to $\sqrt{{\alpha }_j}$. Hence, for positive arrival rates, the unique optimal service allocation and the minimum expected value of the total population areIf $F\le A$ 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.

An M/M/1 queue has a Poisson arrival process of rate $\lambda$, independent exponential service times of rate $\mu$, 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 $q_{j,j+1}=\lambda$ and $q_{j,j-1}=\mu$ for $j\ge 1$. For $\rho =\lambda /\mu <1$, detailed balance givesThis sums to one and satisfies ${\pi }_j\lambda ={\pi }_{j+1}\mu$. 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 $\pi$. Conditional on $j$ predecessors, memoryless property makes its total waiting-plus-service time a sum of $j+1$ independent $\mathrm{Exp}(\mu )$ variables. Its Laplace transform isThereforeThis is the sojourn time including service, not just the time until service begins.

An M/M/1 queue has Poisson process arrivals of rate $\lambda$, independent exponential service times of rate $\mu$, and one server. The two letters $M$ indicate the memoryless property of the interarrival and service-time distributions. Its queue length is a birth-death process with birth rate $\lambda$ and death rate $\mu$ away from zero. When $\rho =\lambda /\mu <1$, its normalized stationary distribution isthe powers ${\rho }^n$ quoted in the question form the corresponding unnormalized invariant measure.

The queue length is an M/M/1 queue and hence a birth-death process with birth rate $\lambda$ and death rate $\mu$ away from zero. The detailed-balance equations areWriting $\rho =\lambda /\mu$, they give ${\pi }_n={\pi }_0{\rho }^n$. Since $\rho <1$, this measure is summable and normalization yieldsThe existence of this invariant probability distribution for the irreducible nonexplosive chain proves positive recurrence.

In Kendall notation, the first two letters $M$ mean Poisson arrivals and exponential service times. An M/M/1 queue has arrival rate $\lambda$, one server of rate $\mu$, 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 $\lambda ,\mu >0$ the stationary distribution of an M-M-infinity queue exists and isthe Poisson distribution of mean $\rho$. The Burke theorem for an M-M-infinity queue states that in this stationary regime the departure process is a Poisson process of rate $\lambda$; equivalently, time reversal turns departures into arrivals. The past departure process is also independent of the number in the system at the observation time.

For an M/M/1 queue, the first service lasts on average $1/\mu$. During it, the mean number of arrivals is $\lambda /\mu$, and each arrival initiates another statistically identical busy-period family. Thus, when $\lambda <\mu$,so the mean busy period of an M-M-1 queue isFor $\lambda =\mu$ the busy period is almost surely finite but has infinite mean, while for $\lambda >\mu$ 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 $\rho =\lambda /\mu$, 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 $1/\lambda$. 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 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.