3

Steve’s Elevator Problem

3.1 THE PROBLEM

In my book Digital Dice (Princeton 2008), I included a puzzle question called “Steve’s elevator problem.” It was named for a reader in California, Steve Saiz, who had written to me about it after reading my book Duelling Idiots (Princeton 2002). As I wrote in Digital Dice, here’s how Steve explained it to me in a March 2004 e-mail:

Every day I ride up to the 15th floor in an elevator. This elevator only goes to floors G, 2 8, 9, 10, 11, 12, 13, 14, 15, 16, and 17. On average, I noticed that I usually make 2 or 3 stops when going from the ground floor, G, to 15, but it really depends on the number of riders in the elevator car. Is it possible to find the expected value for the number of stops the elevator makes during my ride up to the 15th floor, given the number of riders?

I was able, using combinatorial arguments, to derive expressions for the expected number of stops (in a building with n floors above floor G) if there are, initially on floor G, k riders in addition to Steve for the two cases of k = 1 and k = 2. Specifically, if k = 1, then the average number of stops is 2 − 1/n, and if k = 2, then the average number of stops is 3 − 7/n + 3/n². You can find these two derivations in Digital Dice on pp. 49–50 and pp. 124–125. In addition, another special case was solved, again using combinatorial arguments, by Michel Durinx at Leiden University in the Netherlands (for any value of k, assuming that n = 11), with the answer 9 − 8(10/11)^k. (The amusing story of how Michel got into this discussion is told on pp. 127–128 of Digital Dice.)

The status of the problem them remained unchanged until I received, in October 2008, an e-mail from Shane G. Henderson, a professor in the School of Operations Research and Information Engineering at Cornell University. Shane wrote to tell me he had found a complete, general, noncombinatorial analytical solution to Steve’s elevator problem!

3.2 THEORETICAL ANALYSIS

Shane’s analysis is beautiful in its amazing simplicity. Define X as a random variable whose value equals the number of stops for Steve as his elevator starts (with k other people) its ride up from floor G toward floors 1, 2, …, n − 2. In addition, let’s also define the n − 3 random variables I_i, 1 ≤ i ≤ n − 3, as follows:

(Mathematicians call random variables like this indicator functions, hence the I notation.) Then,

where the 1 is the certain stop at floor n − 2 (Steve’s floor) and the summation runs only up to floor n − 3 because Steve doesn’t care what happens above floor n − 2 (and the 1 has already accounted for the stop at floor n − 2). Taking expectations,

We can calculate E(I_i) as

E(I_i) = 0 × Prob(I_i = 0) + 1 × Prob(I_i = 1) = Prob(I_i = 1),

and so

So far this is all pretty straightforward. Now for Shane’s essential insight: the probability the elevator stops at any particular floor is the same as that for stopping at any other floor. If this was not so, then we’d be faced with the problem of explaining why not, that is, why would one floor (at the instant the elevator starts its run up the elevator shaft) be more or less likely to be a stop than some other floor? We have, in fact, no a priori reason to believe that is the case.

As the elevator approaches floor i, 1 ≤ i ≤ n − 3, there will be onboard a number of riders each of whom might get off on that floor (but not Steve, who will get off only at floor n − 2), a number that can range from zero (because all of Steve’s companions have already got off on lower floors) to k (because nobody has yet got off). So, in general, the calculation of the probability that the elevator stops at floor i involves a conditional probability analysis, that is,

This calculation is not horrible to do, but we can avoid it completely by simply noticing that, for the particular case of i = 1, we are guaranteed that all k + 1 original riders (Steve, plus his k initial companions) are still in the elevator (and so up to k people could get off) because nobody has yet had a chance to get off. This special case calculation is easy to do:

Prob(elevator stops at floor 1) = 1 − Prob(elevator does not stop at floor 1)= 1 − Prob(nobody gets off at floor 1).

We, of course, know Steve is not going to get off at floor 1. That much is certain, and so Prob(nobody gets off at floor 1) = Prob(none of the k additional riders gets off at floor 1), a probability that we can write by inspection simply by noticing that any particular one of these k riders gets off on floor 1 with probability 1/n and so does not get off on floor 1 with probability 1 − 1/n. Thus,

Prob(nobody gets off at floor 1) = (1 − 1/n)^k, and therefore Prob(elevator stops at floor 1) = 1 − (1 − 1/n)^k.

This immediately tells us that

and so, at last, we have Shane’s elegant result:

We can partially check this general formula against the three special cases I mentioned earlier.

Case 1: For n = 11 and all possible k (the original “Steve’s elevator problem”),

the result found, using fairly complicated combinatorial arguments, by Michel Durinx (see p. 127 in Digital Dice).

Case 2: For k = 1 and all possible n,

the result found, using simple combinatorial arguments, by me (see pp. 49–50 in Digital Dice).

Case 3: For k = 2 and all possible n,

the result found, using slightly more complicated combinatorial arguments, by me (see pp. 124–125 in Digital Dice).

Notice that Shane’s analysis is easily modified to handle the possibility that Steve’s office is moved to some other floor. A brute force combinatorial approach, on the other hand, would be far more disrupted by such a change.

3.3 COMPUTER SIMULATION

In Digital Dice I included a simulation code called steve.m on p. 126, and I’ll not repeat it here. (You can find it on Princeton University Press’s math website entry for the book.) That code was for the specific case of n = 11 (a value easily changed) and for any value of k.