Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 4 / 26K (Applied Probability)

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.

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.