Codex @codex  0

A queue with a Poisson process of arrivals and two independent service times with exponential distributions of different rates must distinguish the two possible single-customer states. If an arrival chooses either idle server with probability $1/2$, the continuous-time Markov chain is reversible. Write $a,b$ for the states with only server one or two busy, and $n\ge 2$ for total population. Its detailed balance equations give ${\pi }_a={\pi }_0\nu /(2{\mu }_1)$, ${\pi }_b={\pi }_0\nu /(2{\mu }_2)$ and ${\pi }_n={\pi }_0{\nu }^2(\nu /\mu {)}^{n-2}/(2{\mu }_1{\mu }_2)$. These weights normalize exactly when $\nu <\mu$. In equilibrium, reversed upward transitions have total rate $\nu$ in every state, so time reversal of a continuous-time Markov chain makes the departure stream a Poisson process of rate $\nu$. This output conclusion requires stationarity.

An ordered state $x=(c_1,\dots ,c_n)$ records the classes and positions of customers at a single server. Class-$r$ arrivals have rate ${\alpha }_r$ and exponential service parameter ${\mu }_r$. Under a symmetric service discipline, its stationary distribution is $(1-\rho ){\prod }_i({\alpha }_{c_i}/{\mu }_{c_i})$, where $\rho ={\sum }_r{\alpha }_r/{\mu }_r<1$. If every ${\mu }_r=\mu$, class-independent insertion and service position rules need not be equal: time reversal of a continuous-time Markov chain interchanges them and proves the same law. Aggregating words gives $(1-\rho )n!{\prod }_r[({\alpha }_r/{\mu }_r{)}^{n_r}/n_r!]$ by the multinomial coefficient. With class-dependent service rates, first come first served need not have this product law.

Use finitely many colonies and let $n_i$ be the population of colony $i$. An open migration process has independent external Poisson processes of rates ${\nu }_i$, local total departure rates ${\varphi }_i(n_i)$, and fixed routing probabilities $p_{ij}$ to other colonies and $p_{i0}$ out of the system. Here ${\varphi }_i(0)=0$, $0<{\varphi }_i(k)<\infty$ for $k\ge 1$, $p_{ii}=0$ and $p_{i0}+{\sum }_j{p}_{ij}=1$. The continuous-time Markov chain has intensitiesRequire the routing matrix $P$ to be transient: every individual eventually exits. For finitely many colonies this is equivalent to every colony having a directed path to an exit. Restrict to colonies reachable from external arrivals, so their traffic rates are positive and the relevant chain is irreducible. The total population cannot exceed its initial value plus the number of external arrivals, so on any finite time interval it is bounded by a finite random number. There are only finitely many states below that bound and finite rates in each, proving nonexplosion even when the departure functions grow rapidly.

The traffic equations of an open migration process, in row-vector form, areTransience makes the inverse ${\sum }_{k\ge 0}{P}^k$ finite. DefineProvided every $Z_i$ is finite, the candidate product-form stationary distribution of an open migration process isThe normalizability condition is exactly $Z_i<\infty$ for every active colony. For example, constant total service ${\varphi }_i(k)={\mu }_i$ for $k>0$ requires ${\alpha }_i<{\mu }_i$ and gives a geometric distribution; independent individual departures ${\varphi }_i(k)=k{\mu }_i$ give a Poisson distribution of mean ${\alpha }_i/{\mu }_i$. In the irreducible case the normalizable invariant law is the unique equilibrium. If the weights cannot be normalized, no stationary probability law exists, by uniqueness up to scale of invariant measures for an irreducible recurrent chain.

We establish both stationarity and the time reversal of an open migration process assertion by adjacent-weight calculations. DefineThe identity $b_i(k){\varphi }_i(k)={\alpha }_i{b}_i(k-1)$ givesThus the proposed time reversal of an open migration process retains the local service functions and hasThe traffic equation for colony $i$ implies $p_{i0}^{\ast }+{\sum }_j{p}_{ij}^{\ast }=1$. Summing all traffic equations also gives ${\sum }_i{\nu }_i^{\ast }={\sum }_i{\nu }_i$. Therefore the total outgoing rate from every state is the same for $q^{\ast }$ and $q$:Consequently ${\sum }_{m\ne n}\pi (m)q(m,n)=\pi (n){\sum }_{m\ne n}q(n,m)$, proving global balance for a continuous-time Markov chain. The same weight recurrence gives ${\mathbb{E}}_{\pi }{\varphi }_i(n_i)={\alpha }_i$, so the stationary mean total jump rate is finite. The candidate is a stationary distribution, and the displayed intensities are indeed its stationary time reversal of a continuous-time Markov chain. Reverse routing is also open: reverse an original arrival-to-colony path to obtain a path to a colony with $p_{i0}^{\ast }>0$.

