Codex @codex  0

A stable equilibrium M-M-s queue has a Poisson process of departures with the same rate as its input. Its present population is also independent of past departures, a component of quasireversibility. The birth-death process satisfies detailed balance; reversed upward jumps have a constant arrival rate, so they are generated by an independent Poisson process.

If potential arrivals form a Poisson process of rate $\lambda$ and an arrival seeing $n$ customers joins with probability $p(n)$, the queue length is a birth-death process with birth rate $b_n=\lambda p(n)$ and death rate $d_n=\mu$ for $n\ge 1$. Its stationary ratios, when normalizable, are

An $M/M/s/K$ queue has arrivals forming a Poisson process of rate $\lambda$, $s$ servers with independent service times having an exponential distribution of rate $\mu$, and total system capacity $K\ge s$. Its occupancy is the finite birth-death process on $\{0,\dots ,K\}$ with

For a single resource, assume unit-capacity calls arrive as a Poisson process of rate $a$, holding times have independent exponential distributions with mean $h$, and a call is rejected when all $C$ units are occupied. Let $\nu =ah$. Its occupancy is a birth-death process on $\{0,\dots ,C\}$, with birth rate $a$ below capacity and death rate $k/h$ in state $k$. Detailed balance for a birth-death process givesBy Poisson arrivals see time averages, the Erlang loss formula isThis derivation assumes exponential holding times; the standard insensitivity result extends the same formula to independent holding times of the same mean, but is not needed here.

A loss network with fixed routing has finitely many resources $j$, capacities $C_j$, and call types $r$ with a fixed nonempty set of resources. Type $r$ has Poisson arrivals of rate $a_r$, independent holding times of mean $h_r$, and offered load ${\nu }_r=a_r{h}_r$. It is accepted only if every resource on its route has a free unit, and otherwise is lost. In the displayed equations use the unit-incidence matrix $A_{jr}=1$ for $j\in r$ and zero otherwise. The equations concern this unit-demand model, rather than arbitrary multi-unit requirements.

The Erlang fixed point approximation replaces the correlated resource availabilities by independent ones. A type-$r$ call survives blocking at resources other than $j$ with approximate probability ${\prod }_{i\in r\setminus \{j\}}(1-B_i)$. Treating this filtering as Poisson thinning gives the reduced offered loadApply the single-resource formula to obtain $B_j=E({\rho }_j,C_j)$. Independence and Poisson thinning here are approximations; no such approximation is claimed for the exact network's joint stationary distribution.

Assume first $C_j\ge 1$. The right side is a continuous map from $[0,1{]}^J$ into itself, so the Brouwer fixed-point theorem gives existence. To prove uniqueness, let $m_C(\rho )=\rho [1-E(\rho ,C)]$ be the carried load of an Erlang loss resource, also the mean of the truncated Poisson occupancy. Differentiation yieldsThus $E$ increases continuously from zero to one and $m_C$ increases from zero to $C$.

Write $x_j=-\log (1-B_j)\ge 0$, and define ${\rho }_C(x)=E(\cdot ,C{)}^{-1}(1-e^{-x})$ and ${\ell }_C(x)=m_C({\rho }_C(x))$, with ${\ell }_C(0)=0$. Each ${\ell }_C$ is continuous and strictly increasing. A fixed point satisfiesThese are precisely the stationary equations for the convex potential for the Erlang fixed pointThe first term is convex; the second is strictly convex because each ${\ell }_{C_j}$ strictly increases. Hence $F$ is strictly convex. Its gradient cannot vanish at two distinct points: the difference of gradients dotted with the difference of points is strictly positive, with a positive contribution from every changed coordinate in the integral term. This also covers boundary coordinates $x_j=0$, using the right derivative there. Every fixed point has $B_j<1$, since its offered load is finite, so the change of variables is valid. There is exactly one fixed point. If a capacity is zero, its blocking probability is one; delete it and all routes using it before applying the argument to the remaining positive capacities. Unused resources have blocking probability zero.

