Lost in Space

Lost in Space

Want to hear about something in mathematics that terrifies me but no one else seems to care about? Pólya's Random Walk Constants.

Let's talk about random walks to begin. Imagine you are walking in a corridor and you can either go left or right. To decide which way to step next you flip a coin and go left on a tail and right on a head. After taking the step you flip again and you keep this process going forever.

If we call your starting point the origin, then after one step you are either just to the left or just to the right of it. Will you ever return to the origin? Well yes that seems at least possible. A better question becomes with what probability will you return to the origin eventually? Well you have a half chance of returning on step 2. However the other half the time on step 2 you will go even further the other way. You chance of being at the origin after taking your fourth step (note that it will always be an even number of steps) would be ¼, with the possibility of this being your second return. Extending this we have the chance you return eventually as ½+¼+⅛+...+(½)^n+... Summing this up we get a probability of 1. In other words it will definitely happen.

To phrase this in another way, if we flip a coin an infinite number of times then at some point we will have the same number of heads and tails. In fact this will happen an infinite number of times. It is important to say here that the coin has no memory; it isn't trying to catch up. The same logic applies for any point, not just the origin. So we can also say with certainty that eventually the heads will be winning with a billion head lead, or even an infinite lead but it will always return to being equal eventually.

This is an important idea in probability and you will study random walks in your introduction to probability course if you do maths at university. Let's go on to the two dimensional case. You are standing at the origin and this time you can step North, East, South or West, each with a probability of ¼. Either two coin flips in turn, or rolling a tetrahedral die (a D4) will simulate this well. Imagining this as taking place on the cartesian grid is probably the easiest way to go.

You can imagine this as two versions of the 1d case happening at the same time. The surprising thing is that you will still always return to the origin (and get to every other point) eventually. I.e. you will get to the zero point of both 1d scales at the same point eventually. This means that if you are an immortal on the surface of a planet then you would eventually get back home by moving in random directions: it is impossible to get lost forever. Note that the surface of a planet can be mapped (quite literally with a map) onto a plane.

However in 3d space, which we happen to be embedded into, this neatness all falls apart. It is easy enough to set up the model for this. Roll a normal die (a D6) and travel forwards, backwards, left, right, up or down. Imagine you are an immortal travelling through space (Bowerick Wowbagger…) at random in your spaceship. The probability that you will return to the origin eventually is only 0.340537… So after an eternity of randomly moving your only have a one in three chance of getting home. This means that unlike when you are scuttling about on the face of a planet, you can literally get lost in space.

These numbers for each dimension are called Pólya’s Random Walk Constants and here is a short list of the first few to 5 decimal places:

1d 1

2d 1

3d 0.3405

4d 0.1932

5d 0.1352

6d 0.1047

7d 0.0858

8d 0.0729

 George Pólya

George Pólya

This list does tend to 0 if you are travelling in an infinite number of dimensions and they were derived in 1921. So while our 3d immortal can get home about one third of the time, a timelord travelling through time gets there a fifth of the time (also a Long Earther), and a timelord who travels through to different dimensions as in the Tennant era would get back a seventh of the time.

Right are those enough Science Fiction references for one article?

The German Tank Problem

The German Tank Problem

£e

£e