Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 2 / 27I (Applied Probability)

Independence and the moment-generating function of an exponential distribution giveFor each fixed $\theta$, taking logarithms and using $-\log (1-x)\sim x$ yields ${\varphi }_{S_k}(\theta )\to e^{\theta /\mu }$. The limiting service time is the constant $S=1/\mu$. Its moment-generating function is exactly this limit.

An M/G/1 queue has Poisson process arrivals of rate $\lambda$, independent identically distributed service times of law $G$, one server, and here infinite waiting capacity. Use first-come-first-served service. Let $X_n$ be the number left just after the $n$th departure. During the next service, let $A_n$ be the number of arrivals. ThenConditional on the next service time $S_n=s$, $A_n$ is Poisson with mean $\lambda s$. If $X_{n-1}=0$, the server waits for one arrival to start service; that arrival is the customer being served, and is not counted in $A_n$. This constructs the embedded Markov chain.

For the busy-period branching equation, during the first service of a busy period, every arriving customer initiates a subtree of further work. The independence and stationary increments of the Poisson process, together with independent services, give the distributional recursionwhere conditional on $S_k=s$, $N(S_k)$ is Poisson with mean $\lambda s$, and the descendant busy periods are independent copies of $B_k$. One may explore these subtrees in order; the server's total workload is unchanged by that ordering. Consequently, wherever the moment-generating functions are finite,For $\lambda <\mu$, this identity in particular holds in a sufficiently small neighbourhood of zero.

The first arrival time $A$ has an exponential distribution of rate $\lambda$ and is independent of the following busy period. ThusSubstitute ${\varphi }_{B_k}=(\lambda -\theta ){\varphi }_{T_k}/\lambda$ into part (c). Its service-transform argument becomes $\theta +\lambda ({\varphi }_{B_k}-1)=(\lambda -\theta )({\varphi }_{T_k}-1)$. ThereforeAs before, positive arguments must lie in the domain of finite moment-generating functions.

Passing to the deterministic-service limit in part (c), near zero, givesDifferentiation at zero gives $\mathbb{E}B=(1+\lambda \mathbb{E}B)/\mu$. Alternatively, the same branching expectation equation gives $\mathbb{E}{B}_k=1/(\mu -\lambda )$ for every $k$, because $\mathbb{E}{S}_k=1/\mu$. The assumed convergence of finite moment-generating functions at a positive point near zero bounds exponential moments and makes these means uniformly integrable, so the means pass to the limit. Since $T=A+B$, the answers areThey correspond to an M/D/1 queue with deterministic service time $1/\mu$. The calculation only needs finite transforms near zero; the literal assumption of finite transforms for every $\theta <\lambda$ is stronger than necessary and is not generally true for positive busy-period arguments. For instance, with $k=1$ and $\lambda =\mu /2$, part (c) gives $\lambda b^2-(\mu +\lambda -\theta )b+\mu =0$. Its discriminant is negative for $(\sqrt{\mu }-\sqrt{\lambda }{)}^2<\theta <\lambda$, so no finite busy-period transform can exist there.