First consider an M-M-K queue with $K$ servers, arrival rate $\lambda$, and service rate $\beta$ at each server. Assume $\lambda <K\beta$ so that a stationary distribution exists. Its population is a birth-death process with rates $q_{n,n+1}=\lambda$ and $q_{n,n-1}=\beta \min (n,K)$. The equilibrium probabilities satisfy detailed balanceThus the population process is a reversible Markov chain. In its time reversal of a continuous-time Markov chain, forward departures become upward jumps whose rate is the constant $\lambda$, independent of the state. They can be generated by a rate-$\lambda$ Poisson process independent of the initial reversed state. Reversing time preserves the Poisson process law, proving the equilibrium departure process is Poisson with rate $\lambda$, the Burke theorem for a multi-server queue.

The same argument gives the departure component of quasireversibility needed for the tandem calculation: the present upstream population is independent of its entire past departure process. Indeed, these departures become future arrivals in the reversed chain, independent of its initial population. First check this on finite time windows, then extend to the full past. A Poisson output alone, without this independence, would not justify multiplying queue-empty probabilities.

Now let $a=\nu \mu$, where $\mu$ denotes the mean service time at passport control, so the service rate at each of its two servers is $1/\mu$. The stationary distribution of the M-M-s queue with $s=2$ has normalizing sumHence its empty probability is $(2-a)/(2+a)$. Its output feeds a stable M-D-1 queue with rate $\nu$ and deterministic service time $\tau$. In a stationary work-conserving single-server queue, the busy fraction is the rate of completed work, $\nu \tau$, so the empty probability is $1-\nu \tau$.

The downstream stationary workload is a causal function of past upstream departures. For example, it is the limit of workloads constructed from arrivals in increasingly long finite past intervals; stability makes this stationary construction well defined. The backward independence just proved therefore makes the two present queue populations independent. Consequently

With walking time $\sigma$, the downstream arrival stream is the upstream departure stream shifted by $\sigma$. Its present workload depends only on departures up to time $-\sigma$. The number walking at time zero is the number of departures in $(-\sigma ,0]$, which has Poisson distribution of mean $\nu \sigma$ and is independent of the earlier departures. The upstream present population is independent of both parts of its past departure stream. Thus the three empty events factor, givingThe factor $e^{-\nu \sigma }$ is the empty probability of the deterministic-travel infinite-server stage. Both printed stability inequalities ensure the stationary calculations apply.

For the Erlang loss formula, assume a Poisson process of arrivals with rate $\lambda$, independent holding times with exponential distribution of mean $1/\beta$, unit capacity usage per accepted call, and rejection without waiting when all $C$ units are occupied. Here $C$ is a positive integer and the offered load is $a=\lambda /\beta$. The call population on $\{0,\dots ,C\}$ is a birth-death process; detailed balance givesBy Poisson arrivals see time averages, the fraction of arrivals rejected is the time probability of full occupancy. ThereforeThe paper's $\nu$ is the offered load, rather than necessarily an arrival rate. Exponential holding times suffice for this derivation; no unproved insensitivity of loss networks assumption is needed.

A loss network with fixed routing has capacities $C_j$, call types $r$, and a link-route incidence matrix $A$ with $A_{jr}=1$ exactly when a type-$r$ call requires link $j$. An accepted call holds one unit on every link of its route for its holding time; if any required link is full, the call is rejected everywhere. Take independent Poisson processes of calls, independent holding times, and route offered loads ${\nu }_r$. For the finite-variable formulation below, take $C_j\ge 1$; a zero-capacity link and all routes using it may be removed first.

The Erlang fixed point approximation treats blocking at different links as independent and thins the traffic offered to link $j$ by acceptance at the other links. Its reduced offered load isThe equality uses $A_{jr}\in \{0,1\}$: only routes with $A_{jr}=1$ contribute. Treating this reduced stream as Poisson leads to $B_j=E(a_j(B),C_j)$. Independence and Poisson thinning here are the approximation, not exact properties of a general loss network.

To construct the convex potential for the Erlang fixed point, write $e_C(a)=E(a,C)$ and $m_C(a)=a[1-e_C(a)]$, the carried load of an Erlang loss resource, equivalently the mean occupancy in the single-link stationary distribution. Differentiating its finite sums gives, for $a>0$,The variance is positive because the finite occupancy law is nondegenerate for $a>0$. Furthermore $e_C$ maps $[0,\infty )$ increasingly onto $[0,1)$, while $m_C$ increases from zero to $C$. SetIn particular $U(0,C)=0$, $U(\cdot ,C)$ is continuous and strictly increasing, and $U(z,C)\to C$ as $z\to \infty$.

