A Random Walk on the Wild Side

Sophie Maclean

It is midnight in New York. A drunkard sets off from home, and goes for a walk. In their inebriation, at each crossroads they randomly choose a direction with equal probability. North with probability ¼. East with probability ¼. South with probability ¼. West with probability ¼. Will they find their way home?

Before I get the comments pouring in, no, this story does not have to be set in New York. It can be in any city with a grid system. But setting this in Milton Keynes did not seem nearly as exciting.

For most of us, this situation (in New York or in Milton Keynes) is one that we are unlikely to ever find ourselves in. But it does pose an interesting mathematical question. If we choose our directions randomly, do we ever get home?

This is an example of what is called a random walk. A random walk is a process by which your location is determined from a sequence of random steps. We will look at the simplest kind of random walk, known, rather aptly, as a simple random walk. There are many, MANY more random walks. Enough that you could write a book on them. But that is for another time.

Graph showing 3 axes, and 'Probability = 1/2^n' written in all directions

A simple random walk in \(d\) dimensions is when, at each time step, you travel forward or backward with equal probability in a direction chosen from all \(d\) possible perpendicular directions with each direction being equally likely. This means that each move has probability \(1/{2^{2d}}\).

Now, this is a model for our drunkard’s midnight stroll. Our drunkard clearly lives in 2D as they can’t fly, and their home is at the origin (0,0). At each crossroads, they choose to add \((1,0), (-1, 0), (0, 1), (0,-1)\) to their position, each with probability \(¼\). Do they return home?

What if they could fly? What if, instead, they could move in four dimensions? We are getting ahead of ourselves now though. Let us first take this back to the simpler situation of being 1D.

A simple diagram of a one-dimensional random walk. A red dot represents a particle at the center position. Arrows show the particle can move left or right with equal probability (P = 1/2).

Toeing the Line

Let’s say that our drunkard starts at point 0 at time 0. In this simplified model, the drunkard can only move forward and backwards, not side to side. How do we know if they return or not? Well, first, we need to introduce some notation.

We will denote by \(z_n\) the probability that the drunkard is at 0 at time n (to remember this, z stands for zero). There are a few things we can say about \(z_n\), without having to do any calculations:

As they start at 0, z_0 = 1.
\(z_n\) is a probability so it will always be in the interval \([0,1]\)
If \(n\) is odd, \(z_n =0\). This one might be less immediately obvious, but clearer when you notice that in every step, you go from odd to even or even to odd i.e. the parity changes. Therefore when \(n\) is odd, you might be at an odd location and therefore not zero.

We sometimes don’t just care about whether the drunkard is at 0, it is also important to know if it is the first time they have been back to 0. Let us say that \(f_n\) is the probability that they return to 0 for the first time at time \(n\).

Again, we have that \(f_n = 0\) if \(n\) is odd, and that \(f_n\) is in the interval \([0,1]\). One possibly unexpected, but useful, thing we will do is that we will say \(f_0 =0\). This is because, whilst we are at 0 at time \(n=0\), they have not returned there yet.

Intuitively, \(z_n\) is simpler to calculate than \(f_n\). For \(z_n\) we only need to know where the drunkard is right now. For \(f_n\) we also need some information about where they have been. But \(f_n\) is a very important quantity. This is because if we sum the probabilities of returning to 0 for the first time at every time \(n\), we get the probability that we return to 0 at any time.

Putting this symbolically, if

\( f = \sum_{n=0}^\infty f_n\),

then \(f\) is the probability that we ever return to 0, and \(1-f\) is the probability that we never return to 0. ¹

Back to our problem. So \(f_n\) is important, and \(z_n\) is simpler to calculate. We had better hope that there is an expression relating the two! Thankfully there is. It relies on a key property of random walks: the “memoryless” property. This property tells us that it does not matter where we have been, only where we are right now. For example, suppose we find ourselves at position 1. The probability that we next go to 0 is independent of how many times we have visited 0 before.

Therefore, suppose the drunkard first returns to 0 at time k. Then the probability that they are at 0 again at time m is z_{k-m}. If we sum this over all k, we get the probability that they are at 0 at time m.

