4. M/M Queues

4.1 Markov process

Definition 4.1.1   A random exponential variable $X$ with parameter $\lambda>0$ is distributed according to:

$$Pr\left(X\in\left[t,\, t+\, \mathrm{d}t\right]\right)=Cte\times\exp\left(-\lambda\, t\right)\, \mathrm{d}t$$

Proposition 4.1.2   For an exponential variable, we have:

$$Cte=\lambda,\qquad\mathrm{E}\left(X\right)=\frac{1}{\lambda},\qquad\mathrm{var}\left(X\right)=\frac{1}{\lambda^{2}}$$

Preuve. Using $x=\lambda\, t$ leads to the following results:

$$1=\int_{t=0}^{t=\infty}Cte\,\exp\left(-\lambda\, t\right)\, \math... ...x=\infty}\exp\left(-x\right)\frac{1}{\lambda}\mathrm{d}=\frac{1}{\lambda}\, Cte$$

$$\mathrm{E}\left(t\right)=\int_{t=0}^{t=\infty}t\,\exp\left(-\lamb... ...}^{x=\infty}\frac{1}{\lambda}x\,\exp\left(-x\right)\mathrm{d}=\frac{1}{\lambda}$$

$$\mathrm{E}\left(t^{2}\right)=\int_{t=0}^{t=\infty}t^{2}\,\exp\lef... ...rac{1}{\lambda^{2}}x^{2}\,\exp\left(-x\right)\mathrm{d}=\frac{1}{\lambda^{2}}2!$$

$\qedsymbol$

Proposition 4.1.3   The exponential distribution is to be applied when $Pr\left(t>A+B\,\vert\, t>B\right)=Pr\left(t>A\right)$, i.e. when the distribution of the time to wait for an arrival is the same whatever is the starting time of the observation.

Preuve. This comes from:

$$Pr\left(t>A+B\right)=\int_{t=A+B}^{t=\infty}\exp\left(-\lambda\, ... ...right)=\exp\left(-\lambda\, A\right)\times\exp\left(-\lambda\, B\right)\qedhere$$

$\qedsymbol$

Definition 4.1.4   A M/M queue is a waiting queue where both arrivals and services are independent and exponentially distributed.

Proposition 4.1.5   When i.e.  $b\left(t\right)=\mu\,\exp\left(-\mu\, t\right)$, i.e. when services are exponentialy distributed with flow $\mu$, the time distribution of the services is $B\left(t\right)=\mu^{2}\, t\,\exp\left(-\mu\, t\right)$ and we have:

$$\mathrm{E}\left(b\right)=\frac{1}{\mu}\quad;\quad\mathrm{E}\left(B\right)=\frac{2}{\mu}$$

Remark 4.1.6   If you chose (uniformly) a time tick to observe the queue and repeat until you see a running service, this service is longer than average, because that is the reason why you observe this service, rather a shorter one. But your observation takes place at random during the service, the expected value being the middle of that service. And we obtain again that the time to wait to next arrival from a random point in the time line is $\left(1/2\right)\times\left(2\,\mu\right)$, i.e. the expected value of an inter-arrival.

4.2 Number of customers arriving in a time interval

Theorem 4.2.1   When the inter-arrivals are independent and exponentially distributed, the number $n$ of customers arriving in an time interval of fixed length $T$ is Poisson distributed and we have:

$$Pr\left(n=k\right)=\frac{\left(\lambda\, T\right)^{k}}{k!}\exp\left(-\lambda\, T\right)$$

Preuve. Define $t$ as the date of the first arrival occuring after the begining of the observation. In order to have $n=0$, we must have $t>T$ and therefore $Pr\left(n=0\right)=\int_{T}^{\infty}\lambda\,\exp\left(-\lambda\, t\right)\, \mathrm{d}t=\exp\left(-\lambda\, T\right)$.

Suppose now that $n=k+1$. Obviously $T=t+\tau$ where $\tau>0$, and $k$ customers arrive in the time interval $\left[t,\, T\right]$ whose lenght is $\tau$. Using the total probability formula and an obvious recurrence, we obtain:

