Tuesday, March 31, 2009

Elevator Action

Dear Dr. Math,
How do I figure out whether to take the elevator or the stairs? The elevator is faster, when it comes, but sometimes I think I end up waiting longer than it would have taken me to just walk.
Regards,
StairMaster

Excellent question, SM, but we need to clarify what criteria we're using to decide between the two options. Some people might generally prefer the stairs because they enjoy the exercise, or maybe they're worried about the possibility of being stuck alone in a metal box for 41 hours. Some people like the elevator because it's more social, and you can do that thing where you jump at the very end and it feels like you're floating. But from the way you asked, I'm assuming you're just trying to minimize time, and that's all you care about. By the way, what's the big hurry? Take time to enjoy the little things, SM; they're all we have.

To actually answer the question, we need a model for all of the relevant quantities that we care about. To keep it general, I'll use variable names instead of hard numbers, and then we can take a look at some specific examples, and you can apply the theory to your own needs.

First, there's the stair option. Let's use S to denote the time it takes to walk. Since S doesn't really change much from trip to trip, we'll treat it as a constant. If you wanted to get more sophisticated, you could account for things like how many other people were trying to take the stairs, whether you were carrying something heavy, whether you could slide down the banister, etc.

The elevator option is the more interesting one. Let's let e be the shortest possible time the elevator could take, say, if it were already there waiting for you and didn't make any other stops. Similarly, there's a maximum time the elevator could take, if it was the greatest possible number of floors away from you and someone had pushed all the buttons, or something. Denote that time by E. (Upper case for the bigger time; lower case for the smaller one.) Again, we're treating e and E as known quantities and as constants; I encourage you to measure them sometime. If S < e, it's always faster to take the stairs, no matter what. If E < S, it's faster to take the elevator, even in the worst case. The remaining possibility is that e < S < E , so sometimes one is better, sometimes the other. It sounds like that's the situation with your elevator, SM, so we'll take it as a given.

Since we don't know the actual length of time the elevator would take, we have to treat it as a random quantity with a value somewhere between e and E. Let's call the actual time T. Here again, we need to consider what information we might have about T that could tell us what kind of probability distribution is reasonable to associate to it. For example, should we expect it to usually be closer to its minimum possible value, e? That would make sense if not many other people used that elevator and it usually hung out on the correct floor--say, if we were trying to go up from the ground floor to the 7th floor in an apartment building. On the other hand, if we were trying to go down from the top floor of a busy office building, it might be more reasonable to expect T to be closer to its maximum value, E, more of the time.

In the absence of any other information, we'll assume the distribution of T is uniform on the set of times between e and E, meaning it's just as likely to be any value as any other. Another way of saying this is to say that the probability that T is less than any given value, say x , is proportional to the difference between x and e. For x = e, the probability is 0, since e is the smallest possible time; for x = E, the greatest possible time, the probability is 1; for times in the middle, the probability is between 0 and 1. In pictures, the distribution looks like this (a = e, b = E):

As a result, the expected value, or average, of T is the number halfway in between its minimum and maximum possible values, that is, (e + E)/2. So, in the sense of minimizing expected values, you should take the stairs only if S < (e + E)/2; otherwise, you're better off waiting for the elevator, on average. As in my discussion of the lottery, though, the expected value may not be the only consideration. Since the time to take the stairs is a known quantity, it has a variance of 0, and that security may be worth some trade off in expected value. On the other hand, maybe you like to gamble, SM (I don't know you that well), in which case you might prefer the thrill of betting on the higher-risk, higher-reward elevator, even if the average time is slightly greater. Over many trials, though, you'd save time choosing the option with the smallest expected value.

Just to see how this would play out with actual numbers, I'll consider a scenario that I frequently encounter when taking the subway. (And you thought this was just about elevators!) Here, the role of "stairs" will be played by the #1 downtown local train, which makes frequent stops every few blocks, and the "elevator" corresponds to the #2 downtown express train, making stops only every few stations. Let's assume that I'm already on the local train at the 96th Street station, and I'm trying to get to Times Square as quickly as possible. My options are 1) stay on the local train, which will get to Times Square after some fixed amount of time, or 2) gamble on the express train, which might get there earlier or might not.

According to the schedule, it takes the local train about 10 minutes to get from 96th Street to Times Square. And the express train takes 6 minutes but only runs every 12 minutes (in the middle of the day). Therefore, the least possible time it could take is 6 minutes, and the greatest possible time is 18 minutes. Assuming the distribution of times to be uniform between these extremes gives us an average travel time of (6 + 18)/2 = 12 minutes, which is 2 minutes more than the local train. Hence, to minimize expected value, I should always stay on the #1. Here, the randomness of the travel time has more to do with how long I have to wait for the train than how long the trip will actually take, and it's somewhat reasonable to treat this as being uniformly distributed, since the train runs on a regular schedule (every 12 minutes) but I don't know what time it is currently relative to that schedule.

Of course, in practice the situation is more complicated than that. For example, there are actually two possible express trains I can take (the #2 or the #3), just as there might be two possible elevators you could take, and I'll take whichever comes first. If we treated these both as uniformly random variables, independent of each other, then the distribution of the time until the next train would not be uniform and would, in fact, have a smaller expected value.

For the numbers I gave above, it actually works out that the #2/#3 express option has the same expected value, 10 minutes, as the local train. So it's back to personal preference to break the tie. Another interesting variant is to consider how many people you see waiting for the train, elevator, bus, etc. and use that as a way to estimate the amount of time they've already been waiting. For example, if you see 3 people waiting and you know people tend to show up at the rate of 2 per minute, then you could estimate the time already waited at 1.5 minutes, reducing the maximum possible travel time by that same amount and perhaps tipping the balance.

Hope that helps some, and let me know whether the time you save turns out to be greater than the time spent thinking about the problem. I've got to go now to catch a (local) train.

-DrM

Anonymous said...

I think you shouldn't attempt to guess anything about the elevator unless you're familiar with it, which means you have some basic knowledge about the logic driving the elevator.
This means, if you know that e.g. pressed buttons inside have a certain preference over calls, than you're probably going to wait longer then just taking the stairs. (No I didn't make that up, I know at least one such elevator.)

The thing above assumes you have some additional »live knowledge« too: like on which floor the elevator is at the moment of call, ho long it would take the elevator to open and close the doors again (on average).
Also important: is there an override option for important people/transports (especially true if the elevator is located in an hospital or residence for seniors), and if so, how likely is it used (e.g. while doing my civil service I wouldn't have taken the elevator unless needed).

So I guess, this is just one of those problems where you should pick your preference (walking or riding) and stay with it, maybe figure in whether you need to go to the second or the ninth floor or if you have to transport something heavy. But else: just stick to your preference, because otherwise you're making a very uneducated guess (IMHO).

Greetings,
Drizzt

Short Round said...

Aw, man. Now I can't put this in my novel anymore. That'll teach me to talk to a famous internet personality.

drmath said...

Those are good points, Drizzt. I'd say they all fall under the category of information that could affect your estimation of the probability distribution of wait times, however. In my analysis, I was taking that distribution to be uniform in the absence of any more particular information. But yes, knowing things like how the elevator handles button presses (along with the number of other people using it, and how) could give you a different distribution.

There are actually algorithms for approaching this kind of problem that, while not optimal, don't depend on the distribution of wait times. For example, there's a way to solve the ski rental problem and be sure that you pay at most twice the optimal price.

-DrM

drmath said...

There's nothing new under the Sun, Short Round.