Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers 3

up vote 2 down vote accepted

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?

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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