Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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.

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.