# Random walk problem

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:

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

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.

-

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.

-