29
$\begingroup$

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?

$\endgroup$
10
  • 1
    $\begingroup$ 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...? $\endgroup$ Sep 2, 2012 at 0:47
  • 4
    $\begingroup$ @Joseph: The policemen move within {±2,0} with respect to this moving origin but not independently. $\endgroup$ Sep 2, 2012 at 1:16
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 2, 2012 at 1:18
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 2, 2012 at 13:48
  • 3
    $\begingroup$ 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). $\endgroup$ Sep 2, 2012 at 19:28

5 Answers 5

9
$\begingroup$

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)$:
         Thief19
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:
         Histogram100
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:
 N=3, 912 time steps

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ Sep 4, 2012 at 2:23
  • $\begingroup$ @Douglas: Do you mean $N$ in the same sense as in the original question? $\endgroup$
    – Will Sawin
    Sep 4, 2012 at 3:28
  • $\begingroup$ @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. $\endgroup$ Sep 4, 2012 at 4:01
  • $\begingroup$ @Doug: two policemen correspond to $\mathbb{R}^3,$ NOT $\mathbb{R}^2,$ so I am not sure why what you say is relevant. $\endgroup$
    – Igor Rivin
    Sep 4, 2012 at 4:03
  • 1
    $\begingroup$ Does this imply that $N=3$ is necessary and sufficient? What is known? I can't derive a coherent picture from these comments and other comments and answers. $\endgroup$
    – Will Sawin
    Sep 5, 2012 at 5:37
1
$\begingroup$

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$.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 3, 2012 at 2:59
  • $\begingroup$ @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. $\endgroup$
    – cardinal
    Sep 3, 2012 at 19:20
0
$\begingroup$

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."

$\endgroup$
1
  • $\begingroup$ Who is your teacher? You can email me if you don't want to post it. $\endgroup$
    – Igor Rivin
    Sep 4, 2012 at 18:01
-2
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – cardinal
    Sep 2, 2012 at 19:12
  • $\begingroup$ Yes, you are right... $\endgroup$ Sep 2, 2012 at 19:34
  • $\begingroup$ On the other hand, only the leftmost policeman matters. Is it possible to model only that one? $\endgroup$ Sep 2, 2012 at 19:51
  • $\begingroup$ 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. $\endgroup$
    – cardinal
    Sep 2, 2012 at 20:03
  • $\begingroup$ Also, the minimum of $N$ iid random variables does not have the distribution function you give; the maximum does. $\endgroup$
    – cardinal
    Sep 3, 2012 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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