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