For a concrete example:

\( z_2 = z_2f_0 + z_1f_1 + z_0f_2\)

In other words, the probability the drunkard is at 0 at time 2, is the probability they return to 0 for the first time at time 2, plus the probability they return to 0 for the first time at time 1 and return again after 1 step, plus the probability they return to 0 for the first time at time 0 and return again after 2 steps.

In this case, you may notice that, since \(f_n = 0\) if \(n\) is odd, and \(f_0 = 0\), \( z_2 = z_1f_1 \). So perhaps more constructive is to consider \(z_4 = z_4f_0 + z_3f_1 + z_2f_2 + z_1f_3 + z_0f_4 = z_2f_2 + z_0f_4\).

Diagram showing two different paths starting at the origin point (labeled "O") on a number line. One path (in blue, looping leftward) returns to the starting point after 2 steps and again after 2 more steps, forming a small loop. The other path (in green, looping rightward) returns after 4 steps, forming a larger loop. Arrows indicate the direction of movement along each loop.

In general, \(z_m = \sum_{k=0}^m z_k f_{m-k}\).

So it looks like we are getting somewhere!

Mathsy Magic

Now it is time for some mathematical hocus pocus. If you want a quick answer to the question “why do we do this?”, then the reason is because it works and we know it works. The longer answer goes through years of probability theory and the revolutionary idea of generating functions. But that is a blog post for another time (or a google search if you are particularly keen). For now, you just have to trust me.

We are going to define

\(Z(s) = z_0 + z_1s + z_2s^2 + \dots\).

Similarly,

\(F(s) = f_0 + f_1 s + f_2 s^2 + \dots\).

Now,

\( Z(s)F(s) = z_0f_0 + (z_1f_0 + z_0f_1) s + (z_2f_0 + z_1f_1 + z_0f_2)s^2 + \dots\)

\(= 0 + z_1s + z_2 s^2 + \dots = Z(s) -1\).

To get the second line, we use that \(z_m = \sum_{k=0}^m z_k f_{m-k}\), as shown above.

By rearranging this equation, we get that \(1 = Z(s)(1-F(s))\). We could also rearrange this to get \(Z(s) = 1/(1-F(s)\) or even \(F(s) = 1 – 1/Z(s)\).

Remember the question we are trying to answer: Is one guaranteed to return to 0 on a simple random walk starting at 0? In the language we have developed, this is asking if \(f=1\).

But look!

\(F(s) = f_0 + f_1 s + f_2 s^2 + \dots\) so

\(F(1) = f_0 + f_1 + f_2 + \dots = f\).

We therefore now have another expression for \(f\). \(f = F(1)\). This means that if \( F(1) =1\), then our drunkard does return home. And if \( F(1) \ne 1\), they don’t.

We showed earlier that \(Z(s) = 1/(1-F(s))\), so let us consider what happens when \(s = 1\). Substituting \(F(1) = 1\) into this equation gives \(Z(1) = \infty\). Depending on what maths you do, you may or may not be happy with the dividing by infinity that went on there. To satisfy those that aren’t impressed, assuming \(F(1) = 1\),

\(\lim_{s\to 1} Z(s) = \lim_{s\to 1} 1/ (1 – F(s)) =\infty\).

We now have that if \(Z(1) =\infty\) then the drunkard does return to \(0\). If not, they do not. So we want to determine whether or not \(Z(1) = \infty\).

Getting Those Zzzzzs

Now the final step! Calculate \(Z(1) = z_0 + z_1 + z_2 +\dots = \sum_{n=1}^{\infty} z_n \). Remember that fact from the beginning? That \(z_n = 0\) if \(n\) is odd. That means that \(Z(1) = \sum_{n=1}^{\infty} z_{2n}\).

The next step is to find \(z_{2n}\), the probability of returning to 0 after \(2n\) steps. Remember that in the case we are looking at, there is an equal probability of going in each direction at each step.

This is now a classic problem in probability as it’s finding how many ways we can take \(n\) steps right and \(n\) steps left. Alternatively, we are taking \(2n\) steps and exactly \(n\) of them are left (and the other \(n\) are right). The probability of a given step being left (or right) is \(1/2\). So \(z_n = \frac{\begin{pmatrix} 2n \\ n \end{pmatrix}}{2^{2n}}\).

A fun little maths fact called Stirling’s formula tells us that \(\begin{pmatrix} 2n \\ n \end{pmatrix} \approx \frac{2^{2n}}{\sqrt{\pi n}}\). So \( z_{2n} = \frac{1}{\sqrt{\pi n}}\)

Now just one tiny little bit of algebra left…

\(Z(1) = \sum_{n=1}^{\infty} z_{2n} \approx \sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}} = \infty\)

