I recently came across this article which talks about minimizing the expected walking distance when standing in front of a set of elevators. The point of the post is moreso to dwell on the effect different optimization techniques than to describe the specific solution that minimizes distance.

The article correctly gives the solution as the median of the points, along with an intuitive description of why this is the case. But I found myself wanting to write out a simple and general solution.

Let the positions of the elevators be $d_1, d_2, ... d_n$. If we stand at a position $x$, then our distance to elevator $i$ is $|x-d_i|$. We want to find $x_0$ that minimizes: $$ \sum_i^n |x - d_i| $$ The classical way of finding a maximum or minimum applies in setting the derivative of the quantity to zero: $$ \frac{d}{dx} \sum_i^n |x - d_i| = 0 $$ So what does each term of the sum contribute here? It depends on whether $d_i$ is greater or less than $x$ $$ \frac{d}{dx} |x - d_i| = 1 \quad \text{if} \: x > d_i $$ $$ \frac{d}{dx} |x - d_i| = -1 \quad \text{if} \: x < d_i $$ When $ x = d_i $, the derivative is undefined. So now lets define $l$ as the number of elevators to the left of $x$, and $r$ as the number to the right. We can see that: $$ \frac{d}{dx} \sum_i^n |x - d_i| = l - r $$

And so we will have minimized distance whenever $ l - r = 0 $. For an odd number of elevators, this will always correspond to the median, and we'll end up standing in front of an elevator (which in our calculation puts it neither to the left or right, and allows an odd number of elevators to balance out) . For an even number of elevators - this actually doesn't give us a singular point, but instead a range of possible minimizers. This will be between the two "innermost" elevators. The traditional median would have some sort of tiebreaker, usually the arithmetic mean in order to define a single value. But for our use case here, we can freely pace in the area where $l - r = 0$ without a care in the world, knowing our expected distance will stay minimal.

In fact, there is an edge case - we can technically stand right in front of these two innermost elevators, as long as we don't go a centimenter more outside of our range. This didn't show up freely in my analysis of the problem and I gave up trying to make it appear. Absolute values do funny things, and I don't think you can expect cleanly get out all cases from functions that don't permit continuous derivatives. This isn't meant to be too rigorous, so I've skipped some steps and been loose here and there.

The paper linked in the blog post at the top seems to lament that teaching this property of the median through calculus is not very instructive, but I would disagree. I think that without trying to be formal, some simple derivatives allow some rigor to the good intuitive explanation of "every step to the right increases the distance of all elevators to the left and vice versa".

In speculating on optimization techniques in the first article, now that we have found cases that give a range of possible minimizers for expected distance we could ask where we want to stand in those cases! We could apply minimization of the maximum distance or minimization of squared distances - subject to minimized distances. Optimization techniques on top of optimization techniques!