3.5 Random Walk Models

3.5.1 The one-dimensional random walk

The simple random walk on the integers has \(P_{i,i + 1} = p\) and \(P_{i,i - 1} = 1 - p\) for every integer \(i\), with \(0<p<1\). It is irreducible, so it suffices to decide whether state \(0\) is recurrent. A return to \(0\) is possible only after an even number of steps, with equally many steps each way, so \(P_{00}^{(2n + 1)} = 0\) and \[P_{00}^{(2n)} = \binom {2n}{n}p^n(1 - p)^n .\] By Stirling’s formula \(n!\sim n^{n + \frac 12}e^{-n}\sqrt {2\pi }\), so \(\binom {2n}{n} = \frac {(2n)!}{(n!)^2}\sim \frac {4^n}{\sqrt {\pi n}}\) and \[P_{00}^{(2n)}\sim \frac {\left [4p(1 - p)\right ]^n}{\sqrt {\pi n}} .\]

• If \(p = \frac 12\), \(4p(1 - p) = 1\) and the terms behave like \(\frac {1}{\sqrt {\pi n}}\), whose sum diverges. The symmetric walk is recurrent.
• If \(p\ne \frac 12\), then \(4p(1 - p) = 1 - (2p - 1)^2<1\), the terms decrease geometrically, and the sum converges. The walk is transient: it drifts off to \(+\infty \) or \(-\infty \).

3.5.2 Symmetric random walks in two and three dimensions

In two dimensions the walk moves one step up, down, left or right, each with probability \(\frac 14\). A return in \(2n\) steps needs \(i\) steps right, \(i\) left, \(n - i\) up and \(n - i\) down for some \(i\), so \begin {align*} P_{00}^{(2n)} &= \sum _{i=0}^n\frac {(2n)!}{i!\,i!\,(n - i)!\,(n - i)!}\left (\frac 14\right )^{2n} = \left (\frac 14\right )^{2n}\binom {2n}{n}\sum _{i=0}^n\binom ni\binom {n}{n - i}\\ &= \left [\left (\frac 12\right )^{2n}\binom {2n}{n}\right ]^2, \end {align*}

using Vandermonde’s identity \(\sum _i\binom ni\binom {n}{n - i} = \binom {2n}{n}\). So \(P_{00}^{(2n)}\sim \frac {1}{\pi n}\), the sum diverges, and the two-dimensional symmetric walk is recurrent.

In three dimensions the walk moves one unit in one of the six directions \(\pm x, \pm y, \pm z\), each with probability \(\frac 16\). Counting the ways to take \(j\) steps each way in \(x\), \(k\) in \(y\) and \(n - j - k\) in \(z\), \[P_{00}^{(2n)} = \left (\frac 12\right )^{2n}\binom {2n}{n}\sum _{j + k\leq n}\left [\frac {n!}{j!\,k!\,(n - j - k)!}\left (\frac 13\right )^n\right ]^2 .\] The bracketed terms are trinomial probabilities, which sum to \(1\), so the sum of their squares is at most their largest value, attained near \(j = k = \frac n3\); by Stirling’s formula that value is of order \(\frac 1n\). Together with \(\left (\frac 12\right )^{2n}\binom {2n}{n}\sim \frac {1}{\sqrt {\pi n}}\) this gives \(P_{00}^{(2n)}\leq \frac {C}{n^{3/2}}\) for a constant \(C\), and \(\sum _nn^{-3/2}<\infty \). The three-dimensional walk is transient: it returns to its starting point with probability about \(0.34\) only. This is Pólya’s theorem: a drunk man finds his way home, but a drunk bird may not.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.