Random walk with two agents

bigplanet401

1. The problem statement, all variables and given/known data
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.


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

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

m is the displacement, i.e. n(steps to the right) - n(steps to the left).
3. The attempt at a solution
I tried considering their relative motion (their separation distance), but had trouble making adjustments to P_N above.
1. The problem statement, all variables and given/known data



2. Relevant equations



3. The attempt at a solution

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.