A country has m+1 cities (m ∈ N), one of which is the capital. There is a direct railway connection between each city and the capital, but there are no tracks between any two "non-capital" cities. A traveler starts in the capital and takes a train to a randomly chosen noncapital city (all cities are equally likely to be chosen), spends a night there and returns the next morning and immediately boards the train to the next city according to the same rule, spends the night there, . . . , etc. We assume that his choice of the city is independent of the cities visited in the past. Let {Xn}n∈N0 be the number of visited non-capital cities up to (and including) day n, so that X0 = 1, but X1 could be either 1 or 2, etc.
Explain why {Xn}n∈N0 is a Markov chain on the appropriate state space S and the find the transition probabilities of {Xn}n∈N0, i.e., write an expression for
P[Xn+1 = j|Xn = i], for i,j ∈ S.
Find recurrent and transient classes and periods of all states. Sketch the transition graphfor m = 3.
Let τm be the first time the traveler has visited all m non-capital cities, i.e.
τm = min{n ∈ N0 : Xn = m}.
What is the distribution of τm, for m = 1 and m = 2.
Compute E[τm] for general m ∈ N. (Note: you don't need to use any heavy machinery. In particular, no knowledge of the "absorption and reward" techniques are necessary.)