Problem:
A country has $m+1$ cities $(m\in\mathbb{N})$, one os which is the capital. There is a direct railway connection between each city and the capital, but no tracks between any two 'non-capital' cities. A traveler starts in the capital and takes a train to a randomly chosen non-capital city (all cities are equally likely to be chosen), spends a night there and returns the next morning to the capital, and immediately boards the train to the next city according to the same rule.
Assume that her choice of city is independent of the cities visited in the past. Let $(X_n)_{n\geq 0}$ be the number of visited non-capital cities up to and including day, $n,$ so that $X_0 =1$.
Show that the transition probabilites $p_{k,k+1}=\frac{m-k}{m}$ and $p_{k,\ell}=0$ for $\ell \neq k+1$ and $k\neq m$
We just started on Markov Chains and i have read the theory a billion times and looked up similar questions related to mine, but without any luck. Hope somebody can give me some hints or/and explain how to attack a question like this.
Visited cities can be represented as a state of a discrete-time Markov chain which is given by $S = {1, 2, ..., m}$. If the traveler has visited $k$ cities, then they are in state $k$, and they will move to state $k+1$ when they visit a new city.
Transition probabilities:
$p_{k, k+1}$: When the traveler is in state $k$, they have visited $k$ non-capital cities. Since there are a total of m non-capital cities, there are $m-k$ cities left to visit. The probability of visiting a new city on the next trip is $\frac{m-k}{m}$, as each city is equally likely to be chosen. Therefore, $p_{k, k+1} = \frac{m-k}{m}$.
$p_{k, \ell}$: Since there are no direct connections between non-capital cities, the traveler can only visit a new city or return to a previously visited city through the capital. Given this structure, the traveler can only move to state $k+1$ from state $k$. Thus, $p_{k, \ell} = 0$ for $\ell \neq k+1$.
$p_{m, m}$: Once the traveler has visited all $m$ non-capital cities, they will always visit a previously visited city. Therefore, $p_{m, m} = 1$.
To summarize:
$$p_{k, k+1} = \frac{m-k}{m}, \quad p_{k, \ell} = 0 \text{ for } \ell \neq k+1, \quad \text{and} \quad p_{m, m} = 1$$