Random Walks
The Mathematics in 1 Dimension

What is a random walk?

A random walk is the 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. We will come back to this video when we know a little more about random walks.

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 center.

Then, it takes a step, either forward or backward, with equal probability. It keeps taking steps either forward or backward each time. Let's call the 1st step a₁, the second step a₂, the third step a₃ 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 traveled 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 traveled on average. Let's call the distance that the black dot has traveled "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 any one time that we repeat the experiment,

d = a₁ + a₂ + a₃ + ... + a_N

Now we use the notation <d> to mean "the average of d if we repeated the experiments many times":

<d> = <(a₁ + a₂ + a₃ + ... + a_N)> = <a₁> + <a₂> + <a₃> + ... + <a_N>

But <a₁>=0, because if we repeated the experiment many many times, and a₁ has an equal probability of being -1 or +1, we expect the average of a₁ to be 0. So then,

<d> = <a₁> + <a₂> + <a₃> + ... + <a_N> = 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, d² is always positive, so it can't average out to 0. What if we found the average value of d²?

<d²> = <(a₁ + a₂ + a₃ + ... + a_N)²> = <(a₁ + a₂ + a₃ + ... + a_N) (a₁ + a₂ + a₃ + ... + a_N)>

= (<a₁²> + <a₂²> + <a₃²> + ... + <a_N²>) + 2 (<a₁a₂> + <a₁a₃> + ... <a₁a_N> + <a₂a₃> + ... <a₂a_N> + ...)

First let's think about what <a₁²> is equal to. Well a₁ can either be +1 or -1. Either way, a₁² =1. Then on average a₁² is 1 and <a₁²> = 1. The same applies to <a₂²>, <a₃²>, and all the way up to <a_N²>.

Now let's think about what <a₁a₂> is equal to. There are 4 possible combinations of a₁ and a₂, each with equal probability:

Since a₁a₂ is equally likely to be +1 or -1, <a₁a₂> = 0. The same is true of all of <a₁a₃>, <a₁a_N>, <a₂a₃>, <a₂a_N> and all of the other terms containing two different steps. Then:

<d²> = (<a₁²> + <a₂²> + <a₃²> + ... + <a_N²>) + 2 (<a₁a₂> + <a₁a₃> + ... <a₁a_N> + <a₂a₃> + ... <a₂a_N> + ...)

= (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(<d²>)=sqrt(N)

Since sqrt(<d²>) 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.