While waiting for tennis courts to open up the other day, I derived an interesting result:
If k tennis courts are occupied, each with a maximum play time of m hours, and you have been waiting for t hours, then the expected wait time until a court opens is
Look at t = 0 first, then deal with t by simply treating it as a reduction in the maximum wait time m. (If you have been waiting for t hours, then the maximum wait time is now m - t).
For k = 2, this can be visualized geometrically. Treat the x-y plane from 0 to 1, as the space of all possible pairs of wait times. A point (x, y) corresponds to a wait time of x on count #1, and y on court #2. We assume that wait times are uniformly distributed, so that all points (x, y) are equiprobable. Thus the probability of experiencing a wait time infentesimally near (x, y) is dxdy.
The expected value is the probability of experiencing a given wait time before a court opens, multiplied by the wait time itself. In this case, the wait time is min(x, y), or the minimum wait time for both courts (since only one court must open). So the calculation is:
We can evaluate this by noticing that min(x,y) = x over some region R. If we find the integral , we can multiply by 2 (corresponding to the case when min(x,y) = y), to find our original integral. Now we need to find R. In the 2D case, it can be visualized as follows (shaded region):
For a given x, the area of the region R (for which min(x, y) = x) is . So the integral we want is:
So for two courts, the expected time is 1/3 the maximum time.
The case with 3 courts leads to a useful generalization. This time, the integral is:
For some region R, min(x,y,z) = x. To find R, for a given x, plot out the feasible region:
The shaded portion of the y-z plane represents the region, for a given x, for which min(x,y,z) = x. Clearly the area of this region is So the integral we want is:
In general, for k courts, the integral will be:
(Last step through u-substitution u = 1-x).
This leads directly to the result. Scale up to the maximum time, and subtract the time you've already waited from the maximum to complete the solution.