Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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.
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.)
