_{0}, x

_{1}, x

_{2}, ... and so forth. For all i > 0, x

_{i}transitions to x

_{i-1}with probability p and transitions to x

_{i+1}with probability 1-p. The head node x

_{0}is an absorbing state and transitions to itself with probability 1. For p < 1/2, compute the probability that a random walk starting at x

_{1}ever reaches x

_{0}. For p > 1/2, compute the expected number of steps a random walk starting at x

_{1}takes before reaching x

_{0}.

Problem 2. Suppose we have a random walk on a finite graph with nodes x

_{0},...,x

_{N}. For i > 0, x

_{i}transitions to each x

_{j}, 0 <= j < i, with probability 1/i. The head node x

_{0}is an absorbing state and transitions to itself with probability 1. For a random walk starting at x

_{N}, compute the expected number of steps before reaching x

_{0}.

## 4 comments:

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.

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

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.

Awesome! keep it up your work. you are providing precious information to users.

Post a Comment