1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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