… and we’re done! Proof that, at least in 1D, our friend does always return home.

Moving Up a Dimension

Things get a bit more complicated in higher dimensions. Well, all the maths is the same up until the point where we calculate \(z_{2n}\). That is to say, \(Z(1) = \sum_{n=1}^{\infty} z_{2n}\), and that the drunkard returns to \(0\) if and only if \(Z(1) =\infty\).

What is different in higher dimensions is the expression for \(z_{2n}\). In 2D, our person can now move left, right, forward, and back, each with probability \(¼\). Putting this on a graph, we can describe this as moving \((+1,0), (-1, 0), (0, +1), (0,-1)\) each with probability \(¼\).

A red dot is shown at the center of a 2D grid with horizontal and vertical axes. Four red arrows point outward from the dot to adjacent grid points, labeled with coordinate changes: up (0, +1), down (0, -1), left (-1, 0), and right (+1, 0). The diagram illustrates movement from a central point to its four immediate neighbors on a grid.

Imagine rotating everything by ⅛ circle, and dilating it by \(\sqrt(2)\). Now we move \((+1,+1), (-1, +1), (+1, -1), (-1,-1)\) each with probability \(¼\).

A red dot is shown at the center of a 2D grid with diagonal axes. Four red arrows point outward from the dot to adjacent grid points, labeled with coordinate changes: up right (+1, +1), down right (+1, -1), down left (-1, -1), and up left (-1, +1). The diagram illustrates movement from a central point to its four immediate neighbors on a grid.

This can now be viewed as two independent random walks in the x and y directions so \(z_{2n} \approx \big( \frac{1}{\sqrt{\pi n}}\big)^2 = \frac{1}{\pi n}\).

Therefore \(Z(1) = \sum_{n=1}^{\infty} z_{2n} = \sum_{n=1}^{\infty} \frac{1}{\pi n} = \infty\), so, again, we return to the start. A drunk person in New York always returns home.

In 3 dimensions, it gets a lot more calculation heavy, so I will not go through it in its entirety. Essentially, one must sum over how many steps are taken in the x direction, the y direction, and the z direction, and make sure in each case that the number of ”forward” steps equals the number of “backward” steps. But what you get at the end is that \(z_{2n} \leq 2^{-2n} \begin{pmatrix} 2n // n \end{pmatrix} \frac{c}n \approx\ \frac{1}{\sqrt{\pi n}} \frac{c}n = \frac{x}{\pi n^{3/2}}\) for some fixed and calculatable \(c\).

Hence, in this case, \(Z(1) = \sum_{n=1}^{\infty} z_{2n} \leq \sum_{n=1}^{\infty} \frac{C}{\pi n^{3/2}} < \infty\). This means that with probability 1, we never return to the start. A drunk bird is set to roam the skies forever.

And what about higher dimensions? Well if we cannot return home in 3 dimensions, we certainly cannot return home in higher dimensions. That would necessarily require going back to where we started in 3 dimensions too!

So bad luck for any 4 dimensional beings out there. You will never return home…

A quick aside here: the \(\Sigma\) symbol is just saving us some time and space. \(\sum_{i=a}^b x_i\) means sum all the values of \(f_i\) from when \(i=a\) up to when \(i=b\) i.e. \(\sum_{i=a}^b x_i = x_a + x_{a+1} + a_{x+2} + \dots + x_{b-1} + x_b \). ↩︎

The post A Random Walk on the Wild Side originally appeared on the HLFF SciLogs blog.

Back