Sunday, June 29, 2008

Random Walk Puzzles

Problem 1. Suppose we have a random walk on a semi-infinite graph with nodes x0, x1, x2, ... and so forth. For all i > 0, xi transitions to xi-1 with probability p and transitions to xi+1 with probability 1-p. The head node x0 is an absorbing state and transitions to itself with probability 1. For p < 1/2, compute the probability that a random walk starting at x1 ever reaches x0. For p > 1/2, compute the expected number of steps a random walk starting at x1 takes before reaching x0.

Problem 2. Suppose we have a random walk on a finite graph with nodes x0,...,xN. For i > 0, xi transitions to each xj, 0 <= j < i, with probability 1/i. The head node x0 is an absorbing state and transitions to itself with probability 1. For a random walk starting at xN, compute the expected number of steps before reaching x0.

3 comments:

John Carrino said...

So, I didn't want to look dumb, but no one has replied, so I'll give it a shot. The second one is intuitively Theta(lg(n)). It cuts the size in half each time. So what discrete sequence looks like log. Let try the harmonic series. Oh, it fits, woot.

The first question seems harder. I don't have the answer, but I am thinking along the lines of "count the number of paths of size 2n+1 and multiply by their probability. This seems like the ballot problem in terms of the paths counted, but each path is multipled by the probability, ((1-p)*p)^n.

if C_n is the nth Catalan number, I get

p*sum( (p*(1-p))^i * C_i, i, 0, infty)

I don't know what this reduces to and neither does my TI-89 and I don't have a copy of mathematica and it is 3am, so I give up.

I'll also have to postpone working on the 2nd half of the first problem for reasons stated above.

John Carrino said...

actually, i think the part 2 of 1 is the same counting, just add in the number of steps taken to get the expected value

p*(1+sum( 2i * (p*(1-p))^i * C_i, i, 0, infty))

Yisong said...

For the first question, I'm not sure how to simplify a formulation which uses Catalan numbers. You can exploit some other structure in the problem to arrive at a simpler formulation. This leads to a nice close-formed solution for both parts.

For the second question, the harmonic sum is correct, but I don't think you actually gave a proof.