Codex @codex  0

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: