Simple random walk on cycle graph (Ending on specific vertex after cover time) I'm considering a simple random walk on a cycle graph comprising a number of vertices, labelled $1$ to $5$ consecutively. Suppose I start at vertex 1 and can traverse to either side ($2$ or $5$). I continue this random walk until I have covered all vertices. What is the probability that I finish on node $3$, and the expected number of steps to get there? How do I calculate the same quantities if I finish on the other vertices? How do I generalise to say $n$ vertices?
I have seen multiple resources discussing the cover time on a cycle graph, but in this context, I guess I have to include a discussion on either stopping time after visiting all vertices (which I don't really know how to include here, perhaps via a conditional probability) or transforming the end state as an absorbing state (which I guess won't make it a Markov chain anymore). I also suspect that for the first part (ending on node 3) we can exploit symmetry, but I'm not sure how. What should I do here? Thanks!
Edit: after simulating this, I've noticed that the probabilities of ending at any node is $1/4$. The expected number of steps terminating at $3$ (or $4$) should be $11$, and the expected number of steps terminating at $2$ (or $5$) should be $9$.
 A: I'd like to propose another approach, based on the graph being the $N$-cycle.
First, let's fix the notation making it more standard.
We assume that the vertices are $0,1,\dots,N-1$ and that the walker begins from $0$. The RW is symmetric, meaning the transition function is of the form $p(i,i+1 \mod N) = \frac 12 = 1-p(i,i-1 \mod N)$.
Theorem. The distribution of the last hit vertex is uniform on $\{1,\dots, N-1\}$.
Proof
Fix any vertex $j\in \{1,\dots,N-1\}$. Now consider the graph obtained by removing the state $j$. This is an "interval", a line graph with $N-1$ vertices,  $\{j+1 \mod N,\dots,-1 \mod N,0,1,\dots, j-1\}$
Let $\sigma$ be the time until the walk on the cycle,  starting from $0$ hits an endpoint of the interval, namely until the walk hits   $j-1$ or $j+1 \mod N$.
Now $j$ will be the last vertex to be hit by the walk if and only if after $\sigma$, the walk will hit the other endpoint before hitting $j$.
Since:

*

*the walk is symmetric;  and at time $\sigma$ is


*a. $N-2$ units from the other endpoint (remember that the interval has $N-1$ elements in it);


*b. $1$ unit from $j$, in the opposite direction.  the position of the  walk at time $\sigma$ is one unit away from $j$;
We conclude that the probability of $j$ being hit last is independent of $j$, and is the same as the probability of the walk starting from (say) $0$ to hit $N-2$ before hitting $N-1$ (much simple to draw) Since we have $N-1$ choices for $j$, the result follows. $\Box$
Expectation
I'll consider the expectation of the cover time conditioned on $j$ hit last. I  will only outline analysis leading to an answer. All calculations reduce to standard recurrence relations on the integers.
Let $\rho$ be the cover time. We are looking at its distribution conditioned on $j$ hit last. This is an independent sum of the following:

*

*$\sigma$: time to hit one of the endpoints of the interval above, starting from $0$.

*$\rho_1$: starting from that endpoint, time to hit the other endpoint, conditioned it happens before hitting $j$ (note: both endpoints are neighbors of $j$). Regardless of the choice of $j$, this has the same distribution the time  to hit $N-2$ before hitting $N-1$, starting from $0$.

*$\rho_2$: starting from an endpoint, time to hit $j$ (remember that both endpoints are neighbors of $j$).  This has the same distribution as time to hit $N-1$, starting from $0$.

Note that $\sigma+\rho_2$ has the same distribution as time $j$ is first hit starting from $0$ (start from zero, hit one of the endpoints, and then hit $j$), so effectively it is only two recurrence relations one needs to solve.
Also, only the distribution of $\sigma$ depends on $j$, the other two are the same for all $j$.