$$Pr\left(n=k+1\right)=\int_{\tau=0}^{\tau=T}\,\frac{\left(\lambda\... ...ght)\times\exp\left(-\lambda\left(T-\tau\right)\right)\,\lambda\,\mathrm{d}\tau$$

where factors $\exp\left(\pm\lambda\,\tau\right)$ cancel, leading to the requested result. $\qedsymbol$

Proposition 4.2.2   Expectation and variance of a Poisson distribution are both equal to the parameter. Here:

$$\mathrm{E}\left(n\right)=\lambda\, T\qquad;\qquad\mathrm{var}\left(n\right)=\lambda\, T$$

Preuve. The first result is obvious, and the second can be obtained by:

$$\mathrm{var}\left(n\right)=\mathrm{E}\left(n^{2}-n\right)+\mathrm{E}\left(n\right)-\left(\mathrm{E}\left(n\right)^{2}\right)$$

$$\mathrm{E}\left(n^{2}-n\right)=e^{-\lambda T}\,\sum_{k=0}k\left(k... ...{-\lambda T}\, p^{2}\,\sum_{k=2}\frac{p^{k-2}}{\left(k-2\right)!}=p^{2}\qedhere$$

$\qedsymbol$

Remark 4.2.3   The result $\mathrm{E}\left(n\right)=\lambda\, T$ confirms the fact that $\lambda$ is the flow of arrivals. The result $\mathrm{E}\left(n\right)=\mathrm{var}\left(n\right)$ confirms the fact that $n$ is a number, i.e. a dimensionless quantity.

Proposition 4.2.4   When services are iid exponential (M distributed), the time expectation of a service is exactly twice the individual expectation, and the expectation of the (assumed non zero) residual service, as seen by the incomming customer, is exactly the individual expectation.

Preuve. From $b\left(t\right)=\mu\,\exp\left(-\mu\, t\right)$, $\mathrm{E}\left(t\right)=\frac{1}{\mu}$ one obtains $B\left(t\right)=\mu^{2}\, t\,\exp\left(-\mu\, t\right)$ and therefore $\mathrm{E}\left(B\right)=\frac{2}{\mu}$ : you are arriving during the service of this custommer (rather than during another service) because of a greater duration of this service. From the PASTA property (Wolff, 1982), your arrival is at (uniform) random during this service and the average residual service is half the time average. $\qedsymbol$

4.3 Théorème des débits de Poisson

Theorem 4.3.1   The sojourn times in a M/M queue with arrival and service flows $\lambda$ and $\mu>\lambda$ are exponentially distributed, with parameter $\mu-\lambda$. Especially, the average sojourn time is:

$$\mathrm{E}\left(sojourn\right)=\frac{1}{\mu-\lambda}$$

Remark 4.3.2   In this theorem, the flow value for clearing the queue from a busy state is obvious. The content of the theorem is the exponential distribution that allows to link customer/server observations, i.e. number and time averages.

Example 4.3.3   Let us consider a physician office where the flow of patients is around three per hour, and the consultations last about 15 minutes. Assuming a M/M model, the average sojourn time of a patient will be one hour. Using $\lambda$, we see that the time average occupancy is three patients inside or outside the examination room. Using $\mu$, we see that the average number of patients just after an arrival is four, including the incoming one and, if she/he exists, the patient being examinated. For a less crude model, see Gilchrist et al., 2005.

4.4 Pollaczek-Khintchine formula for M/G queues

Theorem 4.4.1   Consider an M/G waiting queue with load $\rho=\mathrm{E}\left(service\right)/\mathrm{E}\left(arrival\right)$. Then:

$$\mathrm{E}\left(sojourn\right)=\mathrm{E}\left(service\right)\tim... ...^{2}\right)}{2\,\mathrm{E}\left(service\right)^{2}}\,\frac{\rho}{1-\rho}\right)$$

Preuve. Assume the next coming . $\qedsymbol$

Theorem 4.4.2 (Pollaczek-Khintchine)   Consider an M/G waiting queues with incoming exponential flow $\lambda$ and workload pdf of service $f$. Denote the pdf of the sojourn time by $h$. Then