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?
apurvnakade
Sat, 2008-07-26 at 15:53:21 +05:30
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
apurvnakade
Sat, 2008-07-26 at 16:02:18 +05:30
I just remembered, Are random walks infinite?
I think i should take a break.
apurvnakade
Sat, 2008-07-26 at 16:06:41 +05:30
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
Shreevatsa
Sat, 2008-07-26 at 17:20:32 +05:30
BTW the problem you solved in the first comment is that of finding the stationary distribution of 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 :)
Shreevatsa
Sat, 2008-07-26 at 17:58:47 +05:30