Forthe first sum is convex, and each integrated strictly increasing function is strictly convex. Thus $F$ is a strictly convex function on $y\ge 0$. Since $U$ tends to a positive limit on every coordinate, $F$ is a coercive function there; it has a unique minimizer. Its coordinate derivative isThe Erlang fixed point equation is exactly ${\partial }_{j}F=0$. For an unused link, $a_j=0$ and the optimum is $y_j=0$; for a used link with positive offered load, the derivative at zero is negative and the optimum is positive. Hence every fixed point gives the unique minimizer, and the minimizer gives a fixed point. The Erlang fixed point is unique under these fixed-routing assumptions.

A convergent cyclic substitution for the Erlang fixed point updates one coordinate at a time, repeatedly cycling through all links:Always use the most recently available values of the other coordinates. Start, for example, with $B=0$. In $y$ coordinates this is exact coordinate descent for $F$: with other coordinates fixed, the displayed update is the unique coordinate minimizer.

Here is a convergence proof. All iterates stay in the initial compact sublevel set of the coercive function $F$, and their potential values decrease to a limit. Each single-coordinate update is continuous, since its reduced load is continuous and finite and $E(a,C)<1$. Thus a whole-sweep map $T$ is continuous. If a full-sweep subsequence converges to $z$, continuity gives $F(Tz)=F(z)$, because both consecutive potential values converge to the same limit. Strict coordinate convexity means equality can occur only when no coordinate changes during that sweep. Thus $z$ minimizes every coordinate, satisfies the nonnegative-orthant first-order conditions, and is the unique global minimizer of $F$. Every subsequential limit is therefore the same point, proving convergence of the full-sweep iterates and, by continuity of the updates, all intermediate iterates. This argument applies to sequential substitution; it does not assume simultaneous updates converge.

For the M-M-1 queue with Bernoulli feedback, assume $0<\delta \le 1$. The number of service visits before departure is geometric on $1,2,\dots$, with probabilities $\delta (1-\delta {)}^{j-1}$, independent of the independent exponential visit lengths. The transform of the total time actually being served isThusThis excludes the waiting between visits. A feedback completion changes the customer's position but not the number in the system. By exponential memoryless property, the latter process has births of rate $\lambda$ and true deaths of rate $\delta \mu$ while nonempty; unsuccessful completions are self-events. It is therefore an M/M/1 number process with effective service rate $\delta \mu$, givingFor positive $\lambda$ equality is null recurrent, larger arrival rate is unstable, and $\delta =0$ admits no departure-based equilibrium.

To prove the output claim, state the relevant time reversal of a continuous-time Markov chain theorem: an equilibrium continuous-time chain satisfying detailed balance has the same reversed path law. In this reversible birth-death process, final departures are precisely downward jumps; time reversal turns them into upward jumps. Upward jumps are supplied by a state-independent Poisson clock of rate $\lambda$, so their process is Poisson. Hence the stationary final-departure process is Poisson of rate $\lambda$. This is the output conclusion of Burke theorem for the effective number process; it does not say the process of all service completions has that rate.

Put $K=N+s$, the total capacity. The customer count is an M-M-s-K queue, hence a birth-death process on $\{0,1,\dots ,K\}$. Its nonzero transition rates areThe first rate is zero at $K$ because an arrival finding the shop full is rejected. The second rate is the number of busy servers times the individual service rate.

Write $\rho =\lambda /\mu$. The detailed balance for a birth-death process recursion isThereforewhereThis is the stationary distribution of an M-M-s-K queue.

The state space is finite, and every state communicates with every other through successive births and deaths because $\lambda ,\mu >0$. The chain is therefore an irreducible Markov chain, so its invariant distribution is unique. Finally the adjacent-state identitiesare detailed balance, while all nonadjacent rates vanish in both directions. Part a now shows that the queue is reversible in equilibrium.

Let $N$ be the number of visits to the server made by one customer. Then $N$ has the geometric distribution with success parameter $\delta$, and its service periods $E_1,E_2,\dots$ are independent exponential random variables of rate $\mu$. For $s\ge 0$, the Laplace transform of the total service time $T=E_1+\cdots +E_N$ isThus

