Thursday, February 12, 2009

Random Walk Revisited

(revisited from the post Random Walk Puzzles)

Consider random walks on a graph with N+1 nodes (numbered 0,1,2...,N) where node j transitions to a lower numbered node i (0 <= i < j) with equal probability 1/j. Node 0 is an absorbing node, and there are no other transitions. We will consider only random walks that start at node N and end at node 0. Define X_j to be a binary random variable which indicates whether a random walk visits node j.

What independence properties can we state about X_0,...X,_N?

What is P(X_j = 1)?

No comments: