Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

To get you started


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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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