So the problem is: Consider the numbers {$1,2... 25$} written around on a circle, one after the another (so that, in particular, $1$ is adjacent to $2$ and $25$). Consider a Markov chain (Xn)n0 that, at each time, jumps with equal probability to one of the two adjacent numbers.
(a) What is the expected number of steps that Xn will take to return to its starting position?
(b) What is the probability that $X_n$ will visit all the other states before returning to its starting position?
a is quite simple, the stationary dist is $1/25$ for symmetric markov chain. So expected number of steps is 25.
but (b), the answer says:
Well I understand how it converts to a random walk with absorbing states of $1$ and $25$, but in the equation, why the probability of $(V_{25}<V_1)=(2-1)/(25-1)$? I know $(V_{25}<V_1)$ means reaching $25$ before reaching 1 with consideration of the initial state space, but I can't figure out why is (2-1)/(25-1). I know the fomula of $((p/q)^x-1)/((p/q)^n-1)$, does it have anything to do with this problem, since I don't know the $p$ and $q$ I guess?
One way of getting the result is to say that, after the move to state $2$ and the cut, each further step either changes the state by $+1$ with probability $\frac12$ or by $-1$ with probability $\frac12$, so the expected value of the state remains $2$ from this point forward.
Since you have absorbing states one of these events must happen $$\mathbb{P}_2(V_{25} \gt V_1) + \mathbb{P}_2(V_{25} \lt V_1) = 1$$ and to keep the expectation a constant $2$ you have $$1\times \mathbb{P}_2(V_{25} \gt V_1) +25 \times \mathbb{P}_2(V_{25} \lt V_1) = 2$$ and so by substitution $$1\times (1-\mathbb{P}_2(V_{25} \lt V_1)) +25 \times \mathbb{P}_2(V_{25} \lt V_1) = 2$$ which implies $$(25-1)\times \mathbb{P}_2(V_{25} \lt V_1) = 2-1$$