In mathematics, a random walk is a mathematical object, known as a stochastic or random process, that describes a path that consists of a succession of random steps on some mathematical space such as the integers.
An elementary example of a random walk is the random walk on the integer number line, Z, which starts at 0 and each step moves +1 or −1 with equal probability. Other examples include the path traced by a molecule as it travels in a liquid or a gas (see Brownian motion), the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler: all can be approximated by random walk models, even though they may not be truly random in reality.
As illustrated by those examples, random walks have applications to engineering and many scientific fields including ecology, psychology, computer science, physics, chemistry, biology, economics, and sociology. Random walks explain the observed behaviours of many processes in these fields and thus serve as a fundamental model for the recorded stochastic activity. As a more mathematical application, the value of π can be approximated by the use of a random walk in an agent-based modelling environment. The term random walk was first introduced by Karl Pearson in 1905.
In the simplest context, the walk is in discrete time, that is a sequence of random variables (Xt) = (X1, X2, …) indexed by the natural numbers. However, it is also possible to define random walks which take their steps at random times, and in that case, the position Xt has to be defined for all times t ∈ [0,+∞).
A random walk is a process by which randomly-moving objects wander away from where they started. The video below shows 7 black dots that start in one place randomly walking away.
How can we describe this mathematically?
The simplest random walk to understand is a 1-dimensional walk. Suppose that the black dot below is sitting on a number line. The black dot starts in the centre.
Then, it takes a step, either forward or backwards, with equal probability. It keeps taking steps either forward or backwards each time. Let’s call the 1st step a1, the second step a2, the third step a3 and so on. Each “a” is either equal to +1 (if the step is forward) or -1 (if the step is backward). The picture below shows a black dot that has taken 5 steps and ended up at -1 on the number line.
Suppose we put the black dot at 0 and then let it take N steps (where N is any number). Now we want to know how far the black dot travels after it has taken N steps. Of course, the distance travelled after N steps will vary each time we repeat the experiment, so what we want to know is, if we repeat the experiment many many times, how far the black dot will have travelled on average. Let’s call the distance that the black dot has travelled “d”. Keep in mind that d can either be positive or negative, depending on whether the black dot ends up to the right or left of 0. We know that for anyone time that we repeat the experiment,
d = a1 + a2 + a3 + … + aN
Now we use the notation <d> to mean “the average of d if we repeated the experiments many times”:
<d> = <(a1 + a2 + a3 + … + aN)> = <a1> + <a2> + <a3> + … + <aN>
But <a1>=0, because if we repeated the experiment many many times, and a1 has an equal probability of being -1 or +1, we expect the average of a1 to be 0. So then,
<d> = <a1> + <a2> + <a3> + … + <aN> = 0 + 0 + 0 + … + 0 = 0
This isn’t too surprising if you think about it. After all, <d> is the average location of the black dot after N steps, and since the dot is equally likely to move forward or backwards, we expect d to be 0, on average.
Well, that was useless!
That exercise didn’t tell us anything about how far the black dot gets after N steps! We are going to have to be a little more clever if we want to find out any kind of useful information.
Here’s an idea… Even though d can be positive or negative, d2 is always positive, so it can’t average out to 0. What if we found the average value of d2?
<d2> = <(a1 + a2 + a3 + … + aN)2> = <(a1 + a2 + a3 + … + aN) (a1 + a2 + a3 + … + aN)>
= (<a12> + <a22> + <a32> + … + <aN2>) + 2 (<a1a2> + <a1a3> + … <a1aN> + <a2a3> + … <a2aN> + …)
First let’s think about what <a12> is equal to. Well a1 can either be +1 or -1. Either way, a12 =1. Then on average a12 is 1 and <a12> = 1. The same applies to <a22>, <a32>, and all the way up to <aN2>.
Now let’s think about what <a1a2> is equal to. There are 4 possible combinations of a1 and a2, each with equal probability:
Since a1a2 is equally likely to be +1 or -1, <a1a2> = 0. The same is true of all of <a1a3>, <a1aN>, <a2a3>, <a2aN> and all of the other terms containing two different steps. Then:
<d2> = (<a12> + <a22> + <a32> + … + <aN2>) + 2 (<a1a2> + <a1a3> + … <a1aN> + <a2a3> + … <a2aN> + …)
= (1 + 1 + 1 + … +1) + 2 (0 + 0 + … + 0 + 0 + …) = N
Now we’re getting somewhere! The average of the square of the distance is equal to N. If we take the square root of this equation, we realize that: sqrt(<d2>)=sqrt(N)
Since sqrt(<d2>) is something like the average positive distance away from 0 after N steps (technically, it’s called the “root-mean-squared” distance), we expect that after N steps, the black dot will be roughly sqrt(N) steps away from where it started. So for 25 steps, we expect the black dot to have moved roughly 5 total spaces from 0 in either direction. Of course, sometimes it will move more and sometimes fewer total spaces, but 5 is roughly what we might expect.
Random walks in more than one dimension
Of course, the 1-dimensional random walk is easy to understand, but not as commonly found in nature as the 2D and 3D random walk, in which an object is free to move along a 2D plane or a 3D space instead of a 1D line (think of gas particles bouncing around in a room, able to move in 3D). We won’t work out the math here, but it turns out to be governed by the same rule as a 1D random walk — the total distance travelled from where it started is approximately sqrt(N) where N is the number of steps taken.
Above we assumed a dimensionless step size of 1. In real life, step sizes are measured in units of distance and sqrt(<d2>)=<r>sqrt(N), where “r” is the size of a step, measured in units of length, and <r> is the average size of a step if the random steps vary in size (which they typically do in nature).
Now that we know a little more about random walks, let’s take another look at the video we saw before. The video shows the paths of 7 black dots undergoing a random walk in 2D. All of the dots start in the same place and then start to wander around. Notice that the steps they take are not all the same length. By the end of the video, some of the dots ended up above where they started, some below, some to the right, and some to the left. Some don’t end up very far from where they started and others manage to travel quite a distance.
Not all random walks are “random”
So far all of the random walks we have considered allowed an object to move with equal probability in any direction. But not all random walks follow this rule. A biased random walk is a random walk that is biased in one direction, leading to a net drift on average of particles in one specific direction.
There are several ways that a random walk can be biased. Think back to our 1D number line.
- Suppose that instead of an equal probability of moving left to right, there was a higher probability of moving to the right.
- Or, suppose the probabilities of moving to the left or right remained equal, but whenever the dot moved to the right, it moved 2 spaces, and when it moved to the left, it only moved 1 space.
In both of these cases, we would expect a net drift to the right. In other words, the random walk is biased toward the right. The video below shows a biased random walk in 2D
Each black dot has an equal probability of stepping towards the right or the left. But the step size is on average longer if the step is towards the right then if the step is towards the left.
Leave a Reply
Want to join the discussion?Feel free to contribute!