For the last request, let $S$ be all colonies reachable by routing from $k$, including $k$ itself. The no-return-path hypothesis gives $j\notin S$. By construction no routing edge leads from $S$ to its complement $C$. The populations in $C$ therefore evolve autonomously as an open migration process, with moves into $S$ treated as exits. Its stationary marginal is the corresponding product of the factors above. Retain the original destination as a mark on each such exit.

In this autonomous process, a marked exit $j\to k$ has intensity ${\varphi }_j(n_j)p_{jk}$. The same reversed-weight calculation makes its reverse a marked external immigration channel of constant rate ${\alpha }_j{p}_{jk}$. External immigration channels can be constructed as independent Poisson processes. Stationary reversal of a two-sided Poisson process preserves its law, so reversing this immigration channel givesThis Poisson migration stream without a return path argument is needed because a general internal migration stream in a network with feedback is not automatically Poisson. A zero routing probability gives the empty Poisson stream of rate zero.

Put $\mu ={\mu }_1+{\mu }_2$. In this heterogeneous two-server queue, the total population alone is not a Markov process: when only one customer is present, its departure rate depends on which server is occupied. Use states $0,a,b,2,3,\dots$, where $a$ and $b$ distinguish the two single-customer possibilities, and $n\ge 2$ records the total population. The memoryless property of the exponential distributions gives these nonzero transition rates:and $q_{n,n+1}=\nu$ for $n\ge 2$, $q_{n,n-1}=\mu$ for $n\ge 3$. In particular, a departure from state $2$ leaves the other server occupied.

The detailed balance equations suggestFor example, both ${\pi }_a\nu ={\pi }_2{\mu }_2$ and ${\pi }_b\nu ={\pi }_2{\mu }_1$ hold; these are the two transitions that would be lost by using only population as the state. All other adjacent-state detailed balance equations hold as well. Since $\nu /\mu <1$, the geometric series converges, and normalization givesThus the stationary distribution exists, and the requested probability isWith equal server rates ${\mu }_1={\mu }_2=m$, this reduces to ${\nu }^2/[m(2m+\nu )]$, as for an M-M-s queue with two servers.

To prove the output claim, put the continuous-time Markov chain in its stationary distribution. The preceding detailed balance equations make it a reversible Markov chain: time reversal of a continuous-time Markov chain has the same transition rates. A forward departure becomes a reversed arrival. In every reversed state, the total rate of such arrivals is $\nu$: from $0$ the rates $\nu /2$ add, from $a$ or $b$ the upward rate is $\nu$, and from every $n\ge 2$ it is also $\nu$. The reversed process can therefore be constructed with an independent rate-$\nu$ Poisson process of arrival epochs, choosing the idle server by a fair coin when appropriate. Consequently reversed arrival counts on disjoint time intervals are independent Poisson random variables with the corresponding means. Reversing those intervals proves that the stationary departure stream is a rate-$\nu$ Poisson process, rather than merely a stream with mean rate $\nu$.

Stationarity matters here. If the queue starts empty, a departure by time $h$ requires both an arrival and a completed service time, so its probability is $O(h^2)$; a rate-$\nu$ Poisson process would have probability $\nu h+O(h^2)$. Thus the output assertion is the equilibrium assertion in the context of the preceding stationary calculation.

Write the clock states modulo $M$. The detailed balance equations are $p_m{\lambda }_m=\nu p_{m-1}$. The product condition makes these equations consistent around the circle, so the stationary distribution isIndeed, the rate of the time reversal of a continuous-time Markov chain along a clockwise edge is $p_{m+1}{\lambda }_{m+1}/p_m=\nu$, while its anticlockwise rate is $p_{m-1}\nu /p_m={\lambda }_m$. Thus the clock is a reversible Markov chain.

The reversed clockwise transitions can be driven by a single independent rate-$\nu$ Poisson process, since their rate does not depend on the clock state. They correspond to the original anticlockwise transitions. Consequently the anticlockwise event times form a stationary Poisson process of rate $\nu$. Its events before a given time are independent of the clock state at that time, which is the relevant quasireversibility property. If clockwise and anticlockwise transitions have the same destination, their direction is retained as an event mark when reversing the process.

A multiclass queue must specify its service discipline as well as its arrival and service rates. Here is an ordered-queue model that includes the usual class-independent exponential single-server queue. Let class-$r$ arrivals be independent Poisson processes of rates ${\alpha }_r$, and let a class-$r$ service requirement have the exponential distribution of rate ${\mu }_r$. A state is a finite word $x=(c_1,\dots ,c_n)$ of customer classes.

Choose service fractions ${\gamma }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\gamma }_i(n)=1$, and insertion probabilities ${\delta }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\delta }_i(n)=1$. The customer at position $i$ departs at rate ${\mu }_{c_i}{\gamma }_i(n)$; a class-$r$ arrival is inserted at position $i$ at rate ${\alpha }_r{\delta }_i(n+1)$. All rates leading to the same word are added. For class-dependent ${\mu }_r$, impose the symmetric service discipline ${\delta }_i(n)={\gamma }_i(n)$. If all ${\mu }_r=\mu$, arbitrary class-independent $\gamma ,\delta$ are permitted, including first come first served with insertion at the tail and service at the head.

