Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 30 / 1

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.

An open migration process has finitely many colonies and state $n\in {\mathbb{N}}^J$. External arrivals to colony $j$ form independent Poisson processes with rates ${\nu }_j$. When $n_j=k>0$, individuals leave that colony at total rate $g_j(k)>0$, with $g_j(0)=0$. A departing individual moves to $k$ with probability $p_{jk}$ or exits with probability $p_{j0}=1-{\sum }_k{p}_{jk}$. The routing choices and all arrival and service randomness are independent. The routing matrix $P=(p_{jk})$ is substochastic and transient: every individual eventually exits, equivalently its spectral radius is less than one. Self-routing is allowed, but creates no state change.

The traffic equations of an open migration process, using row vectors, areThe inverse matrix exists because ${\sum }_{m\ge 0}{P}^m$ converges; its $(k,j)$ entry counts expected visits to $j$ by an individual entering at $k$. Thus ${\alpha }_j$ includes both external arrivals and internal migrations. Restrict first to the accessible colonies with ${\alpha }_j>0$.

SetIf each $Z_j<\infty$, the candidate product-form stationary distribution of an open migration process isHere is a global balance for a continuous-time Markov chain proof, which does not incorrectly assume that the routing is reversible. The weight ratio is $\pi (n+e_j)/\pi (n)={\alpha }_j/g_j(n_j+1)$. After dividing the incoming balance equation at $n$ by $\pi (n)$, external arrivals contribute ${\sum }_{j:n_j>0}{\nu }_j{g}_j(n_j)/{\alpha }_j$, exits contribute ${\sum }_j{\alpha }_j{p}_{j0}$, and migrations from $k$ to $j\ne k$ contribute ${\sum }_{j:n_j>0}{\sum }_{k\ne j}{g}_j(n_j){\alpha }_k{p}_{kj}/{\alpha }_j$. Combining the first and third contributions using the traffic equations of an open migration process yields ${\sum }_j{g}_j(n_j)(1-p_{jj})$. Summing those same traffic equations of an open migration process gives ${\sum }_j{\alpha }_j{p}_{j0}={\sum }_j{\nu }_j$. The incoming rate is therefore exactly the outgoing rateThis proves stationarity. With finite arrival rates, finite service rates in each state and transient routing, the process is nonexplosive: only finitely many individuals enter in a finite interval, and each makes finitely many routing transitions before exit, almost surely. On the accessible irreducible Markov chain, a finite normalizer gives the unique stationary distribution and positive recurrence. Colonies with zero effective arrivals are empty in this equilibrium. For a nonempty accessible colony, a divergent $Z_j$ prevents normalization of the equilibrium weights.

For the single-server specialization, $g_j(k)={\varphi }_j$ for $k>0$. Each colony has the stationary distribution of an M-M-1 queue:requiring ${\varphi }_j>{\alpha }_j$ on every colony with positive traffic. The service rates do not change the traffic equations of an open migration process.

For positive ${\alpha }_j$, write $B=F-{\sum }_j{\alpha }_j$ and $s_j={\varphi }_j-{\alpha }_j$. A stable allocation requires $B>0$ and $s_j>0$, with ${\sum }_j{s}_j=B$. The Cauchy-Schwarz inequality givesEquality holds precisely when $s_j$ is proportional to $\sqrt{{\alpha }_j}$. Hence the unique optimal service-capacity allocation in an open migration process and its mean population areThere is no stable allocation when $F\le {\sum }_j{\alpha }_j$ and some traffic is positive. If some ${\alpha }_j=0$, those empty colonies contribute no population; allocate the spare capacity to the positive-traffic colonies by the same rule. Allowing zero capacity at an unused colony attains this optimum. If strictly positive ${\varphi }_j$ are required even there, the displayed value is only an infimum, approached as their capacities tend to zero. If every ${\alpha }_j=0$, the equilibrium is empty and any admissible allocation minimizes its mean population at zero.