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

Advertisements

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? apurvnakade

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

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

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

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 Shreevatsa

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

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

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