Hitting time for two out of three random walk particles

Question

I'm imagining a simple random walk on $\mathbb{Z}$ with three independent particles (maybe add laziness so they don't jump over each other). Suppose the particles are initially placed at, say, $-10$, $0$ and $10$. The distance between any two particles evolves like a random walk, so the expected hitting time for those two specific particles is infinite. Now, if we require only that any two of the three particles hit, is the expected hitting time still infinite?

Answer 1

The answer is the same for random walks and for Brownian motion.

If you project a $3$-dimensional Brownian motion perpendicular to $x=y=z$, you get a $2$-dimensional Brownian motion. The projection of the set where $x\lt y\lt z$ is a wedge of angle $\frac{\pi}{3}$. Your question is whether the first exit time from a $\frac{\pi}{3}$ wedge has finite expected value. This question and more is answered in Spitzer (1958) Some theorems concerning $2$-dimensional Brownian motion. Trans. Amer. Math. Society 87 pp. 187-197.

In that paper, theorem $2$ on page $192$ is that in a wedge of angle $\beta$, the $\delta$ power of the first exit time has finite expected value iff $2\delta \beta \lt \pi$. In your case, $\frac{2 \pi}{3} \lt \pi$ so the expected value is finite.

I believe you can also check this by the reflection principle, since the probability that you remain in a wedge of angle $\frac{\pi}{3}$ is a finite alternating sum of $6$ densities, $3$ positive and $3$ negative. You should be able to estimate the value in terms of derivatives of the normal density. However, Spitzer's work is worth checking out.

Answer 2

Suppose the particles start at integers $x,y,z$ with $x \leq y \leq z$ and $x \equiv y \equiv z \bmod 2$ (so they can actually hit rather than pass through each other). Then if I did this right the expected hitting time $f(x,y,z)$ is given simply by $$ f(x,y,z) = (z-y) (y-x). $$ For example, for $(x,y,z) = (-10,0,10)$ the expected stopping time is exactly $100$. Here's some gp code that tries this $10^4$ times and sums the lengths of the resulting random walks:

{   
try(v0, v,n) =
  v = v0;
  n = 0;
  while((v[1]<v[2]) && (v[2]<v[3]), for(i=1,3, v[i]+=2*random(2)-1); n++);
  return(n)
}     
sum(t=1,10^4,try([-10,0,10]))

It should take a few seconds to compute a sum that's within a few percent of $10^6$.

Note that the function $f(x,y,z) = (z-y)(y-x)$ satisfies the necessary conditions of being zero for $x=y$ or $y=z$, positive for $x<y<z$, invariant under $(x,y,z) \mapsto (x+t,y+t,z+t)$, and equal to $1$ plus the average of the $8$ values $f(x \pm 1, y \pm 1, z \pm 1)$. But this does not quite determine $f$ uniquely, because $(z-y)(y-x) + c(z-x)(z-y)(y-x)$ also works for any $c>0$; so one must do some work to verify that $(z-y)(y-x)$ is the right function.

Answer 3

Expanding the comment above to a complete proof of Noam Elkies' formula:

Let $\tau$ be the first meeting time for independent simple random walks $X_t, Y_t$ and $Z_t$ started at the even points $x<y<z$. Write $f(x,y,z)= (z-y)(y-x)$. Claim: $ E(\tau)=f(x,y,z)$.

Proof: let $F_n=f(X_{\tau \wedge n},Y_{\tau \wedge n},Z_{\tau \wedge n})$ and $M_n:=F_n+{\tau \wedge n}$. It is easy to verify that $M_n$ is a Martingale so $f(x,y,z)=M_0=E(F_n+\tau\wedge n)$ for any $n$. Therefore $E(\tau) \le f(x,y,z)$. It remains to verify that $\lim_n E(F_n)=0$. Clearly $F_n \to 0$ a.s. so it suffices to verify that $\max_n F_n$ is integrable. For this we will use the linear martingale $L_n=(Z_n-X_n)/2$ and the quadratic martingale $Q_n=F_n+ 2 L_n^2$. The first is a lazy SRW on the integers. The AMGM inequality gives $4f(x,y,z)\le (z-x)^2$, so $E (\max_{n \le t} F_n) \le E(\max_{n \le t} L_n^2) \le 4 E(L_t^2)$ by Doob’s $L^2$ maximal inequality. But $4E(L_t^2) \le 2E(Q_t)=2Q_0$ for every $t$. We conclude that $ E (\max_n F_n) \le 2Q_0$.