25
$\begingroup$

This is a problem about the meeting time of several independent random walks on the lattice $\mathbb{Z}^1$:

Suppose there is a thief at the origin 0 and $N$ policemen at the point 2.

The thief and the policemen began their random walks independently at the same time following the same rule: move left or right both with probability 1/2.

Let $\tau_N$ denote the first time that some policeman meets the thief.

It's not hard to prove $E\tau_1=\infty$.

so what is the smallest $N$ such that $E\tau_N<\infty$?

I was shown this problem on my undergraduate course on Markov chains, but my teacher did not tell me the solution. Does anyone know the solution or references to the problem?

  • 0
    You can probably consider a Markov chain on $\mathbb{Z}^{N+1}$ starting at $(0,2, ..., 2)$ and evolving under a probability transition kernel correctly chosen. Then you're looking at the entrance time to some subset. Just a few ideas, though, I don't know the answer.2012-08-29
  • 0
    Crossposted to MO: http://mathoverflow.net/questions/106133/random-walk-police-catching-the-thief2012-09-02

2 Answers 2