Can You Solve This Elevator Button Puzzle?

A FiveThirtyEight Riddler puzzle.

By Vamshi Jandhyala in mathematics Riddler

May 6, 2016

Problem

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?

Solution

Let $L = F_1 + F_2 + F_3 + \dots F_M$ be the random variable indicating the number of lit buttons where $F_i$ is the indicator random variable which is $1$ when at least $1$ person chooses floor $i$ and $0$ otherwise.

$\mathbb{P}[F_i=1] = 1 - (\frac{M-1}{M})^N$ where $(\frac{M-1}{M})^N$ is the probability of no one selecting floor $i$.

Therefore $\mathbb{E}[L] = \mathbb{E}[\sum_{i=1}^M F_i] = M(1 - (\frac{M-1}{M})^N)$.

Computational verification

from random import random, choice
from collections import Counter

n, m = 30, 20
runs = 10000
total_lit = 0
for _ in range(runs):
    choices = [choice(range(m)) for _ in range(n)]
    num_lit = sum([1 if c > 0 else 0 for l, c in Counter(choices).items()])
    total_lit += num_lit
print(total_lit/runs)