Exact Probability of Collision of Two Independent Random Walkers After N Steps

Two drunks start together at the origin at $t=0$ and every second they move with equal probability either to the right or to the left, each drunk independently from the other. What is the probability that after $N$ seconds they meet again?

I may be on something but I don't know how to write this sum in a close form:

\begin{equation} \sum_{n=0}^{[N/2]}\frac{N!}{n!n!(N-2n)!}\frac{1}{2^{N+2n}} \end{equation}

Any hints?

Solution 1:

Here are two hints:

First hint : We look at how the second drunk moves relatively to the first drunk. If $A_n$ and $B_n$ are the positions of respectively the first drunk and of the second drunk at time $n$, then you can prove that $(A_n - B_n)$ is a random walk, and you are now interested in its return time at $0$.

What is the transition process of this new random walk? Can you express it with a simpler random walk (hint : simple random walk)?

Second hint : This second hint is independent from the first. Now, let us try to find a combinatorial answer. Fiw the time $n$. Let us denote by $L_1$ the left move of the first drunk until time $n$, by $R_1$ its right moves, by $L_2$ the left moves of the second drunk, and by $R_2$ the right moves of the later. The sequence of moves untile time $n$ can be describe by two sequences, say:

$$L_1 L_1 R_1 L_1 R_1 R_1 R_1 \cdots L_1$$ $$L_2 R_2 R_2 L_2 L_2 L_2 R_2 \cdots L_2$$

Say what it means for the two drunks to be at the same place at time $n$. In particlar, what condition on (number of $L_1$ + number of $R_2$) is equivalent to this event?

Solution 2:

As @Chris Taylor mentioned, it is equivalent of having one walker with the following PDF for the each step:

$$ p\left ( x \right ) = \left\{\begin{matrix} -1 & \frac{1}{4} \\ 0 & \frac{1}{2} \\ 1 & \frac{1}{4} \end{matrix}\right. $$

Now we have to calculate the probability of him to get back to the origin. The trick is understand that given he did $ k $ steps to the right he must do $ k $ steps to the left the rest of the steps are standing still.
Moreover, $ k $ is limited up to half of the steps, $ N $, namely, $ k \leq \left \lfloor \frac{N}{2} \right \rfloor $.

Defining $ {S}_{N} = {x}_{1} + {x}_{2} + \cdots + {x}_{N} $ and calculating $ p\left ( {S}_{N} = 0 \right ) $ which is the probability of being at the origin at the $ N $ step yields:

$$ 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 - 2k} \binom{N}{k}\binom{N - k}{k} $$

The logic is, we sum all over the possibilities of routes of the length $ N $ with the same number of right and left turns (Hence choosing $ k $ steps of $ N $ steps and then $ k $ of $ N - k $ left steps).

Another point of view is looking at the route of the 2 walkers as a binary chain.
Each of them creates a chain of length $ N $.

We want the two chains to have the same number of $ 1 $ in them.
If walker A made a chain with length $ N $ which includes $ k $ times $ 1 $ walker B must have a chain of length $ N $ with exactly $ k $ times $ 1 $ which there are $ \binom{N}{k} $ options.
Walker A also has the number of options to have a chain with $ k $ times $ 1 $.

The total number of chains is $ {2}^{N} $.
Which yields:

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

Which give us a nice identity.

Solution 3:

Disclaimer: This is, so far, one of my most downvoted answers on the site. Needless to say, it is perfectly correct, and it answers the question. The downvotes might be due to some extra-mathematical reasons. Happy reading!

Hint: characteristic functions.

The relative movement $X$ in one step has characteristic function $\varphi$ where $\varphi(t)=\mathrm E(\mathrm e^{\mathrm itX})=\frac12+\frac14\mathrm e^{\mathrm it}+\frac14\mathrm e^{-\mathrm it}$ hence $\varphi(t)=\frac12(1+\cos t)=\cos^2\left(\frac{t}2\right)$. The relative position $S_N$ after $N$ steps has characteristic function $\varphi(t)^N=\cos^{2N}\left(\frac{t}2\right)$.

The probability that the two walkers meet at time $N$ is $p_N=\mathrm P(S_N=0)=\int\limits_0^{2\pi}\mathrm E(\mathrm e^{\mathrm itS_N})\frac{\mathrm dt}{2\pi}$ hence $p_N=\int\limits_0^{2\pi}\cos^{2N}\left(\frac{t}2\right)\frac{\mathrm dt}{2\pi}=\frac2\pi\int\limits_0^{\pi/2}\cos^{2N}(t)\mathrm dt$.

Finally, $p_N=\frac2\pi W_N$, where $W_N$ is a Wallis integral, whose value is well known.

Solution 4:

Suppose $X_n$ is the coordinate of the first man after $n$ steps, and $Y$ - of the second one. Suppose $Z_n = X_n - Y_n$. Then your problem is equivalent to finding $P(Z_N = 0)$. We see, that $$Z_n - Z_{n-1} = \begin{cases} 2 & \quad \text{ with probability } \frac{1}{4} \text{ (the probability that the first one makes a step right and the other a step left) } \\ 0 & \quad \text{ with probability } \frac{1}{2} \text{ (the probability that they move in the same direction) } \\ -2 & \quad \text{ with probability } \frac{1}{4} \text{ (the probability that the first one makes a step left and the other a step right) } \end{cases}$$

And each step is assumed to be made independently.

Suppose $N_1$ is the number of the occurrences of the first case, $N_2$ - of the second case, and $N_3$ - of the third case. Then, in case $Z_N = 0$ we have $N = N_1 + N_2 + N_3$ and $N_1 = N_3$. There are $C_{N}^{N_2}C_{N - N_2}^{\frac{N - N_2}{2}}$ such configurations for any fixed $N_2$, such that $N \equiv N_2 (\text{mod }2)$ (and $0$ otherwise). And the probability of each of them is $\frac{1}{2^{N_2}}\frac{1}{4^{N - N_2}} = \frac{1}{2^{2N - N_2}}$. Thus, we have $$P(Z_N = 0) = \begin{cases} \frac{\Sigma_{i = 0}^{\frac{N}{2}} C_{N}^{2i}C_{N - 2i}^{\frac{N}{2} - i}}{4^{N - i}} & \quad N \text{ is even} \\ \frac{\Sigma_{i = 0}^{\frac{N-1}{2}} C_{N}^{2i+1}C_{N - 2i-1}^{\frac{N-1}{2} - i}}{2^{2N - 2i - 1}} & \quad N \text{ is odd}\end{cases}$$

That is your answer.