What Is the Probability of Two Random Walkers Meeting Again After N Steps?

[bigplanet401]

Homework Statement

Two drunks start out together at the origin, each having equal probability of making a step to the left or right along the x-axis. Find the probability that they meet again after N steps. It is understood that the men make their steps simultaneously.

Homework Equations

Binomial theorem. The probability P_N(m) to the single-agent problem is

<br /> P_N(m) = \frac{N!}{[(N+m)/2]! [(N-m)/2]!} \left(\frac{1}{2}\right)^N \, ;<br />

m is the displacement, i.e. n(steps to the right) - n(steps to the left).

The Attempt at a Solution

I tried considering their relative motion (their separation distance), but had trouble making adjustments to P_N above.

 

[AKG]

Suppose you have a drunk that has 1/4 chance of taking 2 steps to the right, 1/4 chance of taking 2 steps to the left, and 1/2 chance of standing still (taking a "step" of zero distance). What's the probability of this drunk returning to his starting position after N "steps" (where "standing still" counts as a step)? Your book must derive the equation you gave for P_N(m). Maybe you can follow the reasoning there and work out an equation for the drunk I'm describing.

The drunk I'm describing returns to the origin if he takes as many left steps as he does right. He can take anywhere from 0 to floor(N/2) steps left and the same number right. So find the probability that he takes k steps left, k steps right, and N-2k steps nowhere, and then take the sum from k=0 to k=floor(N/2). For some arbitrary k, the probability that he takes k left, k right, and N-2k nowhere is (1/4)^k(1/4)^k(1/2)^N-2kX(k,N) where X(k,N) is the number of ways to take N total steps with k to the right, k to the left, and N-2k nowhere. X(k,N) should just be (N choose k)(N-k choose k), or equivalently (N choose 2k)(2k choose k).

I don't know that this will directly lead to a desired result, think of other ways to count. Instead of conditioning on the number of left steps, maybe condition on the number of steps up to the last lateral step (i.e. the number of steps before the drunk stays still at the origin for the remainder of the steps), or maybe something else.