- #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

- 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