1
$\begingroup$

There are 2 drunk guys who walks according to a Random Walk. Each of them, with equal probability of $ 0.5 $ turns either right or left.
They both start at the origin and their turns are synchronized in time (They do the step together at once).

What is the probability that after $ N $ steps the 2 will meet?

$\endgroup$

closed as off-topic by JonMark Perry, Rupert Morrish, athin, Glorfindel, Nautilus Feb 10 at 15:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – JonMark Perry, Rupert Morrish, athin, Glorfindel, Nautilus
If this question can be reworded to fit the rules in the help center, please edit the question.

2
$\begingroup$

There are 2 straight forward solutions to tho which create a nice identity.

Solution 001

Defining the following equivalent random walker for each step $ {x}_{i} $:

$$ \mathbb{P} \left( {x}_{i} \right) = \begin{cases} \frac{1}{4} & \text{ for } {x}_{i} = -1 \\ \frac{1}{4} & \text{ for } {x}_{i} = 1 \\ \frac{1}{2} & \text{ for } {x}_{i} = 0 \end{cases} $$

Defining his walk as $ {S}_{N} = {x}_{1} + {x}_{2} + \cdots + {x}_{N} $.
The equivalent question is $ \mathbb{P} \left( {S}_{N} = 0 \right) = ? $.
Namely when will this walker go back to the origin - do the same number of steps to the left as to the right.

The probability of doing $ k $ steps to the right / left are given by:

$$ {\left( \frac{1}{4} \right)}^{k} {\left( \frac{1}{4} \right)}^{k} {\left( \frac{1}{2} \right)}^{N - k} \binom{N}{k} \binom{N - k}{k} $$

Now going through all valid values of $ k $:

$$ \mathbb{P} \left( {S}_{N} = 0 \right) = \sum_{k = 0}^{ \left \lfloor \frac{N}{2} \right \rfloor } {\left( \frac{1}{4} \right)}^{k} {\left( \frac{1}{4} \right)}^{k} {\left( \frac{1}{2} \right)}^{N - k} \binom{N}{k} \binom{N - k}{k} $$

Solution 002

Let's mark turning left by $ 0 $ and turning right by $ 1 $. Then, each of them is creating a binary number of length $ N $.
In order of them to meet they need to create a number with the same number of $ 1 $ (Hence also $ 0 $) each.

The probability of Walker #1 to create a binary number with $ k $ ones is given by (Ratio between the number of numbers with $ k $ ones and the overall number of numbers with $ N $ digits):

$$ \mathbb{P} \left( k \right) = \frac{ \binom{N}{k} }{ {2}^{N} } $$

The probability they meet is going through $ k = 0, 1, \ldots, N $ and since they are independent, multiply them:

$$ \mathbb{P} \left( {S}_{N} = 0 \right) = \sum_{k = 0}^{n} {\left( \frac{ \binom{N}{k} }{ {2}^{N} } \right)}^{2} = {2}^{-2N} \sum_{k = 0}^{n} {\binom{N}{k}}^{2} = \frac{ \binom{2N}{N} }{ {2}^{2N} } $$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.