Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Random walk with two agents

  1. Feb 18, 2007 #1
    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

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

    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
  2. jcsd
  3. Feb 18, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    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 PN(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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook