## A non-intuitive(?) fact

This seems counter-intuitive, at least to me, but if you can find an intuitive explanation for it, please comment!

Fact: Let G be a cycle (connected graph where every vertex has degree 2: you know what I mean) of length n (i.e., n vertices and n edges). Start a random walk on G from any node u. Then the probability that v is the last node visited (i.e., the random walk hits all other nodes before hitting v) is the **same for every v** other than u!

[Such a property is obviously true for the complete graph, and apparently it’s true only for cycles and complete graphs.]

I do not know a probabilist’s proof; what I could think of is a distinctly ComputerSciencey (Dynamic Programming / recurrence relation) proof.

Just trying :P

p(v)=(p(v-1) + p(v+1))/2

Since the v’s are cyclic the probabilities must all be equal

but then this gives that it is same for every v

including u:(What went wrong?

apurvnakadeSat, 2008-07-26 at 15:53:21

oops

i just read the problem again

v is the last node visited = the random walk hits all other nodes before hitting v

does this mean that the path (u,u+1,u) does not have u as its last visited node? The proof goes down if the answer is affirmative.

D’oh

apurvnakadeSat, 2008-07-26 at 16:02:18

I just remembered, Are random walks infinite?

I think i should take a break.

apurvnakadeSat, 2008-07-26 at 16:06:41

Hi Apurv :)

Random walk on graph: at each step, whatever vertex you’re at, move to each of its neighbours with equal probabilty.

For the purposes of this problem, a random walk is an infinite sequence

u_0 u_1 u_2 u_3…

such that

u_0 = u,

u_{i+1} = u_i + 1 (mod n) with probability ½ and u_i – 1 (mod n) with probability ½

The probability that we don’t hit all the vertices is 0. [That is, probability that not all vertices have been visited at least once by time n goes to zero as n → ∞]

v is the last vertex visited => the sequence contains every other vertex before it contains u.

(e.g. if vertices are {a,b,c,d} (cycle with 4 vertices), then in the sequence ababadabcaba…. the last vertex visited is c

ShreevatsaSat, 2008-07-26 at 17:20:32

BTW the problem you solved in the first comment is that of finding the

stationary distributionof the random walk: when the probabilities “settle down” (and you can prove they will), then each vertex will have equal probability. That is, if you do the random walk for long enough (about n log n steps on average, actually) then you’ll be at each vertex with equal probability :)ShreevatsaSat, 2008-07-26 at 17:58:47