How can A and B have equal chances to be visited last if A has higher chances to be visited before B?

Question

The classical problem considered by Ross is a random particle visiting all chairs under a circular table. That is, there is a circular buffer of size m+1, were random walking particle is placed at position 0. It can go either left or right 50% and experiment terminates as soon as all chairs are visited. If you did not get it, here is the textbook formulation

Example 2.53: Consider a particle that moves along a set of m + 1 nodes, labeled 0, 1, ... , m, that are arranged around a circle. At each step the particle is equally likely to move one position in either the clockwise or counterclockwise direction. That is, if `Xn is the position of the particle after its nth step then

P{Xn+1 = i + 1|X_n = i} = P{Xn+1 = i − 1|Xn = i} = 1

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?

The answer is P{i is last} = 1/m, that is, equal for all the chairs since the reasoning is we get to i-1 and the chances that we get to i+1 sooner that to i are the same as if we first go to chair one and walk around the whole table sooner than step back to 0. There is something doubtful however. Start with a discrete random walk

You see, we sooner visit nodes around 0 before arrive at more distant places. Now, take a very wide range, say [-1000, 1000] and close it into a circle such that +1000 enters into a contact with -1000. Again, the number of steps needed to reach nodes +/-1000 is going to be very high, as I have proven in my simulation (previous edits of this post). How is it possible that the probability that nodes +/-1 are visited last is the same as that probability for nodes +/-1000 and why is whuber say that my simulation is wrong?

Answer 1

For a proof and clearer explanation than mine, visit https://math.stackexchange.com/questions/116446/random-walk-on-n-cycle

I'll give an example that may help build intuition.

Imagine you have a 7 node ring. I'm going to write it as a vector, but imagine it wraps around. Imagine you start at position 4. I'll use a * to denote your current position and the number in the vector to denote the probability a node will be the last visited node. It starts out as every node is equiprobable to be last.

$$x = \begin{bmatrix} \frac{1}{6} &\frac{1}{6} & \frac{1}{6} & 0^* & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \end{bmatrix}$$

50% of the time you'll move right first and the new vector will be: $$ x_R = \begin{bmatrix} \frac{1}{6} &\frac{1}{6} & \frac{2}{6} & 0 & 0^* & \frac{1}{6} & \frac{1}{6} \end{bmatrix}$$

Once you visit a node, it cannot be the last visited node anymore, and the probability of the node on the other end of the interval goes up by $\frac{1}{n-1}$.

50% of the time, you'll move left first and the new vector will be: $$ x_L = \begin{bmatrix} \frac{1}{6} &\frac{1}{6} & 0^* & 0 & \frac{2}{6} & \frac{1}{6} & \frac{1}{6} \end{bmatrix}$$

Notice how a node next to where you start initially has a $\frac{1}{6}$ probability and has a 50% shot of going to $0$ probability and a 50% chance of going to $\frac{2}{6}$.

If our first move is L and the second move is L $$ x_{LL} = \begin{bmatrix} \frac{1}{6} &0^* & 0 & 0 & \frac{3}{6} & \frac{1}{6} & \frac{1}{6} \end{bmatrix}$$ If our first move is L and the second move is R $$ x_{LR} = \begin{bmatrix} \frac{1}{6} & \frac{2}{6} & 0 & 0^* & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} \end{bmatrix}$$

If our first move is L and the second move is L and third move is R $$ x_{LLR} = \begin{bmatrix} \frac{2}{6} &0 & 0^* & 0 & \frac{2}{6} & \frac{1}{6} & \frac{1}{6} \end{bmatrix}$$ If our first move is L and the second move is L and third move is L $$ x_{LLL} = \begin{bmatrix} 0^* &0 & 0 & 0 & \frac{4}{6} & \frac{1}{6} & \frac{1}{6} \end{bmatrix}$$ Let $n$ be the number of nodes. Let $k$ be the number of nodes you have visited (not including your initial node). Each node starts out as $\frac{1}{n-1}$. As the interval you've visited expands, nodes off the boundary keep the same probability of being last but nodes on the boundary split the $\frac{k+1}{n-1}$ probability in a linear fashion depending on where in the interval you are.

Answer 2

The following simulation seems in line the theoretical result:

#!/usr/bin/env perl
use 5.024;
use warnings;

my $N = shift || 7;
my $rep = shift || 1_000_000;
my @last = (0) x ($N + 1);

for (1 .. $rep) {
   my $p = 0;
   my @visited = (0) x ($N + 1);
   $visited[$p] = 1;
   my $n_visited = 0;
   while ($n_visited < $N) {
      my $delta = int rand 2 ? 1 : $N;
      $p = ($p + $delta) % ($N + 1);
      ++$n_visited unless $visited[$p]++;
   }
   ++$last[$p];
}

say "$_: $last[$_]" for 1 .. $N;

Running it:

$ ./ncycle-walk.pl 
1: 142786
2: 142945
3: 142956
4: 143372
5: 143147
6: 142761
7: 142033

Regarding the intuition with $N+1$ nodes (the $+1$ being the starting node): if I start at node 0, it can take me 1 step to go to node 1 if I go "right", but it will take me $N$ steps to arrive it "from the left". So, depending on the head/tails balance and arrangement in the specific sample you get, you might be either very close to 1 or very, very far from it.

When you consider nodes labelled $-1000 \dots 1000$, node $1000$ is $1000$ steps away from the origin when arriving from the positive side, and $1001$ steps away when arriving from the negative side, and node $1$ is $1$ steps away when going positive and $2000$ steps away if your sample goes preferentially through the negative nodes first. In either case, you have to cover $2000$ nodes before landing on that as the last one.