Sunday, February 20, 2011

The Gamow-Stern Elevator Puzzle

"Obvious" is the most dangerous word in mathematics.

An amusing mathematical problem was devised by George Gamow and Marvin Stern, after they had been somewhat frustrated by the elevator service in their office building. Gamow's office was on the second floor and Stern's on the sixth floor of a seven-story building. Gamow noted that, whenever he wished to visit Stern, the first elevator to arrive at the second floor was almost always "going down" not up. It seemed as though new elevators were being created at the top floor and destroyed at the ground floor, since no elevator ever would bypass the second floor intentionally on its way up.

But when waiting for a descending elevator on the sixth floor, precisely the opposite effect was observed; the first elevator to pass was almost always "going up"!

To both Gamow and Stern it seemed almost as if there was a conspiracy to make them wait. In a world in which a conspiracy theory is put forth almost every day, in just about any imaginable setting, this is probably what many people would actually believe.

There is, however, a perfectly logical mathematical explanation for what Gamow and Stern observed.

The case of a building with just one elevator is easy to understand. We imagine that the elevator is continually running, going up and down all day long [2], and so it seems reasonable to assume that, if Gamow requested its service at some arbitrary time, then with probability 1/6 it would be below his floor and with probability 5/6 it would be above his floor.

Therefore, with probability 5/6 it would eventually arrive at his floor going down.

For Stern, it would be just the opposite, i.e., the elevator would, with probability 5/6, be going up when it arrived at his floor. This is what Gamow and Stern wrote and, so far so good, But then they blundered.

As Knuth wrote,

When there is more than one elevator, Gamow and Stern say that the "situation will, of course, remain the same." But this is not true! Many a mathematician has fallen into a similar trap, being misled by something which seems self-evident, and nearly every example of faulty reasoning that has been published is accompanied by the phrase "of course" or its equivalent.

Knuth then quickly demonstrates that if there are two independent elevators,
then the first elevator to arrive at Gamow's floor will be going down with probability 13/18, which is not equal to 5/6 = 15/18.

Knuth's calculation with a Monte Carlo simulation.

Also, what is the probability that the first-arriving elevator at Gamow's floor is going down in a three-elevator building?


[2]. As Knuth wrote, "Let us assume that we have an "ideal" elevator system, which everyone knows does not exist, but which makes it possible to give a reasonable analysis. We will assume that each elevator goes continually up and down from the bottom floor to the top floor of the building, and back again in a cyclic fashion (independent of the other elevators). At the moment we begin to wait for an elevator on some given floor of the building [floor 2 for Gamow], we may assume that each elevator in the system is at random point in its cycle, and that each will proceeed at the same rate of speed until one [first] reaches our floor.",+george+gamow&source=bl&ots=blGGS32cbB&sig=pxALIB7SbsmEaFM1e41_kJHwUJE&hl=en&ei=BadhTeGFJoTbgQfCzfjmAg&sa=X&oi=book_result&ct=result&resnum=9&ved=0CEYQ6AEwCDgK#v=onepage&q=puzzle%20math%2C%20george%20gamow&f=false

People who ride elevators are often puzzled by a strange probability.
If you have an office on a floor near the top.
The first elevator to stop is going up.
It happens a lot.

Suppose you work on a floor near the bottom.
Every day you eat lunch in a restaurant on the top floor.
Whenever you want an elevator, the first one to arrive is usually going down.

The elevator paradox first appeared in the book Puzzle-Math by the physicist George Gamow and his friend Marvin Stern. In explaining the paradox with one elevator, Gamow and Stern made a small mistake. They stated that the probabilities "of course remain the same" if there are two or more elevators.

Donald Knuth was the first to realize that this is not true. Writing on "The Gamow-Stern Elevator Problem" in the Journal of Recreational Mathematics (July 1969), Knuth showed that as the number of elevator increases, the probability that the first elevator to stop on any floor is going up approaches 1/2, and the probability it is going down also approaches 1/2.

This situation, in a way, is even more paradoxical than before.
It means that if you wait on a floor near the top and fix your attention
on any given elevator door, the probability is always high that the next time
elevator arrives it will be going up. But the chance that the next elevator
to stop on the floor will be going up, regardless of the shaft it is in,
is a different matter. This probability approaches 1/2 as the number of elevators
approaches infinity. The same is true of down elevators stopping on a floor near the bottom.

We assume, of course, that elevators travel independently of one another,
with constant speeds, and have the same average waiting time on each floor.
If there are just a few elevators, the changes in probability are slight,
but if there are 20 or more, the probability gets very close to 1/2 for all floors
except the top and bottom ones.


No comments:

Post a Comment