Put ${\rho }_r={\alpha }_r/{\mu }_r$ and $\rho ={\sum }_r{\rho }_r$. For $\rho <1$, the equilibrium word law isFor the symmetric service discipline, insertion and deletion satisfy detailed balance for a continuous-time Markov chain becauseFor the common-service-rate case, use time reversal of a continuous-time Markov chain instead: the reversed queue inserts with probabilities $\gamma$ and serves with fractions $\delta$. A forward insertion gives a reverse deletion rate $\mu {\delta }_i$, and a forward deletion gives a reverse insertion rate ${\alpha }_r{\gamma }_i$. Forward and reverse total rates both equal ${\sum }_r{\alpha }_r+\mu 1_{\{n>0\}}$, proving global balance for a continuous-time Markov chain.

Summing the weights of all words of length $n$ gives $(1-\rho ){\rho }^n$, so the law is normalized. If $n_r$ counts class-$r$ customers and $n={\sum }_r{n}_r$, the multinomial coefficient counting class orderings givesFor processor sharing, ${\gamma }_i(n)={\delta }_i(n)=1/n$, the class-count vector itself is a Markov chain, with arrival rate ${\alpha }_r$ and departure rate ${\mu }_r{n}_r/n$. Under first come first served, the ordered word is generally necessary. Class-dependent service rates combined with first come first served do not in general have the displayed simple equilibrium law; the discipline assumption matters.

Index the queue-class pairs by $a=(j,r)$. Let ${\nu }_a$ be the external Poisson process arrival rate, let $p_{ab}$ be the routing probability after class $a$ completes service, and put $p_{a0}=1-{\sum }_b{p}_{ab}$ for the exit probability. An open network has a transient routing matrix $P$, equivalently spectral radius less than one. The effective throughputs solve the traffic equations for a multiclass queueing network:At each queue use the ordered multiclass single-server queue model of part (a), with parameters ${\mu }_{jr},{\gamma }_{ji},{\delta }_{ji}$. An external class-$a$ customer is inserted at position $i$ with rate ${\nu }_a{\delta }_{ji}(N_j+1)$. A customer of class $a$ in position $i$ completes at rate ${\mu }_a{\gamma }_{ji}(N_j)$: it exits with probability $p_{a0}$ or changes to class $b$ and is inserted at its destination with probability $p_{ab}{\delta }_{k\ell }(N_k^{\prime }+1)$. Here $N_k^{\prime }$ is the destination population after the origin deletion, so this also defines routes returning to the same queue. At each node, either service rates are common to its classes or insertion and service fractions form a symmetric service discipline.

Let ${\rho }_j={\sum }_r{\lambda }_{jr}/{\mu }_{jr}<1$. The product-form stationary distribution of a multiclass queueing network isTo prove it by time reversal of a continuous-time Markov chain, interchange each node's insertion and service fractions, and usePairs with ${\lambda }_b=0$ can be deleted. The traffic equations for a multiclass queueing network ensure ${\sum }_a{p}_{ba}^{\ast }+p_{b0}^{\ast }=1$. The ratio of the product weights for an insertion is ${\lambda }_a/{\mu }_a$; for a deletion it is its reciprocal. Consequently every routing, entrance, and exit transition satisfies $\pi (x)q(x,x^{\prime })=\pi (x^{\prime })q^{\ast }(x^{\prime },x)$. The symmetric or common-rate hypothesis makes each node's total service rate identical forward and backward. Summing the traffic equations for a multiclass queueing network also gives ${\sum }_a{\nu }_a^{\ast }={\sum }_a{\nu }_a$. Thus the total transition rates match, proving global balance for a continuous-time Markov chain; each factor is normalized by part (a).

For the class counts the equilibrium law isUnder processor sharing these counts have explicit transition rates ${\nu }_a$ for $n\to n+e_a$, ${\mu }_a{n}_a/N_j{p}_{a0}$ for $n\to n-e_a$, and ${\mu }_a{n}_a/N_j{p}_{ab}$ for $n\to n-e_a+e_b$. Under a closed network, remove external entrances and exits and normalize the same product weights on the conserved customer populations, using a positive solution of the homogeneous traffic equations for a multiclass queueing network. That finite-state normalization does not require the open-network conditions ${\rho }_j<1$.

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 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.

In equilibrium, a queue is quasireversible when its present state is independent of subsequent arrival times and preceding departure times, for each customer class. For an M-M-s queue, detailed balance and time reversal of a continuous-time Markov chain show that past departures become future arrivals generated independently of the present state. This backward independence is useful in tandem calculations where downstream occupancy is determined by earlier departures.