Random Walk of Two Drunks

The one-dimensional random walk is a key foundational concept in statistical physics which crops up in a variety of situations, albeit normally with far more dimensions. This light-hearted question which is circling amongst statistical physics professors serves as a good introduction to random walks.

If you were set this as a homework and were struggling with where to go, about now would be a good time to pat yourself on the back.

Question

Two persons each move in a one-dimensional random walk. The properties of the random walks are identical for the two, that is, each takes a forward step with probability \(p\) and a backward step with probability \(q=1-p\). The steps are of equal size and are taken at the same times. Given that the two start their random walk at the same location, what is the probability that they meet back at that location after they have each taken \(N\) steps? Assume each direction has an equal probability (i.e. \(p=q=0.5\)).

Solution

At any given point, the displacement from the origin \(D\) will be \(N_{\text{right}}-N_{\text{left}}\) : $$D = x-(N-x)$$where \(x\) is the number of steps right and \(N\) the total number of steps.

Thus we can write \begin{equation} D=2x-N \label{eq:D} \end{equation}

The probability of having taken \(x\) steps to the right after \(N\) steps is Binomial: $$P_N(x)=\frac{N!}{x!(N-x)!}p^xq^{N-x}$$

In terms of displacement \(D\), from \eqref{eq:D} we find: \(x=\frac{D+N}{2}\), and \(N-x=N-\frac{D+N}{2}=\frac{N-D}{2}\).

Therefore we can rewrite the probability in terms of \(D\) and \(N\):

\(P_N(x)=\frac{N!}{\left(\frac{D+N}{2}\right)! \left(\frac{N-D}{2}\right)!}p^{\frac{D+N}{2}}q^{\frac{N-D}{2}}\)

For the given situation, \(p=q=\frac{1}{2}\), the total number of steps is \(N\) for each drunk, giving \(2N\) in total, and the displacement \(D\) must be zero, since they are said to meet.¹

This gives us \(P_{2N}(x=\frac N2)=\frac{(2N)!}{\left(\left(\frac{2N}{2}\right)!\right)^2}p^Nq^N=\frac{(2N)!}{N!^2}p^Nq^N\) \()=\frac{(2N)!}{(2^N N!)^2}\)

So the probability of the two drunks meeting again after N staggers is \(P_{2N}(x=\frac N2)=\frac{(2N)!}{(2^N N!)^2}\).