Why the queue is longer than you think
Tonight's idea
Customers arrive at one counter at random, \(\lambda\) per hour on average (the Poisson arrivals of b13). Service takes \(1/\mu\) hours on average, also memoryless. The utilisation \(\rho = \lambda/\mu\) is the fraction of time the server is busy. Below 1, you might expect a short queue. Not so.
Let \(P(n)\) be the long-run fraction of time \(n\) people are in the system (waiting or being served). Cut between states \(n\) and \(n+1\). The cut is crossed upward at rate \(\lambda P(n)\) (an arrival with \(n\) present) and downward at rate \(\mu P(n+1)\) (a service ending with \(n+1\) present). Each up-crossing is eventually matched by a down-crossing, so the rates match:
\[\lambda P(n) = \mu P(n+1), \qquad\text{so}\qquad P(n+1) = \rho\,P(n).\]
So \(P(n) = P(0)\rho^n\), a geometric sequence. The probabilities sum to 1 and \(\sum \rho^n = 1/(1-\rho)\), so \(P(0) = 1 - \rho\): idle a fraction \(1 - \rho\) of the time. The mean number present is
\(L = \displaystyle\sum_{n\ge0} n\,(1-\rho)\rho^n = \dfrac{\rho}{1-\rho}.\)
At \(\rho = 0.5\), \(L = 1\); at \(\rho = 0.9\), \(L = 9\). Randomness is the cause: arrivals bunch, and a nearly always busy server has no slack to clear a bunch. Real queues break the memoryless assumptions; the shape survives.
Watch one: 24 customers an hour, 2 minutes each
\(\lambda = 24\) per hour and \(\mu = 30\) per hour, so \(\rho = 0.8\). The server is idle \(P(0) = 0.2\) of the time, and \(L = 0.8/0.2 = 4\) people are present on average.
Little's law turns numbers into minutes: \(L = \lambda W\), where \(W\) is the mean time a customer spends in the system. (Those present now arrived in the last \(W\) hours, and there are \(\lambda W\) of them.) So \(W = 4/24\) hours, 10 minutes. Two are service, so the mean wait in the queue is 8 minutes: \(\rho/(1-\rho) = 4\) service times, at a counter idle a fifth of the day.
Your turn
- A server runs at \(\rho = 0.6\). Find \(P(0)\), \(P(1)\), \(P(2)\) and \(L\). Then find the mean number waiting (not being served), \(L_q = L - \rho\), and explain why that subtraction is right.
- Compare \(\rho = 0.5\) with \(\rho = 0.9\): give \(L\) and the mean queueing wait in service times for each. The 90% server wants to halve its \(L\). What \(\rho\) does it need, and by what factor must service speed up?
- Show that \(P(\text{more than } n \text{ in the system}) = \rho^{n+1}\). For \(\rho = 0.8\), what is the chance that more than 6 are present? How large must \(n\) be before that chance drops below 5%?
- (a) Differentiate \(\sum_{n \ge 0} \rho^n = \dfrac{1}{1-\rho}\) with respect to \(\rho\) to get \(\sum n \rho^{n-1}\), and deduce the formula for \(L\). (b) Both \(\lambda\) and \(\mu\) double: twice the customers, a server twice as fast. What happens to \(L\)? To \(W\)? Why?
Stretch: the average hides a lot
Find \(E[N^2] = \sum n^2 (1-\rho)\rho^n\) by differentiating the series a second time, and hence \(\mathrm{Var}(N) = E[N^2] - L^2\). At \(\rho = 0.9\), what is the standard deviation of the number present? What does that say about "the average queue is 9"?
Answers
- \(P(0) = 0.4\), \(P(1) = 0.24\), \(P(2) = 0.144\), \(L = 0.6/0.4 = 1.5\). \(L_q = 1.5 - 0.6 = 0.9\). The number being served is 1 when the server is busy and 0 otherwise, so its mean is \(\rho\); subtract it from the total to leave the queue.
- \(\rho = 0.5\): \(L = 1\), queueing wait 1 service time. \(\rho = 0.9\): \(L = 9\), wait 9 service times. Halving to \(L = 4.5\) needs \(\rho/(1-\rho) = 4.5\), so \(\rho = 4.5/5.5 = 0.818\): service only 10% faster (\(0.9/0.818 = 1.1\)) halves the queue. Near \(\rho = 1\) small improvements are worth a lot.
- \(P(N > n) = \sum_{m > n}(1-\rho)\rho^m = (1-\rho)\rho^{n+1}/(1-\rho) = \rho^{n+1}\). For \(\rho = 0.8\): \(0.8^7 = 0.21\), a one-in-five chance of more than six people. Need \(0.8^{n+1} \lt 0.05\): \(n + 1 > \ln 0.05 / \ln 0.8 = 13.4\), so \(n = 13\). The system exceeds 13 people 4.4% of the time.
- (a) \(\sum n\rho^{n-1} = \dfrac{1}{(1-\rho)^2}\). Multiply by \(\rho(1-\rho)\): \(L = \sum n(1-\rho)\rho^n = \dfrac{\rho(1-\rho)}{(1-\rho)^2} = \dfrac{\rho}{1-\rho}\). (b) \(\rho\) is unchanged, so \(L\) is unchanged: the same number of people are present. But \(W = L/\lambda\) halves, since the same crowd now flows through twice as fast. Big busy systems feel quicker than small busy ones at the same utilisation.
Stretch. Differentiating again, \(\sum n(n-1)\rho^{n-2} = \dfrac{2}{(1-\rho)^3}\), so \(E[N^2] = \dfrac{2\rho^2}{(1-\rho)^2} + \dfrac{\rho}{1-\rho} = \dfrac{\rho(1+\rho)}{(1-\rho)^2}\) and \(\mathrm{Var}(N) = \dfrac{\rho}{(1-\rho)^2}\). At \(\rho = 0.9\) the variance is 90 and the standard deviation about 9.5, as large as the mean. "Nine on average" means an empty counter one visit and twenty-five people the next; the queue is as erratic as it is long.