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 hours1 The sojourn time equals 100 km \(/\) 50 km/h = 2 hours. on the highway, there must be \(120\) cars2 2 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.3 Use the physical dimensions of the components of Little's law to check that \(\E{\J} \neq \lambda \E{\L}\).
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} \frac{1}{t}\int_{0}^{t}L(s)\d s\) exists, and \(\E \L = \lambda \E \J\).
Proof
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 Eq. (3.1.6). Taking the sum over this inequality and using the reasoning that led to Eq. (3.1.8) gives4 Observe 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\).
Claim: Little's law states for a rate-stable \(G/G/1\) queue that \(\E{\J}=\lambda\E{\L}\).
Solution
Solution, for real
False.
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
Solution, for real
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.
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
Solution, for real
True, Ex 4.4.6.
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
Solution, for real
False.
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
Solution, for real
False. Reducing \(\lambda\) also affects \(\rho\), which in turn affects \(\E\J\). While \(\E\L\) typically decreases, the relationship is not simply proportional because \(\E\J\) depends on \(\lambda\) through \(\rho\).
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
Solution, for real
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 system5 An application to actuarial sciences. , and ask how many people are born and die in the Netherlands per week.
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, the death rate in 2023 is about 2900 per week. 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
Solution, for real
Let us make a very simple model to clarify the problem. We start with an initial population size of \(A\). Then assume that each individual dies after exactly 80 years (and does not live a day longer). Moreover, assume that the population increases 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.01-1} = 1.5 A. \end{equation*}However, after 80 years, only \(A\) people die, not \(1.5 A\). Interestingly, \(4000/1.5 = 2700\), which is much closer to 2900 per week.
In conclusion, Little's law must be applied with caution; during periods when the population increases or decreases on average, it does not hold.