Question 2.53: Consider a particle that moves along a set of m + 1 nodes, l......
Consider a particle that moves along a set of m + 1 nodes, labeled 0, 1, … , m, that are arranged around a circle (see Figure 2.3). At each step the particle is equally likely to move one position in either the clockwise or counterclockwise direction. That is, if X_{n} is the position of the particle after its nth step then
P\{X_{n+1}=i+1|X_{n}=i\}=P\{X_{n+1}=i-1|X_{n}=i\}={\frac{1}{2}}where i + 1 ≡ 0 when i = m, and i − 1 ≡ m when i = 0. Suppose now that the particle starts at 0 and continues to move around according to the preceding rules until all the nodes 1, 2, … , m have been visited. What is the probability that node i, i = 1, … , m, is the last one visited?
Surprisingly enough, the probability that node i is the last node visited can be determined without any computations. To do so, consider the first time that the particle is at one of the two neighbors of node i, that is, the first time that the particle is at one of the nodes i−1 or i + 1 (with m + 1 ≡ 0). Suppose it is at node i−1 (the argument in the alternative situation is identical). Since neither node i nor i + 1 has yet been visited, it follows that i will be the last node visited if and only if i + 1 is visited before i. This is so because in order to visit i + 1 before i the particle will have to visit all the nodes on the counterclockwise path from i − 1 to i + 1 before it visits i. But the probability that a particle at node i −1 will visit i + 1 before i is just the probability that a particle will progress m−1 steps in a specified direction before progressing one step in the other direction. That is, it is equal to the probability that a gambler who starts with one unit, and wins one when a fair coin turns up heads and loses one when it turns up tails, will have his fortune go up by m − 1 before he goes broke. Hence, because the preceding implies that the probability that node i is the last node visited is the same for all i, and because these probabilities must sum to 1, we obtain
P{i is the last node visited} = 1/m, i = 1, … , m