Calculating the Probability of Two Men Meeting Again with a Double Random Walk

[dRic2]

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

 

[StoneTemplePython]

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.

 

[dRic2]

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!}$$

 

[StoneTemplePython]

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.

 

[dRic2]

I'm having some difficulties imaging the equivalent problem of a single random walk with doubled steps. I don't get the equivalence

 

[dRic2]

Ahhh. Got it. Now I can see the equivalence. It took a stroll under the rain ahaha