# Random walk: police catching the thief

I posted this problem on stackexchange.com,but haven't get a satifactory answer.

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 that $E\tau_1=\infty$. so what is the smallest N such that $E\tau_N \lt\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?

-
I wonder if it would help to make a thief a moving origin, so the policemen move within $\lbrace \pm 2, 0 \rbrace$ rather than $\pm 1$, and then the question reduces to the time for some policemen to return to the origin...? – Joseph O'Rourke Sep 2 '12 at 0:47
@Joseph: The policemen move within {±2,0} with respect to this moving origin but not independently. – Anton Klyachko Sep 2 '12 at 1:16
This would leave the walks of the policemen related. Passing to Brownian motion shouldn't affect whether the expected stopping time is infinite, and on Brownian motions it is a little easier to apply a linear transformation to restore independence. The covariance of the changes is $t(I_N + J_N),$ and the question is how rapidly this leaves the positive orthant. – Douglas Zare Sep 2 '12 at 1:18
The natural guess is $2$ policeman; let me explain why. Let $p_n(k)$ be the probability that none of the $k$ policemen have caught the thief by time $n$. The expectation in question is $\sum p_n$. If the thief stood still and the police walked, then the walks are independent and $p_n(k) = p_n(1)^k$. Now, $p_n(1)$ dies off like $1/n$ (the ratio of the Catalan numbers to the binomial coefficients). So the sum converges when $k \geq 2$. This isn't a rigorous argument, because the walks aren't independent, but it still feels good. – David Speyer Sep 2 '12 at 13:48
David: when the thief is idle $p_n(1)$ is roughly $n^{-1/2}$, not $n^{-1}$, so the answer in that case is 3, not 2. If the thief is random walking, the answer should be at least 3, due to positive correlations between events, but it is not immediate (to me) what is the upper bound (it is clear the bound exists, though). – Ori Gurel-Gurevich Sep 2 '12 at 19:28

Not an answer, just an illustration for $N=2$ policemen, starting at $x=2$, with the thief starting at $x=0$. Time advances vertically. The thief (black) is caught (by the purple policeman) at $(x,t)=(-3,19)$:

The distribution of catching times is highly skewed, and so it is difficult to determine the mean-time-to-catch from simulations. Here is a histogram for 100 random trials:

In one of my runs (not included above), it took 24,619 time steps to catch the thief (at $x=-49$)!

Just to add an illustration for $N=3$, as per Ori G.-G.'s latest estimation, here is an example where the thief is captured at $(t,x)=(912,2)$. Again the thief is black (the lower curve), but now time increases to the right:

-

The best way to think of this question is as a "configuration space model". Namely, et $X_i$ be the position of the $i$-th walker (we can put $i=1$ for the thief). Now, the state of the system is described by the vector $(X_1, \dots, X_{k+1})$ where $k$ is the number of policemen, and the the system evolves by doing a simple random walk on $\mathbb{Z}^{k+1}.$ The walk stops when $X_1=X_{l},$ for some $l>1,$ and the starting position is $(0, 2, 2, \dots, 2).$ It is easy to see that this is equivalent to having the walk take place in a cone with absorbing boundary -- we are looking for the expectation of exit time to be finite. This, in generality, is not an easy question, but, luckily, quite studied. Unluckily, the papers are a little hard to read for a non-probabilist, but the relevant results seem to be those of Burkholder (￼Exit Times of Brownian Motion, Harmonic Majorization, and Hardy Spaces* D. L. BURKHOLDER, Advances in Math, 1977) and his student Terry McConnell (McConnell, Terry R.(1-CRNL) Exit times of N-dimensional random walks. Z. Wahrsch. Verw. Gebiete 67 (1984), no. 2, 213–233. ), which imply that two policemen suffice.

There are more recent papers, of which the most promising seems to be Denisov and Wachtel:

Random Walks in Cones

