Let x_1, x_2, ..., x_n be n points (in that order) on the circumference of a circle. Dana starts at the point x_1 and walks to one of the two neighboring points with probability 1/2 for each. Dana continues to walk in this way, always moving from the present point to one of the two neighboring points with probability 1/2 for each. P_i is the probability that the point x_i is the last of the n points to be visited for the first time.
1. Show that P_i is the same for all i.
2. Find P_i
Suppose the points, are arranged clockwise as x_1, x_2, ..., x_n. To represent the points on a circle assume that as we go from left to right we are going in the clockwise direction. So, x_k, x_{k+1}, ..., x_N, x_1, ..., x_{k-1} for any k represents the arrangement of points on the circle.
ReplyDeleteNow to find P_k consider the random walk (with probability 1/2) on x_k, x_{k+1}, ..., x_N, x_1, ..., x_{k-1} . If Dana starts from x_1 she will either reach x_{k+1} before she reaches x_{k-1} or vice-versa. Let the probability that Dana reaches x_{k+1} earlier be p then the probability of reaching x_{k-1} first would be 1-p.
Now the probability for reaching x_{k-1} starting from x_{k+1} before it reaches x_{k} is the same as the probability of reaching x_{k+1} starting from x_{k-1} before it reaches x_{k} (bringing x_k to the right hand side). Both these probabilities would be the same as the probability of reaching x_N last starting from x_1 (denoted P_{1,n}). Hence we have :
P_k = p * P_{1,n} + (1-p) * P_{1,n} = P_{1,n}
and P_{1,n} can be computed easily using recurrence relations.