Double random walk

  • Thread starter dRic2
  • Start date
  • #1
dRic2
Gold Member
723
169

Homework Statement:

Two drunks start out together at the origin, each having equal probability of making step to the left or to the right along the x axis. Find the probability that they meet again after N steps. It is also understood that the men make the steps simultaneously. (It may be helpful to consider the relative motion)

Relevant Equations:

Maybe Multinomial coefficients ?
I set up the problem in the following way: considering the relative motion, at each step there is a probability that
- they take a step in the opposite direction going away from each other, so the distance increases and the associated probability is 1/4
- they take a step in the opposite direction but facing each other, so the distance decreases and the associated probability is again 1/4
- the move in the same direction (both to the left or to the right), so the distance stays the same and the associated probability is 1/2

The probability associated to a particular sequence of step is thus:
$$\left ( \frac 1 4 \right)^a \left ( \frac 1 4 \right)^b \left ( \frac 1 2 \right)^c $$
Where a, b, c are the number of steps associated with one of the above mentioned scenarios. Of course I have the constraint that ##a + b + c = N## where ##N## is the total number of steps. Since I do not care about the particular sequence of steps taken but only abut the final distance between the two men after N steps, I need to take into account al the possible permutations:
$$P_{N, a, b} = \frac {N!} {a! b! (N-a-b)!} \left ( \frac 1 4 \right)^a \left ( \frac 1 4 \right)^b \left ( \frac 1 2 \right)^{(N-a-b)} $$
This probability distribution is of course normalized because, by the multinomial theorem
$$\sum_{a, b} P = \left( \frac 1 4 + \frac 1 4 + \frac 1 2 \right)^N = 1$$
Finally, since in order for the tow men to meet again, I need a = b (the distance must increase and decease pf the same number of units) I get that the probability that the 2 men meet again after N step is:
$$P = \sum_{a = 0}^N \frac {N!} {a! a! (N-2a)!} \left ( \frac 1 4 \right)^a \left ( \frac 1 4 \right)^a \left ( \frac 1 2 \right)^{(N-2a)} $$

Is this method correct up until now ?

My problem is that the result is different. I believe the author of the problem found some trick to evaluate the sum, but I can't find any.


Thanks
Ric
 

Answers and Replies

  • #2
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,163
566
what you have seems to be in the right direction. A few thoughts:

1.) "Find the probability that they meet again after N steps" -- does this mean the probability that they ever meet again after N steps, or the probability of meeting again at the end of exactly N steps? I presume the latter but wanted to make sure.

2.) You have (nearly) identified the isomorphic problem of a single random walker who moves left one step with probability ##\frac{1}{4}## and right one step with probability ##\frac{1}{4}## and stays in place with probability ##\frac{1}{2}##... there are two nice ways to interpret this-- (i) this can be interpretted as a regular simple random walk starting at the origin, considered 2 steps at a time (and then purge all odd nodes since such a walk is bipartite and odd nodes aren't reachable on even steps) or (ii) or if you look at the (countably infinite) transition matrix for a regular simple random walk given by ##P##, what you have is the lazy random walk given by ##\frac{1}{2}(P+I)##. I think (i) will be more amenable to combinatorial methods.

3.) The one nit I see with modelling this as ##\frac{1}{4}## and right one step with probability ##\frac{1}{4}## and stays in place with probability ##\frac{1}{2}##, is what about when their distance is zero? I'd consider this being equivalent to a random walk and 'the origin'. Here I see they stay at the origin with probability ##\frac{1}{2}## and distance increases 'one unit' with probability ##\frac{1}{2}##.

I think you can turn this into an appropriate ballot problem and get the answer though I try to avoid combinatorial methods until the very end.
 
  • #3
dRic2
Gold Member
723
169
Thanks for the replay

1) yes, the latter

2) Mhm... too advanced for me... what's an isomorphic problem ?

