Probability related to random walks in two dimensions I'm trying to show that two random walks will eventually meet in a two dimensional setting but I can't figure out where to start. Can someone lead me towards the right direction?
 A: To get you started
Read http://stat.math.uregina.ca/~kozdron/Research/Talks/duke_polya.pdf
Do not analyze two random walks. Your problem can be replaced with a single random walk with:
$$P(2R)=P(2U)=P(2L)=P(2D)=\frac{1}{16}$$
$$P(1R,1U)=P(1R,1D)=P(1L,1U)=P(1L,1D)=\frac{2}{16}$$
$$P(0U,0D)=\frac{4}{16}$$
This last can be thrown away as it doesn't change the state giving
$$P(2R)=P(2U)=P(2L)=P(2D)=\frac{1}{12}$$
$$P(1R,1U)=P(1R,1D)=P(1L,1U)=P(1L,1D)=\frac{2}{12}$$
Please post your solution.
A: I happened to stumble across this question, and while your homework deadline might be over a long time ago, and you haven't been online for a few months, Ricky, I thought I might give a shot at proving it anyways. It is a fun problem.
So, let $P_1(t)$ and $P_2(t)$ be the two random walk trajectories. Then define the following:
$$
P(s) = \begin{cases}P_1\left(\frac{s}{2}\right) - P_2\left(\frac{s}{2}\right) & \text{for s even}\\ P_1\left(\frac{s+1}{2}\right) - P_2\left(\frac{s-1}{2}\right) & \text{for s odd}\end{cases}
$$
$P$ is now the trajectory of a random walk. If $P$ is ever at the origin, that would mean that $P_1$ and $P_2$ met up, and we know that a single random walk almost always ends up back at the origin eventually.
The only immediate problem is that if $P(s) = (0, 0)$ for some odd $s$, then $P_1$ and $P_2$ will have been at the same grid point, but at slightly different times. Luckily, this can never happen, since if for a given $s$ we have $P(s) = (x, y)$, then the parity of $s$ is the same as that of $(x + y)$. That means that a (standard) random walk will never ever be at the origin after an odd number of steps, and we are done.
