Expected Elevator Stops with n+1 floors and k passengers

Question

There’s an elevator that accesses n+1 floors, with k people in it. It starts on the first floor. Every person independently wants to go to some specific randomly chosen floor (not the current one), and presses the corresponding button. How many stops do we expect the elevator to make?

I approached this problem by first looking at the base cases. When n = 1, we will expect only 1 stop regardless of k's value. When n = 2 and k = 1, we will only expect 1 stop again. When n = 2 and k = 2, there is a ½ probability that both passengers choose the same floor and a ½ probability the choose different floors. This means that the expected number of stops will then be 1.5 (0.5*2 + 0.5*1). When n = 2 and k = 3, there is a ¼ probability that all three choose the same floor and a ¾ that both floors are selected in some manner. This means there will be 1.75 expected stops.

I, however, am unsure how to extrapolate this idea to a general formula for any n and any k value.

Answer 1

The probability that one person is not getting off on floor number p is $(1-\frac1n)$ All $k $ people not getting off on the pth floor has probability $(1-\frac1n )^k $

$$ E[X_p] = 1-P(\text{ no one stops on the pth floor)} \\ =1-(1-\frac1n )^k $$ Which is independent of $p$ so the expected number of stops is given by $$ E\left [\sum_{p=2}^{n+1} X_p\right ]=n\left( 1-(1-\frac1n )^k\right) $$

Answer 2

Consider that the elevator reads the signal from each person and makes a new stop when the floor is different from the previous ones. The probability that the $i$th person presses a different floor from the previous ($i-1$) floors is $(1-\frac{1}{n})^{i-1}$

$E[N] = \sum_{i=1}^k (1-\frac{1}{n})^{i-1} = n \left(1 - (1-\frac{1}{n})^k\right)$