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

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.

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.

There is now no separate rate-$\nu$ clockwise transition. The only transitions areBoth preserve $m+n$ modulo $M$. The initial state therefore selects the closed communicating class $m+n\equiv 0(\mathrm{mod}M)$, on which $m\equiv -n(\mathrm{mod}M)$. The population is a birth-death process with birth rate ${\lambda }_{-n}$ and death rate $\mu$.

Define $a_0=1$ and $a_r={\mu }^{-r}{\prod }_{j=0}^{r-1}{\lambda }_{-j}$ for $1\le r<M$. The detailed balance for a birth-death process weights areWriting $n=kM+r$ with $0\le r<M$, the product condition gives $w_n=a_r{\rho }^{kM}$. Summing the resulting geometric series yieldsThis is also the law in part (b) conditioned on $m+n\equiv 0(\mathrm{mod}M)$: the ratio of its weights at consecutive accessible populations is ${\lambda }_{-n}/\mu$. The stability condition is $\mu >\nu$, which uses the product of the periodic birth rates; it does not require $\mu >{\lambda }_m$ for every $m$.