If one person spends one minute waiting in a queue, we will say that one person-minute is wasted. In a bank queue, there are eight people, five of whom plan to perform simple operations taking 1 minute, while the rest plan to perform long operations taking 5 minutes. Find:

a) the minimum and maximum possible total number of wasted person-minutes;

b) the expected value of the number of wasted person-minutes, given that customers join the queue in a random order.
Let a short operation take $a$, and a long one - $b$ minutes $(a<b)$. A client planning a simple operation will be called a rusher, and one who intends to take a long time - a dawdler. Suppose there are $n$ rushers and $m = -2$ dawdlers.

Obviously, the number of wasted person-minutes depends on the order in which the rushers and dawdlers alternate.

a) Suppose somewhere in the queue, a rusher stands immediately behind a dawdler. We will swap their places. Then:

- Those standing in front of them neither gain nor lose anything;
- For those standing behind them, the waiting time remains the same;
- For the rusher, the waiting time decreases by $b$ minutes;
- For the dawdler, the waiting time increases by $a$ minutes.

Therefore, the total wasted time for everyone standing in the queue will decrease by $b-a$ minutes. We will continue to swap people in pairs "dawdler-rusher" until we get a queue where all rushers stand before all dawdlers. In this queue, the wasted time will be minimal.

Let's find the total wasted time. The second person waits for the first, the third waits for the previous two, and so on.

The total time spent waiting for all the rushers in front to finish their operations is

$(a+2a+\ldots+(n-1)a) + mna = \frac{1}{2}an(n-1) + mna$.

Here, the term $mna$ is the total time spent by all dawdlers waiting for all rushers.

The total time spent waiting for the dawdlers in front to finish their operations is $(b+2b+\ldots+(m-1)b) = \frac{1}{2}bm(m-1)$. The overall minimum waiting time for all clients is $T_{\min} = \frac{1}{2}an(n-1) + mna + \frac{1}{2}bm(m-1)$

In our specific case, we get: $1 \cdot 10 + 1 \cdot 3 \cdot 5 + 5 \cdot 3 = 40$.

Similarly, it can be shown that the maximum wasted time will be if all dawdlers stand before all rushers. This time is

$T_{\max} = \frac{1}{2}an(n-1) + mnb + \frac{1}{2}bm(m-1)$

With the numerical data from the problem, we get $1 \cdot 10 + 5 \cdot 3 \cdot 5 + 5 \cdot 3 = 100$.

b) Consider the $k$-th client in the queue. Let $X_{k}$ be the number of dawdlers standing in front of him. Then $X_{k} = I_{1} + I_{2} + \ldots + I_{k-1}$, where the indicator $I_{j}$ takes the value 1 if the $j$-th client is a dawdler and 0 if the $j$-th client is a rusher. The $j$-th client can be a dawdler with probability $\frac{m}{m+n}$ and a rusher with probability $\frac{n}{m+n}$. Therefore, $\mathrm{E}I_{j} = \frac{m}{m+n}$. Consequently, $\mathrm{E}X_{k} = \frac{(k-1)m}{m+n}$.

Let $T_{k}$ be the waiting time of the $k$-th client. We get: $T_{k} = X_{k}b + (k-1-X_{k})a = (b-a)X_{k} + a(k-1)$. Therefore, $\mathrm{E}T_{k} = (b-a)\mathrm{E}X_{k} + a(k-1) = (b-a) \cdot \frac{(k-1)m}{m+n} + a(k-1) = \frac{bm + an}{m+n} \cdot (k-1)$. Summing over all clients from the first to the $(m+n)$-th, we get the expected total wasted time: $\mathrm{E}T = \mathrm{E}(T_{1} + T_{2} + \ldots + T_{m+n}) = \frac{bm + an}{m+n} \cdot (0 + 1 + 2 + \ldots + (m+n-1)) = C_{m+n}^{2} \cdot \frac{bm + an}{m+n}$

Substituting the known values from the problem: $C_{m+n}^{2} \cdot \frac{bm + an}{m+n}$.

## Answer

a) 40 minutes and 100 minutes; b) 70 minutes.

Submit a comment