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.

About these ads

Written by S

Fri, 2008-07-25 at 01:54:50 +05:30

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?

    apurvnakade

    Sat, 2008-07-26 at 15:53:21 +05:30

  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.
    D’oh

    apurvnakade

    Sat, 2008-07-26 at 16:02:18 +05:30

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

  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

    Shreevatsa

    Sat, 2008-07-26 at 17:20:32 +05:30

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

    Shreevatsa

    Sat, 2008-07-26 at 17:58:47 +05:30


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 78 other followers