Expected number with of rounds until n guests receive their correct keys through a random process

40 Views Asked by At

A hotel worker mixed up n keys for n rooms. The n guests show up together. The worker chooses a random permutation of the keys and gives each guest one key. If a guest receives his key, he leaves. The worker repeats the process with the remaining guests and remaining keys. How can I use the stopping theorem to calculate the expected number of rounds after which all guests receive their key. As a first step, define $X_i$ as the number of guests receiving their keys in the $i^{th}$ round. Show that:

$$E(X_i | X_1, X_2, ..., X_{i-1})=1$$