4.4 Little's Law
4.4 Little’s Law
There exists a fascinating connection, known as Little’s law, between the average sojourn time of a job in an input-output system and the long-run time-average number of jobs within that system. To heuristically understand this relationship, imagine a 100 km highway segment between points A and B. Every minute, a car enters the highway and each car maintains a constant speed of 50 km/h. Now, since each car spends 2 hours1The sojourn time equals 100 km \(/\) 50 km/h = 2 hours. on the highway, there must be \(120\) cars22 h \(\times\) 60 min/h \(\times\) 1 car/min = 120 cars. on the highway simultaneously. The objective in this section is to demonstrate that, under a few simple conditions, this relation generalizes to stochastic systems, in which case it takes the form \(\E \L = \lambda \E \J,\) i.e., the average number of `things’ in a system is the rate at which these `things’ enter times the average time they spend in the system.3Use the physical dimensions of the components of Little’s law to check that \(\E{\J} \neq \lambda \E{\L}.\)
Theorem 4.4.1.
If \(\delta = \lambda \in (0, \infty)\) and \(\frac{1}{n}\sum_{k=1}^{n} \J_{k} \to \E \J < \infty\) as \(n\to \infty,\) then the limit \(\E \L = \lim_{t\to\infty} \bar L(t)\) exists, and \(\E \L = \lambda \E \J.\)
Proof
We give the proof for single-server models.4The same result holds for multi-server queues, but then the reasoning is a bit more subtle, because jobs need no longer leave in order of arrival. Suppose we charge a job for the time it spends in the system. This can be done at arrival, while present, or upon departure. A comparison of the costs under each of these three charging schemes shows that for some job \(k\)
\begin{equation*} \J_{k} \1{D_k\leq t} \leq \int_0^t I_k(s) \d s \leq \J_k \1{A_k \leq t}, \end{equation*}where \(I_{k}(s)\) is defined in (3.1.6). Taking the sum over this inequality and using the reasoning that led to (3.1.8) gives5Observe that \(\sum_{k=1}^{\infty} \J_k \1{D_k\leq t} = \sum_{k=1}^{D(t)} \J_{k},\) and similarly for \(A(t).\)
\begin{equation*} \frac{1}{t} \sum_{k=1}^{D(t)} \J_k \leq \frac{1}{t}\int_0^t \sum_{k=1}^{\infty} I_k(s) \d s = \frac{1}{t} \int_{0}^{t}L(s) \d s \leq \frac{1}{t}\sum_{k=1}^{A(t)} \J_{k}. \end{equation*}The assumptions imply that \(D(t)\to\infty\) as \(t\to\infty.\) Thus, for the LHS,
\begin{equation*} \lim_{t\to\infty}\frac{1}{t} \sum_{k=1}^{D(t)} \J_k = \lim_{t\to\infty} \frac{D(t)}{t}\frac{1}{D(t)} \sum_{k=1}^{D(t)}\J_k = \delta \E \J. \end{equation*}Likewise, the RHS converges to \(\lambda \E \J.\) As \(\delta = \lambda< \infty,\) the limits of the LHS and RHS are the same. Consequently, the limit \(\frac{1}{t}\int_{0}^t L(s) \d s \to \E \L\) exists and \(\lambda \E \J = \E \L.\)
The conditions are subtle: assuming only that \(\delta = \lambda < \infty\) does not imply that \(\lim_{n\to\infty} \frac{1}{n}\sum_{k=1}^{n} \J_{k} < \infty.\) For example, consider a single-server queue, take \(A_k = k,\) and \(S_k = 1\) if \(k\) is not a square but \(S_k = 2\) if \(k\) is a square. Then for very large \(k,\) \(D_k \sim k + \sqrt k.\) Hence, \(A_{k}/k \to 1\) and \(D_k/k\to1.\) However, for large \(s,\) \(L(s) = A(s) - D(s) \approx \sqrt s,\) so that \(t^{-1}\int_0^t\sqrt s \d s \to \infty\) as \(t\to \infty.\)
TF 1.
Claim: Little’s law states for a rate-stable \(G/G/1\) queue that \(\E{\J}=\lambda\E{\L}.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False.
TF 2.
Claim: For Little’s law to be true for any input-output system the equality
\begin{equation*} \int_0^T L(s)\, \d s = \sum_{k=1}^{A(T)} \W_k \end{equation*}must hold for all \(T\geq 0.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. First, \(\W_{k}\) should be \(\J_{k}.\) Second, even after replacing \(\W_{k}\) by \(\J_{k},\) it is only valid at times \(T\) when the system is empty.
TF 3.
Consider the server of the \(G/G/1\) queue as a system in itself. The time jobs stay in this system is \(\E S,\) and jobs arrive at a rate \(\lambda.\) Claim: It follows from Little’s law that the fraction of time the server is busy is \(\lambda \E S.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True, Exercise 6.
TF 4.
Suppose that there are 10 jobs present in the \(M/M/1\) queue with arrival rate \(\lambda=3\) and service rate \(\mu=4\) per hour. Claim: The time to clear the system follows from Little’s law and is \(3\times 10 = 30\) hours.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False.
TF 5.
Claim: Little’s law \(\E\L = \lambda \E\J\) implies that reducing the arrival rate \(\lambda\) always reduces the average number of jobs \(\E\L\) in the system.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. Little’s law alone does not imply that \(\lambda\E\J\) decreases when \(\lambda\) decreases, because it supplies no bound on the accompanying change in \(\E\J.\) For example, with unit service times, arrivals every two time units give \(\lambda=1/2\) and \(\E\L=1/2,\) whereas pairs arriving at offsets \(0\) and \(0.1\) in each five-unit cycle give \(\lambda=2/5\) and \(\E\L=0.58.\)
Exercise 6.
Think of all servers in the (stable) \(G/G/c\) queue as being placed in a box. Jobs enter the box at a rate \(\lambda\) and stay for a duration \(\E S\) in this box. Use Little’s law to conclude that the time-average number of busy servers is \(\E{\Ls} = \lambda \E S.\)
Hint
Recall that \(\lim_{t\to\infty} t^{-1}\int_0^t \Ls(s)\d s\) is the time-average number of servers busy up to \(t.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
Since the queue is stable, the jobs leave at rate \(\lambda,\) thus each job that enters the box leaves it. The average time a job spends in the box is \(\E S.\) By Little’s law, the average number in the box is \(\E\Ls = \lambda \E S.\)
Let’s take `life’ itself as an input-output system6An application to actuarial sciences., and ask how many people are born and die in the Netherlands per week.
Exercise 7.
For simplicity, assume that in 2023 the Netherlands has 16 M inhabitants, and people have an expected lifetime (i.e., the time they remain in the system called `life’) of 80 years. By Little’s law, the rate \(\lambda\) of people entering the system (births) is \(16 M/80 = 0.2 M \) per year. For simplicity, if a year has 50 weeks, there are 4000 births per week. If the size of the population remains about constant, also around 4000 people die per week.
As it turns out, CBS records 169521 deaths in 2023, or about 3260 per week when dividing by 52. This is much lower than the estimate, and a more precise computation does not close the gap. Can you explain this paradoxical difference?
Hint
What happens if the population increases?
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
Let us make a very simple model to clarify the problem. We start with an initial population of \(A\) people and, for this heuristic, assume that everyone initially present or subsequently added remains in the population for exactly 80 more years. In year \(k=1,2,\ldots,\) we add \(A(1.01)^k\) people, so the annual increase through these additions grows by \(1\%\) per year. After 79 years, the population size is \(A \sum_{k=0}^{79}(1.01)^{k}.\) If we assume (as we do when we apply Little’s law) that each year contains the same amount of people, then the number of people per year equals
\begin{equation*} \frac{A}{80}\sum_{k=0}^{79} (1.01)^k = \frac{A}{80} \frac{(1.01)^{80}-1}{1.01-1} \approx 1.52 A. \end{equation*}However, after 80 years, only \(A\) people die, not \(1.52 A.\) Here, \(4000/1.52\approx2630.\) This illustrates how applying the constant-population calculation to a growing population can overestimate the current death rate.
In conclusion, Little’s law must be applied with caution; during periods when the population increases or decreases on average, it does not hold.