Little’s Law

$\bar{N}=\lambda \bar{W}.$

Here $\bar{N}$ is the long run queue length; $\bar{W}$ is the expected waiting time; $\lambda$ is the arrival rate at the queue.

Little’s Law is one of applied probability’s most robust results.

$N(t)$ is the number of customers in a queue at time $t\geq 0$ .
$A(t)$ is the total number of arrivals at the queue by time $t\geq 0$ . $A(0)$ includes customers at the queue at time $0$ .
Let $W_k$ be the waiting time of the $k$ -th arrival at the queue. That is the time from arrival until departure.

It relates mean queue length to waiting times and arrival rates.

Lemma (Little’s Law): We assume the number of customers $N(t)$ is smaller than $t$ : $\lim_{t\rightarrow\infty}\frac{N(t)}{t} = 0.$ Assuming there is a long run waiting time $\bar{W}$ and a long run arrival rate $\lambda$ , that is there are well defined limits:

$\lim_{k\rightarrow\infty} \frac{\sum_{k=1}^K W_k}{k} = \bar{W} \qquad\text{and}\qquad \lim_{t\rightarrow\infty} \frac{A(t)}{t} =\lambda\qquad \text{exist}$

then the long run queue length $\bar{N}=\lim_{t\rightarrow\infty} \frac{1}{t} \int_0^t N(s)ds$ is well defined and is given by Little’s Law:

$\bar{N}=\lambda \bar{W}.$

Proof: The average number of customers in the queue bounded above by sum of the waiting times of all arriving customers and is lower bounded by the sum of waiting times of the customers who have completed service. I.e.

$\sum_{k=1}^{A(t)-N(t)} W_k \leq \int_0^t N(s) ds \leq \sum_{k=1}^{A(t)} W_k$

Thus

$\frac{{A(t)-N(t)} }{t}\times \frac{1}{A(t)-N(t)} \sum_{k=1}^{A(t)-N(t)} W_k \leq \frac{1}{t} \int_0^t N(s) ds \leq \frac{A(t)}{t}\times \frac{1}{A(t)}\sum_{k=1}^{A(t)} W_k.$