# Expected waiting time in M/M/1 queue

What is the expected waiting time in an $$M/M/1$$ queue where order service is last-in-first-out? On service completion, the next customer served is the most recent arrived. Suppose we do not know the order of service (think of a busy retail shop that does not have a "take a number" system).

I tried many things like using $$L = \lambda w$$ but I am not able to make progress with this exercise. I am new to queueing theory and will appreciate some help. I can't find very much information online about this scenario either.

I found this online: https://people.maths.bris.ac.uk/~maajg/teaching/iqn/queues.pdf

It helped me understand more.

But it does help me with this problem.

I think that the expected waiting time (time waiting in queue plus service time) in LIFO is the same as FIFO. But I am not completely sure. I remember reading this somewhere. Maybe this can help?

Let $$X(t)$$ be the number of customers in the system at time $$t$$, $$\lambda$$ the arrival rate, and $$\mu$$ the service rate. Assume $$\rho:=\frac\lambda\mu<1$$. We have the balance equations $$\lambda \pi_n = \mu\pi_{n+1},\ n=0,1,\ldots,$$ which yield the recurrence $$\pi_n = \rho^n\pi_0$$. From $$\sum_{n=0}^\infty\pi_n=1$$ we see that $$\pi_0=1-\rho$$ and hence $$\pi_n=\rho^n(1-\rho)$$. The expected size in system is $$L = \mathbb E[\pi] = \sum_{n=1}^\infty n\pi_n = \sum_{n=1}^\infty n\rho^n(1-\rho) = \frac\rho{1-\rho}.$$ By Little's law, the mean sojourn time is then $$W = \frac L\lambda = \frac1{\mu-\lambda}.$$ Now, the waiting time is the sojourn time (total time in system) minus the service time:
$$W_q = W - \frac1\mu = \frac1{\mu-\lambda}-\frac1\mu = \frac\lambda{\mu(\mu-\lambda)} = \frac\rho{\mu-\lambda}.$$
We can further derive the distribution of the sojourn times. Let $$L^a$$ be the number of customers in the system immediately before an arrival, and $$W_k$$ the service time of the $$k^{\mathrm{th}}$$ customer. It follows that $$W = \sum_{k=1}^{L^a+1}W_k$$. Conditioning on $$L^a$$ yields \begin{align} \mathbb P(W>t) &= \sum_{n=0}^\infty \mathbb P(W>t\mid L^a=n)\mathbb P(L^a=n)\\ &= \sum_{n=0}^\infty \mathbb P\left(\sum_{k=1}^{L^a+1}W_k>t\mid L^a=n\right)\mathbb P(L^a=n). \end{align} By the so-called "Poisson Arrivals See Time Averages" property, we have $$\mathbb P(L^a=n)=\pi_n=\rho^n(1-\rho)$$, and the sum $$\sum_{k=1}^n W_k$$ has $$\mathrm{Erlang}(n,\mu)$$ distribution. So we have $$\mathbb P(W>t) = \sum_{n=0}^\infty \sum_{k=0}^n\frac{(\mu t)^k}{k!}e^{-\mu t}\rho^n(1-\rho)$$ Since the summands are all nonnegative, Tonelli's theorem allows us to interchange the order of summation: \begin{align} \mathbb P(W>t) &= \sum_{k=0}^\infty\frac{(\mu t)^k}{k!}e^{-\mu t}(1-\rho)\sum_{n=k}^\infty \rho^n\\ &= \sum_{k=0}^\infty\frac{(\mu t)^k}{k!}e^{-\mu t}\rho^k\\ &= e^{-\mu t}\sum_{k=0}^\infty\frac{(\mu\rho t)^k}{k!}\\ &= e^{-\mu(1-\rho)t}\\ &= e^{-(\mu-\lambda) t}. \end{align} So $$W$$ is exponentially distributed with parameter $$\mu-\lambda$$. To find the distribution of $$W_q$$, we condition on $$L$$ and use the law of total probability: \begin{align} \mathbb P(W_q\leqslant t) &= \sum_{n=0}^\infty\mathbb P(W_q\leqslant t, L=n)\\ &= \sum_{n=0}^\infty \mathbb P(W_q\leqslant t\mid L=n)\mathbb P(L=n)\\ &= (1-\rho)\cdot\mathsf 1_{\{t=0\}}+(1-\rho)\cdot\mathsf 1_{\{t=0\}} + \sum_{n=1}^\infty (1-\rho)\rho^n \int_0^t \mu e^{-\mu s}\frac{(\mu s)^{n-1}}{(n-1)!}\\ &= (1-\rho)\cdot\mathsf 1_{\{t=0\}}+\rho(1-\rho)\sum_{n=1}^\infty\rho^n\int_0^t \mu e^{-\mu s}\frac{(\mu\rho s)^{n-1}}{(n-1)!}\ \mathsf ds\\ &= (1-\rho)\cdot\mathsf 1_{\{t=0\}}+\rho(1-\rho)\int_0^t \mu e^{-\mu(1-\rho)s}\ \mathsf ds\\ &= (1-\rho)\cdot\mathsf 1_{\{t=0\}} + 1-\rho e^{-\mu(1-\rho)t)}\cdot\mathsf 1_{(0,\infty)}(t). \end{align}