Live data from Hacker News

Where to wait for an elevator (2010)

johndcook.com

101–110 of 115 posts

Re: Where to wait for an elevator (2010)

#101
post #78

The best real-world optimization: stand aside to make room for anyone exiting the elevator before crowding the doorway trying to walk in too quickly!

Great, you just made the problem more complicated. That's is because if there are people in the elevator and you right in front of it, you have to move away, wait, and go back. Not ideal, it makes more sense to wait on the side of the elevator, possibly at a distance proportional to the expected time it takes for the passengers to leave. That would make the ideal waiting spot somewhere between the middle elevator and…

Depends a bit on assumptions, but it's not quite what I expected, actually:

    import math
    import random

    B = 1000
    elevators = [-6, 0, 3]

    def time_to_enter_distribution(position):
        for _ in range(0, B):
            elevator = random.choice(elevators)
            distance = elevator - position
            # What matters is not how many people are in the elevator, but how
            # quickly they can evacuate. Approximate Poisson distribution.
            evac_time = [0, 1, 2, 3, 3, 4, 5][random.randint(0, 6)]

            # While you walk to the elevator, you give time for people to evacuate
            # and your time passes.
            evac_time -= abs(distance)
            time = abs(distance)

            # If people are still evacuating when you have arrived, you have to wait
            # for that to end by the side of the elevator, and then take the final
            # 0.5 metres to step inside.
            if evac_time > 0:
                time += evac_time + 0.5

            yield time

    def time_to_enter_summary(position):
        distr = list(time_to_enter_distribution(position))
        sum_time = sum(distr)
        sum_sq_time = sum(t**2 for t in distr)
        mean = sum_time/B
        sd = (sum_sq_time - sum_time**2/B)/(B-1)
        se = sd/math.sqrt(B)
        return (mean, se)

    if __name__ == '__main__':
        print(f'{"pos":5s}  {"t":4s} {"se":3s}')
        for p in (i/4 for i in range(-6*4, 3*4)):
            (t, se) = time_to_enter_summary(p)
            print(f'{p:5.2f}: {t:4.2f} ({se:3.2f})')

Re: Where to wait for an elevator (2010)

#102
post #100

Earlier quoted context omitted.

> But the nails have slightly different weights, so you need to pick some representative value. Question: Should you pick the mean or the median? Answer: You should pick the mean, because when you weigh all the nails together the differences will cancel out. Well, yes, that is the definition of the mean. But you can't know what the mean is without having already answered your original question of "how many nails are…

> But you can't know what the mean is without having already answered your original question of "how many nails are there?", so as a formal matter this is completely useless advice. Yes, obviously you'd estimate the mean/median by taking a small sample (or using a published value). I left that detail out because it's not relevant to the choice between mean and median.

I still don't really see the point of the observation. It's weird to say "You should pick the mean, because when you weigh all the nails together the differences will cancel out". That's true because the mean is defined as the value that achieves that result. It's like answering the Monty Hall problem by saying "you should pick the door with a car behind it, because that door has a car behind it".

You're asking what the mean weight of a bundle of nails is and then pointing out that the mean weight is a better estimate of the mean weight than the median weight is. Why is that worth noting?

Re: Where to wait for an elevator (2010)

#104
post #55

Is there any intuitive explanation for why the mean minimizes the squared error? I know it IS true - this property is used for linear regressions etc - but I couldn’t actually explain it. It seems like whatever minimizes a squared error should itself have some squares in it.

Suppose there are a bunch of points on a number line (elevators in the example) and you are standing somewhere between them. You decide to minimize the sum of squared differences by the greedy algorithm - make a small move either left or right, whichever makes it smaller, then re-evaluate and repeat.

First just consider one point, A. The squared distance from that point is a parabola with its apex at A, or as a formula (x - A)^2. The derivative of that is 2x - 2A. So if 2x - 2A > 0, moving to the right makes the squared distance go up, moving to the left makes it go down. If it's But you want to minimize the sum of the squared differences. So you are checking sum(2x - 2Ai) where Ai are all the different points. This means comparing 2nx with sum(2Ai), if n is the number of points. Or equivalently, you can divide by 2n and compare x with sum(Ai)/n. This formula is just the mean of the points. If this is greater than x, you should move a bit to the right. If it is smaller, you should move to the left. If equal, you have minimized the sum of squared differences.

We didn't prove uniqueness but we've established that the derivative of the sum of squared distances has only linear terms in it, so a little more calculus will easily allow us to check that.

tl;dr: To minimize a function requires an equation in that function's derivative. To minimize sum of squared errors we solve an equation with only linear terms.

Re: Where to wait for an elevator (2010)

#105
post #100

Earlier quoted context omitted.

> But you can't know what the mean is without having already answered your original question of "how many nails are there?", so as a formal matter this is completely useless advice. Yes, obviously you'd estimate the mean/median by taking a small sample (or using a published value). I left that detail out because it's not relevant to the choice between mean and median.

