The mathematics behind a drunkard’s walk
Random walk is an important concept of probability and mathematical finance — but what exactly is it and why should I care?
What is a random walk?
Random walks fall under probability theory — arguably the most amazing branch of mathematics — that amongst other things, focuses on random processes in a rigorous manner and draws conclusions on their behaviour.
The mathematically strict definition of a random walk is as follows:
Let’s go through a few examples to understand this definition better.
A simple walk
Let’s start with a simple random walk in 1 dimension. Imagine a drunk person on their way home from the pub, already at half-way — stopping every minute and making a decision: carry on going towards their home or return to the pub for another drink. With the assumptions, that the drunkard is moving with constant speed, the decisions are made with 50% probability and independently from each other and that there is a straight street from the pub to their home, we can formulate the following model:
Let (Xn) be -1 or +1 independent and identically distributed random variables, with probability p=0.5, then the drunkard’s distance from halfway after n minutes is:
A random variable Xᵢ in this case would correspond to the choice made at time i: +1 if the drunkard decides to move towards home and -1 if towards the pub (the random variable is the mapping between the choice and the values). All X’s have the same distribution (1 with probability 0.5, and -1 with probability 0.5) and are independent of each other. Therefore, the position from the start will be the sum of n decisions made.
How does that look though? Now, assuming the drunkard starts at 0, home is at 50 and the pub is at -50, we get the following:
This shows us how undecisive our walker is — this is due to the probability p being 0.5 and the decisions being independent of each other (i.e. no previous decisions influence the outcome of the following one). What can we say about this random walk in general? An important piece of information of Sn is its expected value — this will give us information about the expected location of the drunkard after n steps.
The second equality holds due to our random variables being independent. The expected value of any Xᵢ (since they have the same distribution) is:
Therefore the expected distance from halfway is:
Which explains the indecisive behaviour of the walker.
Looking back on our definition from earlier — the random walk here describes the path of our drunkard and consists of random steps, that are the decisions our walker makes after one another.
Adding bias to the model
Now let’s introduce a new concept, the “bias” — this usually means an inclination towards something. In our case it will mean the drunkard is more inclined to go back to the pub. In mathematical terms, we can easily model that by changing p to — say — 0.3, i.e. only 30% of the times will the drunkard start going towards their home.
The effect is clear — the position of the walker shifts in the negative direction as the number of steps increases. Let’s take a look at how the bias has changed the expected value of the position:
Now that the expected value of each step is non-zero, the expected position after n-steps is:
So after n=100 steps the expected position is -40.
More complex walks
Of course random walks don’t stop here. Expansions of the concept include higher dimensions (e.g. 2D on a square lattice ~ random walker on the Manhattan street map), or other graphs (even random environments, such as percolations — these are networks where nodes or edges are removed), as well as self-interacting random walks (e.g. self-avoiding walks, that don’t visit the same point twice) and correlating random walks.
How do random walks help us understand the world?
Now that we’ve achieved a considerable level of abstraction from our starting point (getting home from the pub), let’s go through why random walks are important for us — other than the obvious beauty of these processes.
What would you do if you had a chance to peak into the future one week from now? Maybe check the lottery results? Or the stock and commodity prices?
It has been a key interest of traders to have knowledge of the future, since Thales, the Greek mathematician who is believed to have bought the first options to speculate on the outcome of the olive harvest. Knowledge of the future price ensures, that we can buy below and sell above the real value of the asset.
Whilst the Holy Grail of looking into the future isn’t at our disposal, random walks are, and as it turns out they are almost as good. The strength of the concept is that regardless of it being random, with reasonable assumptions, we can deduce general facts about its behaviour, which makes it a perfect candidate to model future scenarios with a probabilistic approach.
However, this requires extremely advanced mathematical tools, many of which we weren’t in the possession of until recently. The first step was the Wiener process (named after Norbert Wiener, but sometimes also referred to as Brownian Motion), which is the scaling limit of a random walk in 1 dimension — this means that if the unit of time between decisions of the walker is tending to zero, then our random walk approaches the true Wiener process (imagine the drunkard making decisions every moment). With this in hand, it was Kiyosi Itô in the 1940s, who made the next step by extending the usual methods of calculus to stochastics processes, therefore creating the theory of Itô Calculus (also called Stochastic calculus). This enabled Black, Scholes and Merton to create their option-pricing model in 1970 for which they were awarded the Nobel-prize in Economics. This model allowed traders to model option-prices a lot more accurately than ever before — almost as if looking into the future.
Financial Mathematics emerged from this breakthrough. It has since developed into a discipline on its own right, but the best pricing models currently driving our markets still use the fundamentals that Norbert Wiener and Kiyoshi Itô laid down.
Other applications
The original notion of the Brownian Motion comes from Scottish botanist Robert Brown, who observed the seemingly random movement of pollen in water through a microscope. The concept since expanded onto the random motion of particles (rather than pollen) in a fluid. Similarly to pollens, one of the hottest topics of physics is also utilising random walks: Quantum Field Theory. Mathematical ecology is using it to model population dynamics, biodiffusion and animal movements. Further applications include network theory (both physical networks and social networks, such as estimating the size of the web), chemistry and material science, but the list is endless.
Hopefully the above gives a good overview of this cornerstone of modern science, and sheds light on how random walks bring some certainty into our world.
If you would like to read more, I recommend this article on the Black-Scholes model and stay tuned for more content on random graphs.
