What are random walks? (Tipsy tottering, sunlight and the smell of coffee: it’s all random)

A shorter version of this post was published on The Conversation on 19th December 2013.

His walk home might comprise random steps, but mathematics says he’ll find his way eventually. (David Blackwell)

His walk home might comprise random steps, but mathematics says he’ll find his way eventually. (David Blackwell)

The sun as captured by NASA's SDO mission - each particle of sunlight has undergone a remarkable journey. (http://sdo.gsfc.nasa.gov/gallery/main/item/184)

The sun as captured by NASA’s SDO mission – each particle of sunlight has undergone a remarkable journey. (http://sdo.gsfc.nasa.gov/gallery/main/item/184)

“So much of life, it seems to me, is determined by pure randomness” – Sidney Poitier

The warmth of sunlight on your face, the view from your backyard – such delights are delivered to you by countless pieces of sunlight that you constantly absorb. Each such photon of sunlight has come to the end of an incredible journey. Its journey began with a violent birth in the nuclear fires of the sun’s core, which was followed by a long migration to the solar surface and a final leap across the 150 million kilometre void of space to reach the Earth (and you).

Still more remarkable is the time required for such a journey. Travelling at the fastest speed known to physics, the photon crossed from the sun to the Earth in a mere 9 minutes. In contrast, the first 0.05% of the journey – just from the sun’s core up to its surface – lasted almost 10 thousand million times as long, taking an average of 170 000 years to complete.

Such a discrepancy arises due to the fact that, unlike the freedom of (almost) empty space, the interior of the sun is a crowded place indeed. Even travelling at the speed of light, a photon can only cross about a millimetre of space before bumping into one of the sun’s atoms, where it is absorbed and then ejected again after a moment’s delay. The photon’s struggle toward the surface proceeds in fits and starts as it is absorbed by atom after atom and spat out in a random direction each time, drifting along an aimless path until it finally manages to burst free of the sun.
Perhaps the most remarkable thing about this extraordinary journey is how much we know about it – our ability to even calculate the average time that this ‘random walk’ takes to reach the solar surface, even though the photon’s path is… well, random. The modern mathematical theory of random walks allows us to grapple with the fundamental aspects of random physical processes – and to extract predictable behaviours out of such random tangles.

Discrete random walks

“Creativity is the ability to introduce order into the randomness of nature” – Eric Hoffer
The meanderings of photons are just one of the many ways that random motion manifests in the world around us. The simplest type of random motion is a discrete one-dimensional random walk, in which the walker only moves back and forth along one particular direction (and takes the same sized step every time). For instance, we might position ourselves at a starting point (the origin) and take one hundred steps, using a coin flip at each step to determine our next move. If the coin comes up heads, we’ll move one metre to the north; if tails, one metre south. If we keep track of our progress and repeat the exercise eight different times, we might end up with the eight random walks shown below:
A sequence of 8 discrete one-dimensional random walks (Wikimedia commons)

A sequence of 8 discrete one-dimensional random walks (Wikimedia commons)

It’s tempting to think that we ought to hover around our starting point, since at every step we’re just as likely to move north as we are south. However, most of the random walks above have actually drifted a little bit away from the origin. In these cases, would we keep on drifting if we went further still? Or would we eventually return to the origin?

Analysing the mathematics (by applying the central limit theorem) tells us that for walks like these, the probability of being at a particular spot after a certain number of steps closely follows the normal distribution. In fact, if we look at the 100th row of Pascal’s Triangle we see an orderly row of 100 different numbers, each of which corresponds to one of the locations we could have ended our walk on, and each of which tells us how many different random walks (of 100 steps) we could have taken to end up at that particular spot. So studying Pascal’s triangle shows us exactly how likely we are to end up at a particular location –  the bigger the number in that spot, the more likely it is that your random walk will lead you there.
The mathematics of random walks also throws up an interesting insight known as the level-crossing phenomena – if allowed to go on forever, a simple random walk like this will cross every point (including the origin) infinitely many times. So yes, we are guaranteed to return to our starting point – eventually. The level-crossing phenomenon is also known as the gambler’s ruin, since if our random walk represents the bank balance of a gambler who is playing against a house with unlimited funds, the gambler’s balance is guaranteed to cross zero eventually – after which the game has ended, and the gambler has lost.
As well as being central to models of stock prices, one dimensional random walks are also familiar to tennis fans. Whenever a score of deuce (40-40) occurs, one of the players is required to score two consecutive points before the game is awarded. Thus we enter a situation similar to a random walk, where the advantage moves back and forth between the players until it manages to get two steps away from the starting point of deuce.

Non-discreet drunken walks

“A drunk man will find his way home, but a drunk bird may get lost forever.” – Shizuo Kakutani

Two-dimensional random walks are often illustrated by considering the walk of a tipsy pub patron on their way home. Perhaps they are more than a little tipsy; they might take two steps forward and then abruptly lurch to the right, before stepping backwards, then left, then stumbling onwards in a discrete two-dimensional random walk (the steps are still the same size, but now the walker can move randomly on a two-dimensional grid). Not only do they capture the wanderings of over-indulgent partygoers, random walks such as these (and their higher-dimensional counterparts) are the basis on which nearly all random activity is modelled – from the wanderings of foraging animals to the twists and turns of chemical polymers.
A discrete two-dimensional random walk (Wikimedia commons)

A discrete two-dimensional random walk (Wikimedia commons)

The history of random walks itself wanders across a wide range of subjects. The first use of the term ‘random walk’ can be traced back to 1905, when the English mathematician Karl Pearson wrote a letter to Nature asking for assistance with determining the probability of finding a random walker at a specific place after a certain number of steps. Pearson went on to use random walks to develop mathematical models of mosquito infestation. His letter was answered by the Nobel-winning physicist Lord Rayleigh, who had already analysed a more general version of Pearson’s problem – in a model of sound waves travelling though uniform materials.
Seperately, the foundations for a coherent mathematical theory of random walks had just been laid in a PhD thesis. In 1900, the French mathematician Louis Bachelier was investigating random walks for yet another reason – he wanted to analyse the behaviour of stock markets and found that random walks with tiny step sizes were ripe for the purpose. In terms of theoretical finance, Bachelier was about six decades ahead of his time.
Bachelier was also the first to notice a striking property of random walks, known as the Markov property: if you want to predict the future behaviour of the random walker, you only need know where they are right now. Knowing where they have been in the past adds no helpful insight whatsoever!
Modern random walk theory, though still being built up by the current generation of mathematicians, allows us predict a great many properties of random walk paths accurately – even if we cannot know the details of the otherwise random walks in advance (a situation that is echoed in Chaos Theory). For instance, after a certain amount of time has elapsed, we can calculate both the expected distance away from the starting point that the walker will be and the number of different spots the walker will have visited. We can also compute the probability that the walker will eventually return to their starting point after a long enough time. For a festive friend walking on a two-dimensional surface, mathematics is on their side – they are almost certainly guaranteed to return to their starting point (if you wait long enough). On the other hand, for three-dimensional random walks – like those taken by inebriated birds, or solar photons – there is only about a one-in-three chance of returning to the point of origin. Thus do photons eventually, inevitably, drift free of the sun after a predictable period of time.

Continuous random walks

“…agreement of the Brownian movement with the requirements of the kinetic hypothesis… justify the most cautious scientist in now speaking of the experimental proof of the atomic nature of matter” – Wilhelm Ostwald, 1909
As the Roman philosopher Lucretius observed around 60 BCE, beams of sunlight can also shed light on an unexpected (and ubiquitous) natural phenomenon – the jittery motions of tiny particles:
“Observe what happens when sunbeams are admitted into a building and shed light on its shadowy places. You will see a multitude of tiny particles mingling in a multitude of ways… their dancing is an actual indication of underlying movements of matter that are hidden from our sight.”
At the turn of the 20th century the greatest minds in physicists had also turned their attention to this dance of the tiny particles. This physical phenomena was dubbed Brownian motion, and the explanation of its origins would provide the first definitive proof for the existence of atoms.
The namesake of Brownian motion was the Scottish botanist Robert Brown, who in 1827 was examining grains of pollen suspended in water under a microscope. The microscopic pieces of pollen threw off some still tinier bits, and their jittery motion caught Brown’s eye. At first thinking that the movement may have some biological origin, the mystery only grew deeper after Brown tested and eliminated this possibility by observing the same mysterious motion in similarly small particles of inorganic material.
The mystery was finally cracked by none other than Albert Einstein during his Annus Mirabilis (miracle year) of 1905.  Einstein provided a detailed explanation for why Brownian motion occurred – the particles were so small that they were actually being buffeted to-and-fro by collisions with surrounding atoms and molecules, like a miniature plane in a never-ending storm of molecular turbulence.
Brownian motion in action - a dust particle (yellow) jiggles as it is struck seemingly at random by surrounding gas molecules (black) in a computer simulation(image from http://en.wikipedia.org/wiki/File:Brownian_motion_large.gif)

A small dust particle (yellow) jitters as it is struck seemingly at random by surrounding gas molecules (black) in a computer simulation (Wikimedia commons)

By modelling Brownian motion as a random walk with tiny, random step sizes, driven by molecular collisions, Einstein provided the mathematics that enabled the very first estimates of the size of individual molecules. Einstein’s equations were experimentally verified by Jean Perrin four years later, finally providing the first conclusive proof for the long-suspected existence of atoms.

Beyond watery pollen, Brownian motion arises in a wide range of circumstances. Perhaps the most widespread is the phenomena of diffusion. Any time you open a perfume bottle, a fresh bag of coffee or any other aromatic container, the pleasant scent that you experience is due to the fragrant molecules being carried all the way from the container to your nose through Brownian-like collisions with the gas molecules in the atmosphere.

In 1923, the American mathematician Norbert Wiener devised a general type of random process, known as a Wiener process, of which Brownian motion is but one specific case. Wiener showed that the paths followed in such processes were both continuous everywhere and differentiable nowhere – in fact, the paths were fractal in nature. And to tie everything together, it became apparent that, when the step sizes were made ever smaller, the majority of discrete random walks became Wiener processes – hence explaining the ubiquity of Brownian motion in nature.

Walking on π (and other nifty numbers)

“If you are seeking creative ideas, go out walking.” – Raymond Inmon

The mathematics of random walks has recently found a new and very novel application in the analysis of walks taken on numbers, as first described in a 2013 paper by Francisco J. Aragón Artacho, David H. Bailey, Jonathan M. Borwein and Peter B. Borwein (a collection of related publications can be viewed here).

To take a two-dimensional walk on a particular number, we use the same ideas as for discrete two-dimension random walks – except, rather than choosing the step directions at random, we use the digits in the number’s decimal expansion as a set of instructions on where to go next.

A number like 1/3, which has decimal expansion 0.333333… is not particularly interesting – the walk will keep going in the same direction forever. A walk on the famous circle constant π, whose digits begin 3.141592… is far more fascinating. In the original Aragón, Bailey, Borwein and Borwein paper, the following walk is taken on the first 100 billion digits of π:

A walk on the first 100 billion digits of pi (in base 4). The walk starts in red at the origin, and the colours move up the rainbow as the walk progresses (http://walks.carma.newcastle.edu.au/walks.html)

A walk on the first 100 billion digits of pi (in base 4). The walk starts in red at the origin, and the colours move up the rainbow as the walk progresses (http://walks.carma.newcastle.edu.au/walks.html – see also http://gigapan.com/gigapans/106803 for a fully interactive version)

As you can see, this long walk on π bears a striking similarity to a random walk. This is almost certainly not a coincidence – in fact, new pictures such as these may help us resolve a long-standing mathematical question regarding the ‘randomness’ of the digits of π.

Since the ancient Greeks, humanity has been fascinated by the digits of π. In 1761, the Swiss mathematician Johann Lambert proved what had been suspected many centuries prior – that π was an irrational number. That is to say, it cannot be written as a fraction and so its digits go on and on forever without any repeating pattern. Today, another question with a long-suspected but unresolved answer remains regarding whether or not π is a ‘normal number‘ – do the digits 0-9 show up equally often in the decimal expansion of π, or do you eventually reach a point where you’re swamped by 7s (for instance)? That is, do the digits of π behave in a ‘random manner’?

Although we don’t have any proof that the digits of π are behaving randomly, the walks on π are certainly suggestive – and in fact, recent computations have pegged the probability that π is normal (in base 16) at over 99.999… (with more than 3000 other 9s) percent!

Any time random motion is present – be it drifting molecules, fluctuating stock prices or escaping sunlight – the mathematics of random walk theory allows us to extract predictable features from the otherwise unpredictable. And at the current frontiers of mathematical research, it is literally allowing us to see familiar numbers in a whole new light.