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? 
 A: 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:
 
A: 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.
A: 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$.
A: 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."
A: 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.
