Eccentric Elevator
Probability; Difficulty: easy
Escaping the Eccentric Elevator
I’ve adapted this probability puzzle from one that I came across some months ago.
Edit: This submission also made to the FiveThirtyEight Riddler Express for the week of May 6th, albeit with a slight modification by Riddler Zach.
You are on the 10th floor of a building, looking to exit on floor 0 (maybe 0 is parking level where your car is at, or maybe you’re in the UK where ground level is typically designated as level 0). You get in to the elevator and hit zero. But this elevator is malfunctioning in a specific way. When you hit zero, unknown to you, it registers the request to descend, but its messed up circuitry randomly selects some floor below the one you are on (including possibly zero). The car then stops at that floor. If this floor is not zero, you again hit 0 and the process is repeated till you get to your destination level .
Assuming no other passengers besides you (hence no other requests), how many floors on average will the car have stopped at (including the final stop at 0) when you exit at level 0? (i.e. the total expected no. of stops on your descent)
*spoiler alert* solution and answer follow in the sections below:
Solution
Let \(E_n\) be the expected number of stops to get to level 0 when starting at level \(n\).
Observe that if the first stop is below \(n-1\), then the expected number of stops would be the same as had you started on floor \(n-1\). So conditioning on the first stop being floor \(n-1\) vs. some level below \(n-1\):
\[
E_n \ = \ \frac{1}{n}(1 + E_{n-1})\ \ + \ \ \frac{n-1}{n}E_{n-1} \\
\]
The first term: ( \( \displaystyle \frac{1}{n}\) probability of landing on the level immediately below) times (the expected value being 1 stop + the expected stops from the level below)
The second term:( \( \displaystyle \frac{n-1}{n}\) probability of the next stop being below level \(n-1\) ) times (the expected value of starting at level \(n-1\) )
Simplifying:
\[
E_n \ = \ \frac{1}{n}\ \ + \ \ E_{n-1}
\]
This simply says that the difference between \(E_n\) and \(E_{n-1} \) is the probability that the first stop is \(n-1 \); else the two values would be the same! Now \(E_1 = 1\) (Starting at 1 the next stop has to be 0).
\[
\Rightarrow \ \ E_n \ = \ \sum_{k=1}^{n}\frac{1}{k}
\]
So \(E_n\) is just the \(n^{th}\) harmonic number.
Starting at the 10th floor the the expected number of stops is
\[
1 + \frac{1}{2} + \frac{1}{3} +…+ \frac{1}{10} = \mathbf {\color{Red}{2.93} }
\]
Reader Alex Zorn has a clever alternative solution in their comment below.
The harmonic series grows slowly (logarithmic growth). So even if you were to start at floor 100, you can expect to make 5.19 stops vs. 2.93 starting on floor 10. (See chart below).
2 thoughts on “Eccentric Elevator”
Fun alternate solution that doesn’t use induction:
Consider the floors [0,…,k], for some k < 10. At some point, we must visit one of these floors for the first time, call this floor X_k. If we have not yet reached a floor in [0,…,k], then each floor in that range is equally likely to be visited on the next press. It follows that X_k is uniformly distributed on [0,…,k]. Note that we only visit the kth floor at all if X_k = k, which by the previous reasoning has probability 1/(k+1).
Writing I_k to be the random variable which is 1 if we visit floor k and 0 otherwise:
[# of stops] = [# of floors visited] = Sum_k I_k
So
E(# of stops) = Sum_k E(I_k) = Sum_k 1/(k+1) = 1/1 + 1/2 + … + 1/10.
Love it! Thanks Alex. I’ve included a mention of this in the main write up. cheers!