3
$\begingroup$

Say there are $n$ different countries, the flight starts from some initial country. At each step, the flight can go to a random country other than the one where it currently is. The probability of going to other countries are equal. Let random variable $X$ be the number of steps until the flight has visited all the countries at least once. What is $\mathbb{E}[X]$?

I drew some examples and got $1/(n-1)^n$, but I don't know what to do next. I think it needs linearity of expectations.

$\endgroup$
2
$\begingroup$

This sounds like a homework problem, so I will only give a hint, rather than a full solution. Your problem is a slight variation on the coupon collector's problem, where the variation in your problem is that no two consecutive coupons (countries) can be the same. A simple way to solve this problem would be to look at the expected time in the standard coupon collector's problem (where the same coupon can occur consecutively), and then subtract the expected number of times that the consecutive coupons will occur. (Don't forget to also take account of the fact that you start in one of the countries, so you don't need to get a flight to that country.)

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.