Calculating the Probability of Two Random Walkers Meeting After N Steps

[mathlete]

The question:

"Two men start out together at the origin, each having a 1/2 chance of making a step to the left or right along the x-axis. Find the probability that they meet again after N steps."

It then says it may help to consider their relative position but I don't see how that would help.

The probability for one person is Wn(n1) = N!/[(n1!)(N-n1)!]*p^n1*q^(N-n2)

where N is total steps, n1 is steps to the right, p = q = 1/2 (for this problem). I just don't know how to combine/adjust it for two people.

Also, I'm not sure, but would this involve an integral from 0 to N steps at some point (to cover all cases)?

edit: I have posted this in the math section as it is more relevant

 

[tim_lou]

i think this is more of a math problem but oh well...

let's consider their "distance function". there is 1/4 chance that they both move right, 1/4 chance that they both move left. In all of these cases the distance function remains constant... consider all other cases, and the increase/decrease of the "distance function".

i guess it is a little bit like the binomial theorem... when the number of increases = number of decreases, the two people meet. the problem with this thing is that the distance can remain constant rather than just two choices (increase and decrease, sucess and failure)... i guess you have to try to figure it out.

 

[tim_lou]

hmmm... this is rather difficult... i guess you have to sum up the probability of all the posibilities.
1 increase, 1 decrease, N-2 remains constant
...and other cases...

and consider what happens when N is odd and when N is even
damn i shouldn't be giving too many hints... i guess i'll just leave it at that.

good luck. the "binomial theorem" with more than "2 variables" should be the essential equation to use (forgot the name of that theorem...i guess we should call it multi-nomial theorem then... hehe).

 

[mathlete]

hmmm... this is rather difficult... i guess you have to sum up the probability of all the posibilities.
1 increase, 1 decrease, N-2 remains constant
...and other cases...

and consider what happens when N is odd and when N is even
damn i shouldn't be giving too many hints... i guess i'll just leave it at that.

good luck. the "binomial theorem" with more than "2 variables" should be the essential equation to use (forgot the name of that theorem...i guess we should call it multi-nomial theorem then... hehe).

Thanks for the response, but I'm not sure I quite understand. This seems very in-depth and complicated for what I think the problem was intended to be.

What I really don't understand is how considering their relative motion helps me in anyway. And on the surface it seems that the probability of them meeting up is just (1/2)^N but that is obviously wrong and way too simple.

I'm completely stuck and don't know what to try next

 

[oasis2007]

Hi... Did you every get the right answer to this question? can you please help me with the answer.

 

[gulaman]

random walk solution

Hey... I have the same homework...

What i did was solve for the probability of having the two drunks separated by distance d...

where,
d = (total steps to the right of both drunks, r) - (total steps to the left of both drunks, l) (eqn 1)
2N = r + l (eqn 2)

the probability would then be,

...hey, i had to edit the post... i just read the guidelines and i totally get the spirit of PF...

anyway... continue from here...
you get the probability... set d=0 (so the two drunks meet)

wahlah! you get the answer!