A Drunk Ant, a Drunk Man and a Drunk Bird: Random Walk in 1D, 2D and 3D

A drunk ant and a drunk man will return back to home but a drunk bird may not. Mathematically, an ant, a man, and a bird is used to model an entity's motion in 1D, 2D, and 3D, respectively. By drunk, we mean that the entity is doing a random walk. In this article, we discuss a counter-intuitive result on random walk in higher dimensions.

Random walk

1d 2d 3d coordinates — 1D, 2D and 3D coordinate systems

Random walk is a well-studied problem in probability and random processes. It models an entity which moves in a random direction at each time step. The random direction is chosen uniformly over all possible options. The number of options depends on the dimension of the random walk.

Aside: Brownian motion is an important example of random walk. It is used to study motion of particles in a medium. Brownian motion is also used to derive several other mathematical results. The article Eclipse attack on a blockchain network uses a test statistic for change detection that converges to Brownian motion asymptotically.

An animation of drunk ant doing random walk in 1D — Drunk ant doing a random walk in 1D

For 1D, the entity can either move left or right, one unit step at a time. shows a drunk ant doing a random walk in 1D.

An animation of drunk man doing random walk in 2D — Drunk man doing a random walk in 2D

For 2D, the entity can chose between a unit step in +X (right), -X (left), +Y (top) or -Y (bottom). shows a drunk man doing a random walk in 2D. Similarly, one can enumerate all possible options for higher dimensions. A drunk ant, a drunk man and a drunk bird are used to model a random walk in 1D, 2D and 3D.

Counter-intuitive result in random walk

The focus of this article is an interesting, counter-intuitive result on random walk. Suppose, I were to ask you this question: if the entity starts from the origin, is it guaranteed that it will return to the origin sometime in the future? Our intuition would suggest that the entity should definitely return to origin, independent of the dimension of the problem. It turns out that this intuition is partially correct and cannot be generalized for all dimensions. Specifically, for random walk in 1 and 2 dimension, the entity is guaranteed to return to the origin, but not in 3 dimension random walk. In this article, we will use mathematics to analyze this result.

Analysis of random walk in 1D, 2D and 3D

In our definition of random walk, random steps were allowed only along the axis. This constraint implies that if the entity starts from the origin, it can return to the origin only after even number of steps. Using this insight, we can calculate \( P_{2n} \), the probability of returning to origin in \(2n\) steps for \(n\) in the set of positive integers. Note that \(P_{2n}\) is not the probability of first return.

For 1D, if the entity returns to the origin, it must have taken \(n\) steps in the right direction and \(n\) steps in the left direction over te. Calculating \(P_{2n}\) using permutation and combination yields,

\[P_{2n}^{1D}=\binom{2n}{n} \left(\frac{1}{2}\right)^{2n}\approx \frac{1}{\sqrt{\pi n}}\]

For 2D, calculating exact expression for \(P_{2n}\) is difficult, hence, it is approximated using its characteristic function. We skip the derivation and mention the final result here.

\[P_{2n}^{2D} \approx \frac{1}{4\pi n}\]

For 3D, calculating exact expression for \(P_{2n}\) is also difficult, hence, we skip the derivation and mention the final result here. For some constant C,

\[P_{2n}^{3D} \approx \frac{C}{n^{3/2}} \]

Recurrence in Markov chain

Random walk is an example of Markov chain on a lattice. A state \(s\) in a Markov chain is transient, if, starting from state \(s\), there is a non-zero probability that it will never return to state \(s\). Otherwise, the state \(s\) is recurrent. To prove our result, we need to prove that the origin is a recurrent state.

We will present an important result from theory of Markov chain to prove that the origin is a recurrent state. The result is as follows. Let \(P_n\) denote the probability of return to the origin in \(n\) steps. Then,

\[\sum_{n=1}^{\infty}P_{n}=\infty \iff \text{Entity returns to the origin infinitely often}\]

The other case

\[\sum_{n=1}^{\infty}P_{n}<\infty \iff \text{Entity returns to the origin finitely often}\]

Note that in our case \(P_n=0\) when \(n\) is odd.

Reimann Zeta function

We will need another important result from theory of series and their convergence to calculate whether \(\sum_{n=1}^{\infty}P_{2n}\) is finite or not. The result is as follows.

\[\sum_{n=1}^{\infty}\frac{1}{n^p}=\infty, p\leq 1\]

\[\sum_{n=1}^{\infty}\frac{1}{n^p}<\infty, p>1\]

Combining above two results, we conclude that the entity definitely returns to the origin in future for 1D and 2D but not in 3D. Moreover, for a random walk in any dimension greater than or equal to 3, the origin is a transient state.

Author

Anurag Gupta is an M.S. graduate in Electrical and Computer Engineering from Cornell University. He also holds an M.Tech degree in Systems and Control Engineering and a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay.

Comment

Past Comments

No comments yet. Be the first!