Random walk with two agents

  • #1
104
0

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

[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).

The Attempt at a Solution


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

Homework Statement





Homework Equations





The Attempt at a Solution

 

Answers and Replies

  • #2
AKG
Science Advisor
Homework Helper
2,565
4
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.
 

Related Threads on Random walk with two agents

  • Last Post
Replies
6
Views
561
Replies
16
Views
590
Replies
16
Views
24K
Replies
1
Views
2K
Replies
13
Views
3K
  • Last Post
2
Replies
25
Views
5K
  • Last Post
Replies
4
Views
14K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
2K
Top