Denis Denisov, Vitali Wachtel (http://arxiv.org/abs/1110.1254), they prove sharper estimates on the moments, and also give a bit of a survey of where these sorts of results are used.

EDIT Thanks to @Douglas Zare's trenchant comment it should be noted that the above argument is off by one, because we have $k-1$ hyperplanes in $\mathbb{R}^k$ which do not describe a cone with a compact base, so the correct statement is that three or more policemen suffice.

-
For Brownian motion, it's harder for policemen to catch a thief who moves than a thief who stands still, and the expected time to catch a thief who moves with $N=2$ is infinite. Does that change with a random walk? – Douglas Zare Sep 4 '12 at 2:23
@Douglas: Do you mean $N$ in the same sense as in the original question? – Will Sawin Sep 4 '12 at 3:28
@will Sawin: Yes. I don't think $2$ policemen suffice. If I read the results correctly, there is an expected value for the first exit time of a Brownian motion from a cone in $R^2$ when the angle of the cone is smaller than $\pi/2,$ but the cone here is larger after the linear transformation to restore isotropy. – Douglas Zare Sep 4 '12 at 4:01
@Doug: two policemen correspond to $\mathbb{R}^3,$ NOT $\mathbb{R}^2,$ so I am not sure why what you say is relevant. – Igor Rivin Sep 4 '12 at 4:03
@Doug: Ah, yes, now I see what you mean. The point is that there are TWO hyperplanes in $\mathbb{R}^3,$ not three, so this corresponds to the two dimensional case. – Igor Rivin Sep 4 '12 at 4:10

For a single policeman, $E\tau_1$ is finite if he has a probability ($1/2+\epsilon$) of moving towards the thief.

If there is a second policeman, further away from the thief than the first, both back on $p=\frac{1}{2}$ then there is a non-zero probability that he will catch up with the first in a finite time (provided that this time is sufficient, of course). When they move from the same position, there is a higher probability that one of them will move towards the thief. So, very informally, can we say that a second policeman effectively increases the probability of one policeman moving towards the thief? This gives us an equivalent case to my first paragraph, with a finite $E\tau$.

Here is a vague justification for the single-policeman case with probability $p$ of moving towards thief. Actually, it helped me to start with $p=\frac{1}{2}$: for that case, define $E_n$ as the expected number of further steps if the current separation is $2n$.

$E_n = 1+\frac{1}{4}E_{n-1}+\frac{1}{2}E_{n}+\frac{1}{4}E_{n+1}$

Rearrange: $E_n = 2+\frac{1}{2}E_{n-1}+\frac{1}{2}E_{n+1}$

Apply this to both $E$'s on the RHS and rearrange: $E_n = 8+\frac{1}{2}E_{n-2}+\frac{1}{2}E_{n+2}$

This formula can then be applied to itself in a similar way, and so on:

$E_n = 32+\frac{1}{2}E_{n-4}+\frac{1}{2}E_{n+4} = 128+\frac{1}{2}E_{n-8}+\frac{1}{2}E_{n+8}$ $E_n = 2^{2k+1}+\frac{1}{2}E_{n-2^k}+\frac{1}{2}E_{n+2^k}$

All of these are valid so long as there are no negative subscripts. However, we can use $E_0=0$:

$E_2=8+\frac{1}{2}E_4=8+\frac{1}{2}(32+\frac{1}{2}E_8)=8+16+32+\dots$

which is infinite as expected. But if we follow the same steps with probability $p>0.5$, the behaviour is different:

$E'_n = C_1+p_1 E'_{n-2}+(1-p_1) E'_{n+2}$

where $C_1=4/[1-2p(1-p)]$ and, more importantly, $p_1=p^2/[1-2p(1-p)]\approx (\frac{1}{2}+2\epsilon)>p$, so subsequent steps are increasingly different. Quite soon:

$\{E'\}_n \approx D 2^k +\{E'\}_{n-2^k}$ and so $\{E'\}_{2^k} \approx D 2^k$.

-
No, the maximum doesn't move down with a fixed probability greater than 1/2. The expected value of the maximum of two random walks is still $O(\sqrt{n})$ not $\Omega(n).$ As Ori Gurel-Gurevich pointed out, if the thief doesn't move, then the expected time before $2$ policemen discover the thief is infinite, so for $N=2$ the behavior is known to be different from what your "very informal" argument says. – Douglas Zare Sep 3 '12 at 2:59
@Douglas: The discrepancy between the left-most policeman and the thief is a supermartingale (unless I've made a terribly embarrassing error) and, thus the stopped process is a nonnegative supermartingale. Hence, for any $N$ such that it is not uniformly integrable, we know the expected time of capture must be infinite. – cardinal Sep 3 '12 at 19:20

OK, I mailed my teacher today and he told me "as far as I know, this problem is still open,but for continuous Brown motion in 1D,the answer is N=4."

-
Who is your teacher? You can email me if you don't want to post it. – Igor Rivin Sep 4 '12 at 18:01

My attempt: If you can calculate the cdf of meeting times $F(x)$ of 1 thief -- 1 policeman, then the distribution of 2 policemen meeting times will be the minimum of the individual meeting times, which is $F(x)^2$. For N policemen, it will be $F(x)^N$. The question is then to choose the minimum N for that the expected value is defined.

-
This would be true if the meeting times were independent. But, they are not since it is the same thief that each policeman is attempting to catch. – cardinal Sep 2 '12 at 19:12
Yes, you are right... – Endre Varga Sep 2 '12 at 19:34
On the other hand, only the leftmost policeman matters. Is it possible to model only that one? – Endre Varga Sep 2 '12 at 19:51
The position of the thief is binomially distributed (up to an affine transformation) and the distribution of the left-most policeman is distributed as the minimum of $N$ such independent random variables. These two are independent and so you need to look at the probability that these two are equal (for the first time) at each step. – cardinal Sep 2 '12 at 20:03
Also, the minimum of $N$ iid random variables does not have the distribution function you give; the maximum does. – cardinal Sep 3 '12 at 4:11