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?

• This feels like it's equivalent to a random walk by one particle. If you write their positions as $x_t$ and $y_t$ and denote the distance between them by $d_t=x_t-y_t$ then $d_0=0$ and at each stage, $d_{t+1}$ is either $d_t$ (probability $1/2$), $d_t-2$ (probability $1/4$) or $d_t+2$ (probability $1/4$). – Chris Taylor Mar 8 '12 at 22:47
• Yes, it is just what I thought and following that idea I found the summation above. Can you rewrite it in a nicer form? – quark1245 Mar 8 '12 at 22:52
• The no. of left movement should be same for both persons.Hence the probability is ${1}\over{N}$, since N is no. of distinct left movements. – quartz Mar 8 '12 at 23:02

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?

• About your second hint: the condition we need is that the number of left moves is equal for the two drunks, or that the number of left moves of the first + the number of right moves of the second is equal to N. The number of all possible walks is $4^N$. Call $n$ the number of left moves of the first drunk. We can choose these $n$ moves in $(N\,\,\,\, n)$ ways. The number of left moves of the second drunk must be $n$ too and so the probability is $\sum_{n=0}^N=(N \,\,\,\, n)^2/4^N$, that is $4^{-N}(2N\,\,\,\, N)$. Is this right? Thanks – quark1245 Mar 8 '12 at 23:30
• This is right, but there is a slightly shorter reasoning. Both path are entirely determined by the data of the $N$ left moves of the firsts + right moves of the second, so there is $(2N N)$ good paths, among the $4^N$ possible paths. – D. Thomine Mar 8 '12 at 23:38

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.

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.

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