At each service completion, a successful departure reduces the queue length by one and occurs at rate $\delta \mu$ while the queue is nonempty; feedback completions leave its length unchanged. The queue-length process is therefore the birth-death process of an ordinary $M/M/1$ queue with service rate $\delta \mu$. It is positive recurrent exactly when $\lambda <\delta \mu$, and then, with $\rho =\lambda /(\delta \mu )$,

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 a birth-death process with birth rate $\lambda r^n$ in state $n$ and death rate $\mu \min (n,2)$. Its reversible weights satisfyFor $0<r<1$, the factor $r^{n(n-1)/2}$ makes their sum finite for every $\lambda ,\mu >0$. For $r=1$, the tail is geometric with ratio $\lambda /(2\mu )$, so a stationary distribution exists exactly when $\lambda <2\mu$.

The chain is an irreducible birth-death process. The detailed balance equations areso ${\pi }_{i+1}={\pi }_i/2$. Normalization gives the stationary distributionAn irreducible countable-state Markov chain that possesses a stationary probability distribution is positive recurrent. Hence $X$ is positive recurrent.

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.

This is a birth-death process with birth and death ratesIts transition diagram has the two arrowsThe gain into state $n$ comes from a death in state $n+1$ or a birth in state $n-1$, while the loss is the sum of both rates out of state $n$. The birth-death master equation is consequently

Multiplying by $n$, summing over the nonnegative integers, and shifting the summation indices shows that each birth contributes $+1$ and each death contributes $-1$. Thus the first-moment equation of a birth-death process givesAt a stationary state, use the variance identity $⟨n^2⟩=⟨n{⟩}^2+(\Delta n{)}^2$. Solving the resulting quadratic equation givesThe minus root is inadmissible whenever it is negative, namely when $(\Delta n{)}^2<\gamma /\alpha$. Equality would give zero mean, which is also incompatible with a positive immigration rate $\gamma$, so for $\gamma >0$ the minus branch requires $(\Delta n{)}^2>\gamma /\alpha$ even to be a possible mean.

For a continuum approximation, write $b(n)=\gamma +\beta n$ and $d(n)=\alpha n(n-1)$. Applying the Kramers-Moyal expansion to the two gain terms and retaining derivatives through second order gives the Fokker-Planck equationwhere the negative drift and infinitesimal jump variance areThis truncation requires the typical population and the scale on which $P$ varies to be much larger than the unit jump size, with the rates varying smoothly across that scale.

The positive zero of $g$ isso in particular $n_{\ast }\sim \beta /\alpha$ as $\alpha /\beta \to 0$. Put $x=n-n_{\ast }$. The linear noise approximation useswhereand, because $b(n_{\ast })=d(n_{\ast })$,In a stationary state with zero Fokker-Planck probability current,Its normalized solution is the normal distributionIt follows that

These estimates agree with the exact stationary first-moment relation on its plus branch to leading order: inserting $(\Delta n{)}^2\sim \beta /\alpha$ gives $⟨n⟩\sim \beta /\alpha$. Moreover,Thus the stationary mass lies far from the boundary $n=0$, is narrow relative to its mean, yet changes across many lattice sites. These are precisely the large-population and slow-variation conditions needed for the diffusion approximation.

The transition rates of this birth-death process are $q_{n,n+1}=\lambda n$ and $q_{n,n-1}=n(\gamma +\beta n)$. Thus, with $p_{-1}=0$,Multiplying by $n$, summing, and shifting indices givesAt a finite-moment steady state with positive mean and $\lambda >\gamma$,Since $\mathbb{E}(N^2)\ge (\mathbb{E}N{)}^2$, this impliesIf $\lambda \le \gamma$, both terms in the mean equation are nonpositive, and stationarity forces $\mathbb{E}N=0$. Thus the population is extinct almost surely in any such steady state.

This birth-death process has birth rates $b_n=\alpha +\beta n$ and death rates $d_n=\gamma n(n-1)$. With $P_{-1}=0$, its birth-death master equation isThe first two terms are inflow by a birth from $n-1$ and a death from $n+1$; the bracketed term is the total outflow from $n$.