Consider an $n$ times $n$ grid. Assume there are two agents $A$ and $B$.

At time $t_0$, agent $A$ is at square $(n,n)$ and $B$ is at random square. At time $t+1$, agent $B$ has moved one square from his current position to an adjacent square, one left, right, above or below, provided he isn't at the edge. At the same time, $A$ can also move one square in similar fashion or stay put.

Assume that $A$ tries to find $B$, ie. be at time $t$ at the same square $B$ is.

What is the optimal way for $A$ to move?

To me, two strategies strategies come to mind. One is for $A$ to stay in the same square all the time, for the random walked will certainly intercept him at some point. Other would be for $A$ to go on a random walk too. (If this would be human "game", psychologically the second sounds more appealing)

  • $\begingroup$ Periodicity is a problem. Think of the grid as a chessboard, if A starts on a white square and B on a black square the two random walkers can never meet. Otherwise the random walk is a better strategy, especially as opposed to sitting in the corner $(n,n)$. This is just my intuition, I haven't done any calculations. $\endgroup$ – user940 Feb 17 '13 at 1:21
  • $\begingroup$ @ByronSchmuland Why in the case of a chessboard they could never meet? If one stays put and the other moves one, then he is on white and they are both in white. $\endgroup$ – Valtteri Feb 17 '13 at 1:42
  • $\begingroup$ No, I mean if they are both moving. $\endgroup$ – user940 Feb 17 '13 at 1:43
  • $\begingroup$ @ByronSchmuland Yeah, then the other will always be in white and the other in black. $\endgroup$ – Valtteri Feb 17 '13 at 1:45
  • $\begingroup$ A random walk on a chessboard doesn't visit every square equally often. So it might be, for instance, better for $A$ to walk to a center square and then sit there... this could be better than either of the strategies you listed. $\endgroup$ – mjqxxxx Feb 17 '13 at 4:30

Your Answer

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

Browse other questions tagged or ask your own question.