Meeting of 2 Drunk Walkers (Random Walk) [closed]

Question

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?

Answer 1

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