3) Mhm I don't think there is a problem with the distance being zero. It's true what you say but looking at the expression
##P_{a, b, N} = \frac {N!} {a!b!(N-a-b)!} \left( \frac 1 4 \right)^a \left( \frac 1 4 \right)^b
\left( \frac 1 2 \right)^{N-a-b}##
for N=1 the constraint ##N = a + b + c## means that I can only have
- ##a = 1##, ##b = 0## and ##c = 0##
- ##a = 0##, ##b = 1## and ##c = 0##
- ##a = 0##, ##b = 0## and ##c = 1##
In the first two cases I get correctly that ##P = \frac 1 4 + \frac 1 4 = \frac 1 2## is the probability that the distance increases. Otherwise if they both move in the same direction I also get correctly c = 1 and so ##P = \frac 1 2##

*********

I'm weak. I gave up and looked for a solution. I feel bad, but I must admit that I would have never figured it out. Oh it's so beautiful. Here it is:

If I look at the expression I found for the probability
$$P = \sum_{a=0}^N \frac {N!}{a!a!(N-2a)!} \left( \frac 1 4 \right)^a \left( \frac 1 4 \right)^a \left( \frac 1 2 \right)^{N-2a}$$
you can notice that it can be obtained from the general expression (multinomial theorem)
$$(1/2 + 1/4 + 1/4)^N = \sum_{a+b+c=N}^N \frac {N!}{a!b!c!} \left( \frac 1 4 \right)^a \left( \frac 1 4 \right)^b \left( \frac 1 2 \right)^c$$
by selecting only the terms with ##a = b## . A ver cleaver and beautiful way to "select" those terms is by evaluating instead the following expression
$$\sum_{a+b+c=N}^N \frac {N!}{a!b!c!} \left( \frac x 4 \right)^a \left( \frac 1 {4x} \right)^b \left( \frac 1 2 \right)^c$$
You can easily see that when ##a = b## the ##x## cancel out and so, for ##a = b##, the terms of this expression are exactly equal to the ones belonging to the expansion of ## \left( \frac 1 4 + \frac 1 4 + \frac 1 2 \right)^N## (which are the one that I need to evaluate).

By the multinomial theorem I get
$$\sum_{a+b+c=N}^N \frac {N!}{a!b!c!} \left( \frac x 4 \right)^a \left( \frac 1 {4x} \right)^b \left( \frac 1 2 \right)^c = \left( \frac 1 {4x} + \frac x 4 + \frac 1 2 \right)^N$$

Exploiting the useful identity ##(z^{1/2} + z^{-1/2})^2 = (z + 1/z + 2)## and expanding with the binomial theorem the resulting square therm:
$$ \left( \frac 1 {4x} + \frac x 4 + \frac 1 2 \right)^N = \left( \frac 1 2 \right)^{2N} \sum_{k = 0}^{2N} \frac {(2N)!} {k!(2N-k)!}(x^{1/2})^k(x^{-1/2})^{2N-k}$$
Now I have to remember that I did all this mess to find the terms where the ##x## cancel out. Looking at the above expression I see that this happens only for ##k = 2N - k##, that is ##k = N##.
So finally I get that
$$P = \left( \frac 1 2 \right)^{2N} \frac {(2N)!}{(N!)N!}$$
 
  • #4
StoneTemplePython
Science Advisor
Gold Member
2019 Award
1,163
566
2) Mhm... too advanced for me... what's an isomorphic problem ?
a fancy term for 'equivalent'...

....
So finally I get that
$$P = \left( \frac 1 2 \right)^{2N} \frac {(2N)!}{(N!)N!}$$
yes, but there's a very easy way to this result. If you understand that your problem is equivalent to a simple random walk (1 person) but viewed 2 steps at a time, this literally reads, on the ##2N##th iteration, what's the probability of getting N heads and N tails (i.e. starting at the origin and a heads being a +1 and a tails being -1, what's the probability of being at the origin on the 2Nth toss), then binomial distribution for coin tossing tells you this happens with probability ##\left( \frac 1 2 \right)^{2N} \frac {(2N)!}{(N!)N!}##. That's really it.
 
  • Like
Likes dRic2
  • #5
dRic2
Gold Member
723
169
I'm having some difficulties imaging the equivalent problem of a single random walk with doubled steps. I don't get the equivalence
 
  • #6
dRic2
Gold Member
723
169
Ahhh. Got it. Now I can see the equivalence. It took a stroll under the rain ahaha
 
  • Like
Likes StoneTemplePython

Related Threads on Double random walk

  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
18
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
1
Views
454
Top