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$
  • $\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$ – Robert Israel May 17 '16 at 0:31
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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