Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For a graph G, let W be the (random) vertex occupied at the first time the random walk has visited every vertex. That is, W is the last new vertex to be visited by the random walk. Prove the following remarkable fact: for random walk on an n-cycle, W is uniformly distributed over all vertices different from the starting vertex.

I would really appreciate if you could help me!

share|improve this question
1  
A good start would be to reformulate the claim to be about an ordinary random walk on $\mathbb Z$. The claim is then that at the first time $n-1$ different nodes have been visited, the number $u$ of visited nodes to the right of the starting point is uniformly distributed between $0$ and $n-2$. In this form it looks like it should be amenable to an induction proof, if you strengthen it to say something about the probability that the rightmost node (and not the leftmost one) was the last one visited, as a function of $n$ and $u$. –  Henning Makholm Mar 4 '12 at 21:54
1  
I'm curious to know why you changed the accepted answer. –  joriki Mar 5 '12 at 23:53
    
I wish I could accept two answers. I am very grateful to both of you and I wanted to express my gratitude by accepting both answers. And Didier Piau's answer made me realize that your elegant solution requires a notable amount of mathematical maturity, that I may lack. On the other hand, your soultion is elegant indeed. You made me think, I think I change the accepted answer again :) –  benny Mar 6 '12 at 5:33
1  
In other words, you accept a solution because (people tell you) it is elegant although you do not understand how it works nor why it is true. O well. (To be clear: PLEASE do not change again.) –  Did Mar 6 '12 at 6:07
1  
Note that while you automatically get notified of comments under your post, others that you respond to (me in this case) don't get notified unless you ping them using the @username idiom. –  joriki Mar 6 '12 at 11:27

2 Answers 2

up vote 3 down vote accepted

In order to reach $W$ last, the walk has to visit one of $W$'s neigbours for the last time and then go all around the cycle to arrive at $W$ from the other side. Let's call a segment of a random walk on the cycle that starts at some vertex $V$ and reaches one of $V$'s neighbours by going around the cycle without returning to $V$ a final segment. Then the last vertex reached after time $t$ is the final vertex of the first final segment that begins at or after $t$. Consider a random walk on the cycle, and for every final segment that ends at $W$, consider the stretch of times $t$ for which it is the first final segment that begins at or after $t$. If we can show that all vertices except $W$ occur with the same frequency in this stretch, then it will follow that conversely $W$ is reached last with the same probability from all other vertices, and thus all vertices $W$ are reached last with the same probability from a given initial vertex.

But the stretch extends precisely up to the last visit to $W$ before the segment, so the frequency of vertices in it is just that between any two successive visits to $W$, which is just the frequency of occurrence of the vertices other than $W$ in the walk in general, which is the same for all vertices.

P.S.: It's actually not too difficult to determine the probability of each vertex to be the last vertex visited at any stage in the process. The vertices already visited always form an interval. If the current position is at the end of an interval of $k$ visited vertices, every unvisited vertex has the same $1/(n-1)$ probability of becoming the last one, except the first unvisited vertex at the other end of the interval, which has $k/(n-1)$. This is because for all vertices except this one, exactly the same realizations of the walk will make them the last vertex as would be the case if no vertices had been visited yet. Thus, every vertex has a constant probability $1/(n-1)$ of ending up as the last vertex until the walk first visits one of its neighbours.

If the current position is in the interior of the interval of visited vertices, the probability of reaching one end of the interval before the other varies linearly over the interval, and thus so do the probabilities of the two unvisited vertices bordering the interval to become the last vertex – the sum of their probabilities is $(k+1)/(n-1)$, and this shifts by $1/(n-1)$ by each move, in favour of the vertex that the move moves away from.

share|improve this answer

Consider a simple symmetric random walk on the integer line starting from $0$ and, for some integers $-a\leqslant 0\leqslant b$ such that $(a,b)\ne(0,0)$, the event that the walk visits every vertex in $[-a,b]$ before visiting vertex $-a-1$ or vertex $b+1$. This is the disjoint union of two events:

  • Event 1: Starting from $0$, the walk visits $b$ before visiting $-a$, then, starting from $b$, it visits $-a$ before visiting $b+1$,
  • Event 2: Starting from $0$, the walk visits $-a$ before hitting $b$, then, starting from $-a$, it visits $b$ before hitting $-a-1$.

Recall that the probability that a simple symmetric random walk starting from $i$ visits $i-j\leqslant i$ before visiting $i+k\geqslant i$ is $\frac{k}{k+j}$, for every nonnegative integers $j$ and $k$.

Hence, the probability of Event 1 is $\frac{a}{a+b}\cdot\frac1{a+b+1}$, the probability of Event 2 is $\frac{b}{a+b}\cdot\frac1{a+b+1}$, and the probability of their union is $\frac1{a+b+1}$. Note that this last formula is also valid when $a=b=0$.

If $b=x-1$ and $a=n-x-1$ with $1\leqslant x\leqslant n-1$ and $n\geqslant2$, then $a+b+1=n-1$ hence the computation above shows that the probability that the last visited vertex in the discrete circle $\{0,1,\ldots,n-1\}$ is $x$ is $\frac1{a+b+1}=\frac1{n-1}$. That is, the probability of the event $[W=x]$ is $\frac1{n-1}$ for each $x\ne0$ in the circle, and $W$ is uniformly distributed on the circle minus the starting point of the random walk.

share|improve this answer
1  
Usually it tends to be you who finds the more elegant solutions that explain the unexpectedly simple result without undue calculation; this time it's the other way around :-) –  joriki Mar 5 '12 at 9:19
1  
@joriki: Yes. But I know as an experimental fact that a rigorous justification of each step of the elegant solution requires a notable amount of mathematical maturity. –  Did Mar 5 '12 at 17:56
1  
Didier, I hope my comment in connection with my curiosity about the change of the accepted answer and the subsequent re-change didn't create a "competitive" impression -- I was just pleased to find a solution involving less calculation than yours because it's more often the other way around :-) By the way, I still owe you an answer to an earlier comment -- yes, I do stay up during the night a lot, but I'm trying to cut down on that :-) –  joriki Mar 6 '12 at 11:32
1  
@joriki: You certainly do not have to worry about this (and your answer is excellent, naturally). You already know this but let me say it nevertheless: first, I am often puzzled by the acceptation choices on MSE; second, this puzzlement does not concern you as an answerer: you proposed a (mathematically sophisticated) solution, it got accepted hence it can only mean the OP is happy, everything is fine. (Unrelated: in my experience, staying up at night to do maths is a gambit which is difficult to refuse but is often lost, in the long run....) –  Did Mar 6 '12 at 13:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.