Little's law
|
|
In queueing theory, Little's result, theorem, or law says:
- The average number of customers in a stable system (over some time interval) is equal to their average arrival rate, multiplied by their average time in the system.
Although it looks intuitively reasonable, it's a quite remarkable result, as it implies that this behavior is entirely independent of any of the detailed probability distributions involved, and hence requires no assumptions about the schedule according to which customers arrive or are serviced, or whether they are served in the order in which they arrive.
It is also a comparatively recent result - it was first proved by John Little in 1961.
Handily his result applies to any system, and particularly, it applies to systems within systems. So in a bank, the queue might be one subsystem, and each of the tellers another subsystem, and Little's result could be applied to each one, as well as the whole thing. The only requirement is that the system is stable -- it can't be in some transition state such as just starting up or just shutting down.
| Contents |
Small example
Imagine a small shop with a single counter and an area for browsing, where only one person can be at the counter at a time, and no one leaves without buying something. So the system is roughly:
- Entrance → Browsing → Counter → Exit
This is a stable system, so the rate at which people enter the store is the rate at which they arrive at the counter and the rate at which they exit as well. We call this the arrival rate.
Little's Law tells us that the average number of customers in the store is the arrival rate times the average time that a customer spends in the store.
Assume customers arrive at the rate of 10 per hour and stay an average of .5 hour. This means we should find the average number of customers in the store at any time to be 5.
Now lets say the store is considering doing more advertising to raise the arrival rate to 20 per hour. The store must either be prepared to host an average of 10 occupants or must reduce the time each customer spends in the store to .25 hour. The store might achieve the latter by ringing up the bill faster or by walking up to customers who seem to be taking their time browsing and saying, "Can I help you?" in an annoying fashion.
We can apply Little's Law to systems within the shop. For example, the counter and its queue. Assume we notice that there are on average 2 customers in the queue and at the counter. We know the arrival rate is 10 per hour, so customers must be spending .2 hour on average checking out.
We can even apply Little's Law to the counter itself. The average number of people at the counter would be in the range (0,1) since no more than one person can be at the counter at a time. In that case, the average number of people at the counter is also known as the counter's utilisation.
Mathematical formalisation of Little's theorem
Let α(t) be the number of arrivals to some system in the interval [0, t]. Let β(t) be the number of departures from the same system in the interval [0, t]. Both α(t) and β(t) are integer valued increasing functions by their definition. Let Tt be the mean time spent in the system (during the interval [0, t]) for all the customers who were in the system during the interval [0, t] . Let Nt by the mean number of customers in the system over the duration of the interval [0, t].
If the following limits exist,
- <math>\lambda= \lim_{t \rightarrow \infty} \alpha(t)/t,\,<math>
- <math>\delta= \lim_{t \rightarrow \infty} \beta(t)/t,\,<math>
- <math>T = \lim_{t \rightarrow \infty} T_t,\, <math>
and, further, if λ = δ then Little's theorem holds, the limit
- <math>N = \lim_{t \rightarrow \infty} N_t,\, <math>
exists and is given by Little's theorem,
- <math>\, N= \lambda T.<math>
Use in performance testing of computer systems
Little's Law can be used in software performance testing to ensure that the observed performance results are not due to bottlenecks imposed by the testing apparatus. See http://www.onjava.com/pub/a/onjava/2005/01/19/j2ee-bottlenecks.html
References
- Little, J. D. C. "A Proof of the Queueing Formula L = λ W" Operations Research, 9, 383-387 (1961).