Riddler

The Elevator Button Puzzle

A solution to this week's riddle by fivethirtyeight.com.

Here is this week’s ridde from fivethirtyeight.com:

In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people than floors, or more floors than people. Each person is equally likely to choose any floor, independently of one another. When a floor button is pushed, it will light up. What is the expected number of lit buttons when the elevator begins its ascent?

This is an expected value problem, and the obvious wrinkle is that multiple people may get off on the same floor. So, we can also think of this as a sort of sampling of floors with replacement. But before we determine the expected value, we can simulate this scenario for many buildings. Doing this for a thousand buildings should be more than enough. So for a thousand buildings, let’s randomly generate a number of $m$ floors and $n$ elevator riders. Each building has between one and a thousand floors (a very tall building!), and each elevator has between one and a thousand riders (a very big elevator!).

set.seed(405)
# generate random data
m<-sample(1:1000, 1000, replace = TRUE)
n<-sample(1:1000, 1000, replace = TRUE)
mn<-data.frame(cbind(m,n))
mn$sim<-0
for(i in 1:length(mn$m)){
  # count unique button press
  mn$sim[i]<-length(unique(sample(1:mn$m[i],mn$n[i],replace=TRUE)))/mn$m[i]
}
summary(mn)

##        m               n              sim          
##  Min.   :  1.0   Min.   :  1.0   Min.   :0.002395  
##  1st Qu.:245.0   1st Qu.:263.5   1st Qu.:0.408180  
##  Median :497.0   Median :486.5   Median :0.637261  
##  Mean   :490.6   Mean   :496.7   Mean   :0.615192  
##  3rd Qu.:720.5   3rd Qu.:741.0   3rd Qu.:0.867930  
##  Max.   :999.0   Max.   :999.0   Max.   :1.000000

On average, about 62% of buttons will be pressed. But, can we get the same result without simulating the problem? Some advice by Andre Nicolas gives us a good starting point.

For $i = 1$ to $M$, let a random variable $X_i = 1$ if $M_i$ is chosen at least once, i.e., if at least one rider presses the button for this floor, and let $X_i = 0$ otherwise.

For any single rider pressing a button, the probability of not choosing $M_i$ is equal to $\frac{M-1}{M}$. Therefore, for multiple riders, where each may or may not select a floor already selected by another rider, we get: $$Pr(M_i=1) = 1 - \left( \frac{M-1}{M} \right)^N$$

The number of floors selected, i.e., buttons pressed, is then the sum over all floors. Let’s call the total number of buttons pressed $Y$. $$Y = \sum_{i=1}^{M} M_i$$

So by the linearity of expectation we then get the expected value: $$E(Y) = \sum_{i=1}^{M} M_i = M \left(1 - \left( \frac{M-1}{M} \right)^N \right)$$

To get the percent of buttons pressed in expectation, we then just divide though by $M$. Let’s do this for the thousand buildings in our simulation and see if we get the same answer.

# calculate with expected value function
mn$math<-(1-((mn$m-1)/mn$m)^mn$n)
# some descriptives
mean(mn$math)

## [1] 0.614962

sd(mn$sim)

## [1] 0.2836344

cor(mn$math,mn$sim)

## [1] 0.9990653

Indeed, we get the same mean and standard deviation. There is also a nearly perfect correlation (showing we got the ‘right’ answer) between the simulated percent and the expected value percent. This can be easily seen in a plot of both.

# a plot
library(ggplot2)
ggplot(mn, aes(x=sim, y=math)) + geom_point(shape=1) + ggtitle("The Elevator Button Puzzle") +
xlab("Simulated Percent (mean in blue at 0.614)") + ylab("Expected Value Percent (mean in red at 0.615)") +   geom_hline(yintercept=mean(mn$math), color="red") + geom_vline(xintercept=mean(mn$sim), color="blue") 

Therefore, if you have a meeting at the top of a very tall building, and there are many other riders in your elevator with very random preferences about where to get off, be prepared for a rather long ride.

Dialogue & Discussion