The Lumber Room

"Consign them to dust and damp by way of preserving them"

A non-intuitive(?) fact

with 5 comments

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.

Written by S

Fri, 2008-07-25 at 01:54:50

5 Responses

Subscribe to comments with RSS.

  1. 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?


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

  2. 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.


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

  3. I just remembered, Are random walks infinite?
    I think i should take a break.


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

  4. 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


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

  5. 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 :)


    Sat, 2008-07-26 at 17:58:47

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: