3
$\begingroup$

Suppose $X,Y$ are symmetric, independent random walks on the lattice $\mathbb{Z}^2$. I am trying to find the probability: $$\mathbb{P}\big(X_n=Y_n=(0,0)\;\text{for some}\;n\,\big|\,X_0=Y_0=(0,N)\big)$$ i.e. that both eventually meet at the origin given that both start at $A=(0,N)$.


So I think we can write the probability as $\sum_n \big(p_{A,0}^{(n)}\big)^2$ where $p_{ij}^{(n)}$ is the probability of getting from $i$ to $j$ in exactly $n$ steps. But then I'm not sure how to proceed. I'm familiar with the usual random walk where we look at $p_{0,0}^{(n)}$ to prove recurrence, but the starting point here bothers me. I could define hitting times for when each reaches the origin but that doesn't seem like a good idea...

$\endgroup$
1
  • $\begingroup$ Your formula $\sum_n (p^{(n)}_{A,0})^2$ gives not the probability of a meeting, but rather the expected number of meetings. $\endgroup$ May 17, 2016 at 0:31

1 Answer 1

1
$\begingroup$

Consider the positions of the two walkers as corresponding to a point in $\mathbb Z^4$, initially $Z_0 = (N,0,N,0)$. At each step, you add to your current position one of the $16$ possible displacements $S = \{(\pm 1,0,\pm 1, 0), (\pm 1, 0, 0, \pm 1), (0,\pm 1, \pm 1, 0), (0, \pm 1, 0, \pm 1)\}$, with equal probabilities. Since this is four-dimensional, we expect the walk to be transient. The hitting probability for $(0,0,0,0)$, starting at $(x,y,z,w)$, is $u(x,y,z,w)$ where $u(0,0,0,0) = 1$, $u(X) = (1/16) \sum_{s \in S} u(X+s)$ otherwise, and $\lim_{|X| \to \infty} u(X) = 0$. Using Fourier series, this can be expressed in terms of integrals over $[0, 2\pi]^4$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .