1
$\begingroup$

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

enter image description here

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?

$\endgroup$
  • $\begingroup$ Am I correct that what you wrote boils down to "there is a theoretical result X, I wrote a code to check it, and according to simulations, the theoretical result is not true (code and simulations are presented)"? $\endgroup$ – user31264 Nov 6 '16 at 9:13
  • 2
    $\begingroup$ @user31264 The problem isn't the OP's simulation. The problem is that the OP's intuition is wrong that a greater likelihood of hitting a node sooner implies a greater likelihood of hitting the node last. To reach a node $X$ last, you need to reach a neighbor of $X$ then come entirely around the ring to reach $X$ from the other direction. At all times, this is equally likely for any node not on the boundary of the interval visited. And initially, it is equally likely for all nodes. These explanations are excellent: math.stackexchange.com/questions/116446/random-walk-on-n-cycle $\endgroup$ – Matthew Gunn Nov 6 '16 at 9:49
  • $\begingroup$ You say that my situation was discussed earlier here. But, that analysis does shifts focus away from the paradox I address. Thanks for pointing out that I have no code bugs. Now, it is time to realize that I do not have any false assumptions either. My code confirms all the assumptions and theoretical results and confirms the intuitive paradox I had. Just think about it: you hit A, the the left and right elements of the table sooner than reach B, the center of the table. However, getting later to A is as likely as later B. How is it possible? Why do not you see neither my question nor paradox? $\endgroup$ – Little Alien Nov 6 '16 at 11:50
  • $\begingroup$ @LittleAlien What's wrong with your intuition is that getting RIGHT next to a node doesn't increase the probability at all! If you're right next to it, there's a 50% probability you hit it and then it can NEVER be the last node. The only way the probability for a node $X_i$ goes up is that: (1) you happen to have gotten next to it and (2) you get lucky and move away. I advise reading the math.stackexchange.com link and going through those two answers very carefully. $\endgroup$ – Matthew Gunn Nov 6 '16 at 12:12
  • 1
    $\begingroup$ @LittleAlien if you're having problems with the moderation, please use the acceptable channels to resolve it (flagging behavior you think is wrong, bringing to meta the issue perhaps). Don't do it in the question itself, it's off-topic. Questions are meant to be concise and self-contained. $\endgroup$ – Firebug Dec 8 '16 at 11:13
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ We see that the nodes closer to the entrance have higher chances to be visited first, which reduces their chances to be last. You demonstrate that the probabilities of being last are increased as we elaborate the area around the entrance, which lifts the probabilities of the remaining nodes to be the last. The node, laying oppositely to the entrance must have the higher chances to be visited last. But, you say that probabilities come out equal. I do not get that. $\endgroup$ – Little Alien Nov 6 '16 at 13:12
  • $\begingroup$ You see, your central nodes have turned to 0 almost immediately. How can they have the same probability of being last visited as your extreme left and right nodes? $\endgroup$ – Little Alien Nov 6 '16 at 13:30
  • 2
    $\begingroup$ @LittleAlien "...which reduces their chances to be last." no! All I can say is go read Did's extremely explicit explanation. $\endgroup$ – Matthew Gunn Nov 6 '16 at 13:34
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.