Consider an $M / G / 1$ queue with $\rho=\lambda \mathbb{E} S<1$. Here $\lambda$ is the arrival rate and $\mathbb{E} S$ is the mean service time. Prove that in equilibrium, the customer's waiting time $W$ has the moment-generating function $M_{W}(t)=\mathbb{E} e^{t W}$ given by

$$M_{W}(t)=\frac{(1-\rho) t}{t+\lambda\left(1-M_{S}(t)\right)}$$

where $M_{S}(t)=\mathbb{E} e^{t S}$ is the moment-generating function of service time $S$.

[You may assume that in equilibrium, the $M / G / 1$ queue size $X$ at the time immediately after the customer's departure has the probability generating function

$$\left.\mathbb{E} z^{X}=\frac{(1-\rho)(1-z) M_{S}(\lambda(z-1))}{M_{S}(\lambda(z-1))-z}, \quad 0 \leqslant z<1 .\right]$$

Deduce that when the service times are exponential of rate $\mu$ then

$$M_{W}(t)=1-\rho+\frac{\lambda(1-\rho)}{\mu-\lambda-t}, \quad-\infty<t<\mu-\lambda .$$

Further, deduce that $W$ takes value 0 with probability $1-\rho$ and that

$$\mathbb{P}(W>x \mid W>0)=e^{-(\mu-\lambda) x}, \quad x>0 .$$

Sketch the graph of $\mathbb{P}(W>x)$ as a function of $x$.

Now consider the $M / G / 1$ queue in the heavy traffic approximation, when the service-time distribution is kept fixed and the arrival rate $\lambda \rightarrow 1 / \mathbb{E} S$, so that $\rho \rightarrow 1$. Assuming that the second moment $\mathbb{E} S^{2}<\infty$, check that the limiting distribution of the re-scaled waiting time $\tilde{W}_{\lambda}=(1-\lambda \mathbb{E} S) W$ is exponential, with rate $2 \mathbb{E} S / \mathbb{E} S^{2}$.