M/M/1 queue
Section of Birth–death chains and queues, part of Stochastic processes
M/M/1 queue
| Type | Section |
| Taught in | Birth–death chains and queues |
| Part | Stochastic processes |
| Questions using it | 1 |
Arrivals are Poisson of rate \lambda. Service times are independent \mathrm{Exp}(\mu), and a single server works whenever the system is non-empty. Then \lambda_n=\lambda for every n, and \mu_n=\mu for n\ge 1. Set \rho=\lambda/\mu. The product for the weights is \pi_n=\pi_0\rho^n. The geometric series \sum_{n=0}^{\infty}\rho^n converges if and only if \rho<1, in which case \pi_0=1-\rho and
\pi_n=(1-\rho)\rho^n, \qquad n\ge 0.
If \rho\ge 1 the weights cannot be normalised. The queue length drifts to infinity and there is no stationary probability distribution.
The mean number in system, when \rho<1, is
L=\sum_{n=0}^{\infty} n(1-\rho)\rho^n=(1-\rho)\rho\sum_{n=1}^{\infty} n\rho^{n-1}=\frac{\rho}{1-\rho},
using \sum_{n\ge 1} n r^{n-1}=1/(1-r)^2 at r=\rho. The tail is geometric as well: \mathbb{P}(N\ge k)=\rho^k.
If arrivals see the time-average distribution, which Poisson arrivals do when the arrival process is independent of the past of the queue in the usual way, Little’s law gives the mean time in system W=L/\lambda. Substituting L produces
W=\frac{\rho}{\lambda(1-\rho)}=\frac{1}{\mu-\lambda}.
The mean wait diverges as \lambda approaches \mu from below. Spare capacity is then small, and the random fluctuations of arrivals and service produce long busy periods even while the mean arrival rate is still below the mean service rate.
Used in
- Taught in Birth–death chains and queues
- Questions that use it (1) — An M/M/1 queue
- All 3 questions on Birth–death chains and queues
See also
Little’s law · Birth–death balance · M/M/∞ queue · Multi-server and finite-capacity queues · Machine-repair model · Three capacity rules · Blocking, throughput, and Little’s law · Local balance