26
$\begingroup$

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 the random walk on an $n$-cycle, $W$ is uniformly distributed over all vertices different from the starting vertex.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Henning Makholm Mar 4 '12 at 21:54
  • $\begingroup$ 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 :) $\endgroup$ – benny Mar 6 '12 at 5:33
  • 1
    $\begingroup$ 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.) $\endgroup$ – Did Mar 6 '12 at 6:07
  • 1
    $\begingroup$ 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. $\endgroup$ – joriki Mar 6 '12 at 11:27
  • $\begingroup$ @DidierPiau I am afraid you are right. I would like to emphasize that I am very grateful for you clear, detailed and precise answer. You helped me a lot! Thank you so much and sorry for my strange acceptation choice. $\endgroup$ – benny Mar 6 '12 at 18:25
12
$\begingroup$

In order to reach $W$ last, the walk has to visit one of $W$'s neighbours 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.

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 :-) $\endgroup$ – joriki Mar 5 '12 at 9:19
  • 2
    $\begingroup$ @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. $\endgroup$ – Did Mar 5 '12 at 17:56
  • 1
    $\begingroup$ 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 :-) $\endgroup$ – joriki Mar 6 '12 at 11:32
  • 1
    $\begingroup$ @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....) $\endgroup$ – Did Mar 6 '12 at 13:25
  • $\begingroup$ Is there a way to come up with recursive equations for this problem (the closed form of which gives the answer) ? $\endgroup$ – emmy Mar 2 '18 at 20:16
6
$\begingroup$

This question is rephrased as a game and can be analyzed with no computation!

A class of 30 children is playing a game where they all stand in a circle along with their teacher. The teacher is holding two things: a coin and a potato. The game progresses like this: The teacher tosses the coin. Whoever holds the potato passes it to the left if the coin comes up heads and to the right if the coin comes up tails. The game ends when every child except one has held the potato, and the one who hasn't is declared the winner.

How do a child's chances of winning change depending on where they are in the circle? In other words, what is each child's win probability?

From FiveThirtyEight Puzzle Column

It is equivalent to show that all students have equal probability of winning. To this end, consider the students to the left and the right of the teacher. Call them the teacher's pets. Both teacher's pets have equal probability of winning by symmetry.

The teacher is blue, the teacher's pets are green, and the potato is a lumpy yellow cloud. Small white circles are the other students.

Diagram 1: The teacher is blue, the teacher's pets are green, and the potato is a lumpy yellow cloud. Small white circles are the other students.

Now consider any student who hasn't lost yet. We can show he has the same chance of winning as a teacher's pet. Call this student "Purple".

Purple is a student who hasn't lost yet.

Diagram 2: Purple is a student who hasn't lost yet.

With $100 \%$ certainty, the potato will arrive to Purple's left or to his right eventually. Consider the first time this happens.

The potato touches one of his neighbors for the first time. Red players have lost already.
Diagram 3: The potato touches one of his neighbors for the first time. Red players have lost already.

In that situation, he use the power of imagination! He can image that he himself is a teacher's pet since his situation has become identical to the starting condition, and therefore his probability of winning is the same as that of the teacher's pets.

Purple imagines that he is a teacher's pet.
Diagram 4: Purple imagines that he is a teacher's pet. The arrow should be understood to mean "imagines himself as".

$\endgroup$
  • $\begingroup$ This is an excellent intuitive solution! I think it would get more (deserved) attention if the key step was explained better: you're really using a coupling between two copies of the process, one started from the teacher and the other started next to purple. $\endgroup$ – J Richey Feb 15 at 10:39
  • $\begingroup$ Thank you! I'll make an attempt to incorporate your suggestion. There really should be a way to depict it that requires no text at all. $\endgroup$ – Mark Feb 15 at 13:58
  • $\begingroup$ @JRichey I am not completely clear how to use the language of coupling to express the result. Maybe you can submit an answer? $\endgroup$ – Mark Feb 23 at 23:30
  • 1
    $\begingroup$ Wow. This is amazing! $\endgroup$ – Daniel Li Aug 20 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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