At an $\mathrm{M} / \mathrm{G} / 1$ queue, the arrival times form a Poisson process of rate $\lambda$ while service times $S_{1}, S_{2}, \ldots$ are independent of each other and of the arrival times and have a common distribution $G$ with mean $\mathbb{E} S_{1}<+\infty$.

(i) Show that the random variables $Q_{n}$ giving the number of customers left in the queue at departure times form a Markov chain.

(ii) Specify the transition probabilities of this chain as integrals in $\mathrm{d} G(t)$ involving parameter $\lambda$. [No proofs are needed.]

(iii) Assuming that $\rho=\lambda \mathbb{E} S_{1}<1$ and the chain $\left(Q_{n}\right)$ is positive recurrent, show that its stationary distribution $\left(\pi_{k}, k \geqslant 0\right)$ has the generating function given by

$$\sum_{k \geqslant 0} \pi_{k} s^{k}=\frac{(1-\rho)(s-1) g(s)}{s-g(s)},|s| \leqslant 1$$

for an appropriate function $g$, to be specified.

(iv) Deduce that, in equilibrium, $Q_{n}$ has the mean value

$$\rho+\frac{\lambda^{2} \mathbb{E} S_{1}^{2}}{2(1-\rho)}$$