I have a question that is probably very well known, but I don't quite understand the proof (it is about showing that probability of ending up at a state say i assuming you have visited all the other nodes, so basically i is the last node you ended at when you traversing the circle).
Basically it is page 9 here: https://www.utsc.utoronto.ca/~sdamouras/courses/STA348H5_F11/Lecture%203%20Annotated.pdf
My question is I don't quite understand why P(node i visited last | node i-1 visited first before node i+1 visited first) is the same as P(node i visited last | node i+1 visited first before node i-1 visited first), i.e. the $\pi$ probability in the note notation here.
The reason I don't quite understand is because: say if we start at index 0, and say there are total of 1 million states, i.e. m = 1,000,000.
Say now i = 2 (i.e. the last node visited is 2), then I don't quite understand why P(node 2 visited last | node 1 visited first before node 3 visited first) is the same as P(node 2 visited last | node 3 visited first before node 1 visited first).
I thought that to visit node 3 ever for the first time before you visit node 1 for the first time is way more difficult (i.e. much smaller probability) then you visit node 1 ever for the first time before you visit node 3 for the first time IF YOU START from 0 like this question.
Isn't it true that to visit 1 if you start from 0, you have 1/2 probability? (assuming moving clockwise or counter-clockwise has equal probability at any position). But to visit 3 for the first time if you start from 0 before you visit 1 for the first time, isn't it much much less likely? before you have to have visited m=1000000, 999999, 999998, ...., 7, 6, 5,4 before you hit 3?
I'll give it another go, and try to be clearer.
Start at zero. Between the two of them, you will either hit 1 or 3 first. Split the sample space into these two options.
As you say, 1 is much more likely. Given that we've hit 1 before we hit 3, what is the probability that 2 is the last node we hit? Well, we haven't hit 2 or 3 yet. If we hit 2 before we hit 3 then we don't hit 2 last. If we hit 3 before 2 then we do hit 2 last, because we haven't hit it yet, and in getting back around to 3, we hit everything else, so 2 is the only thing left and we'll hit it eventually. So our conditional probability that 2 will come last is just the probability of us getting back around the circle to 3 without hitting 2 first. (Which coincidentally will be slightly smaller but close to the probability at the outset of hitting 3 before 1 when we start at 0.)
And what if we hit 3 before we hit 1? What is the probability that 2 is the last node we hit conditional on that? Well... we have to get all the way back around and hit 1 without hitting 2. It's the exact same situation as before in reverse. The probability is exactly the same.
Thus these two conditional probabilities are exactly the same, and they don't depend on $i$ at all. So by the logic explained in the slide, the probability distribution for which node will be last is uniform on $\{1,2,\ldots m\},$ which might be counterintuitive since you might think you have less of a chance of hitting nodes close to zero last since you start nearby them.
old answer
In both situations, node $i$ is visited last if and only if you make it all the way back around the circle to the unvisited node on the other side of $i$ without visiting $i$ in between. If you do so, you will automatically visit any remaining nodes along the way, so $i$ will be last. If you visit $i$ at any point before visiting the one on the other side, you will not visit $i$ last.
These two situations are perfectly symmetrical, so regardless of the relative likelihood of getting in one or the other states (and you're correct... in your example one is much more likely than the other), the conditional probability of visiting $i$ last is the same.