I still don't really see the point of the observation. It's weird to say "You should pick the mean, because when you weigh all the nails together the differences will cancel out". That's true because the mean is defined as the value that achieves that result. It's like answering the Monty Hall problem by saying "you should pick the door with a car behind it, because that door has a car behind it". You're asking what…

I was trying to come up with a scenario where you have to choose between the mean and the median, and the correct choice is the mean due to signedness (in contrast with the elevator example, where the correct choice is the median because the distance is unsigned). Do you have a better example?

It should be obvious that the mean is the correct representative value for weighing nails. My point is that there are cases that call for the mean and cases that call for the median, and the distinction can be explained by considering the signedness (without having to consider squared distances).

Maybe the following variation on the nail example would help: Suppose the manufacturer of the nails must publish a reference value for the weight of a nail, and will be fined for every nail that is not exactly the correct weight. The fine is proportional to the absolute error. Question: Should the manufacturer publish the mean or the median in order to minimise fines? Answer: The median.

Why is the mean the correct representative value for counting nails, but not for minimising fines? I'm arguing that it's because when the nails are weighed together the errors are signed, but when the fines are calculated the errors are unsigned (in the same way that the distances to the elevators are unsigned).

Re: Where to wait for an elevator (2010)

#108
post #107

Why is it not the first elevator in my direction? I’ll need to walk the same distance if it ends up being the third. If it is the first I saved walking to the median and back.

I thought the same thing - the way the problem is stated doesn't explicitly discount the distance walked before reaching any of the elevators, so logically the answer will depend on the configuration of the lobby and where you first enter it...or at least the position of the elevator call button. E.g. if the call button is to the left of all 3 elevators, it definitely makes sense to walk to the first of those, but any further is adding distance that will be doubled if that leftmost elevator is the first to arrive. I'm pretty sure even if the next two elevators are 100s of metres away, the mean distance walked from the moment you press the call button will go up if you start walking towards them, but haven't tried proving it.

Re: Where to wait for an elevator (2010)

#109
post #105

Earlier quoted context omitted.

I still don't really see the point of the observation. It's weird to say "You should pick the mean, because when you weigh all the nails together the differences will cancel out". That's true because the mean is defined as the value that achieves that result. It's like answering the Monty Hall problem by saying "you should pick the door with a car behind it, because that door has a car behind it". You're asking what…

I was trying to come up with a scenario where you have to choose between the mean and the median, and the correct choice is the mean due to signedness (in contrast with the elevator example, where the correct choice is the median because the distance is unsigned). Do you have a better example? It should be obvious that the mean is the correct representative value for weighing nails. My point is that there are cases t…

It is an interesting example, but after some thought it's basically identical to the elevator example. It is so similar that I have some doubts about whether I could correctly extrapolate a principle based on those two examples.

> Why is the mean the correct representative value for counting nails, but not for minimising fines? I'm arguing that it's because when the nails are weighed together the errors are signed, but when the fines are calculated the errors are unsigned (in the same way that the distances to the elevators are unsigned).

And here, there are two points that bother me.

First, the mean is the correct representative for counting nails because that's how it's defined. A mean is just the answer to any question of the form "if all of these data points were equal to each other, what is the value they would all share?". That's the question you're asking about the weight of the nails.

Second, I find it difficult to believe in your stated explanation of why you might choose the mean over the median (or vice versa), because we've already observed that the mean minimizes the sum of squared errors, and squared errors are all unsigned. You're relying on the assumption that, in the above example, the fine (which should be minimized) is directly proportional to difference from the estimate. But that assumption doesn't appear in the explanation of why one metric or the other will minimize the fine.

Re: Where to wait for an elevator (2010)

#110

"Since you can’t move without increasing the average distance, you must have started at the best spot." Technically this isn't a fully sound inference. All this proves is that you're at a local optimum. So you'd also need to know or show that there is only one optimum/the problem is convex/local=global or any variant. Of course that is the case here, but it's always worth noting the specific properties of a problem t…

> "Since you can’t move without increasing the average distance, you must have started at the best spot."

> Technically this isn't a fully sound inference. All this proves is that you're at a local optimum. So you'd also need to know or show that there is only one optimum/the problem is convex/local=global or any variant.

You can't move away from the median without increasing the average distance over all doors, when you're standing on the median.

But that's just a special case of the also-easy-to-prove fact that you can't move away from the median without increasing the average distance over all doors, no matter where you're standing. You can show that by exactly the same argument used in the post - if you move away from the median, your total distance to all doors will increase, because you moved away from more than half of the doors.

This suffices to show that -- if there is a global optimum superior to the local optimum at the median door -- that global optimum cannot be located in the neighborhood of any point on the real number line, which is to say it cannot be located at any finite distance from the median. Or in other words, no such global optimum can exist.

Post reply on HN