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.