Have you ever gone on a journey and ended up right back where you started?

As it turns out this can happen even when we are dealing with random processes.

Taking a random walk

Imagine you are walking in an unfamiliar place, It’s the middle of the night, pitch black and the ground is muddy; but you’re in no hurry to reach a certain destination.

As you wander about in the dark, each step you take squelches a footprint in the mud. You can’t see anything, so the direction of every step you take is random.

At times you find yourself retracing your steps or walking back though footprints you’ve already made.

After a while you get tired and stop, luckily enough you find yourself not too far from where you started.

The next day, you retrace your steps, recording the co-ordinates of your footprints.

The journey you’ve just been on is known as a random walk.

So what did your journey look like, and why did you end up near where you started?

The journey, not the destination.

You may be wondering, why follow a random walk, isn’t it – well, random?

We could only record the final destination, however we would be ignoring the valuable information gained from following the journey itself.

In our example, each footprint gives us information about a point in time.

By looking at the entire journey, we can see where we’ve spent our time and how far we’ve wandered away from the starting point.

Ultimately, tracing the entire journey gives us a sequence of observations.

To illustrate, imagine we plot the location of each footprint:

set.seed(21) 

# number of steps
n_steps <- 100

# starting position
x <- 0
y <- 0

# record your footprints
x_positions <- x
y_positions <- y

# start the random walk
for (i in 1:n_steps) {
  
  # randomly choose a direction in 2D space
  direction <- sample(
    c("left", "right", "up", "down"),
    size = 1
  )
  
  # take the step
  if (direction == "left") {
    x <- x - 1
  } else if (direction == "right") {
    x <- x + 1
  } else if (direction == "up") {
    y <- y + 1
  } else {
    y <- y - 1
  }
  
  # leave a footprint
  x_positions <- c(x_positions, x)
  y_positions <- c(y_positions, y)
}

# plot your journey
plot(
  x_positions,
  y_positions,
  type = "l",
  xlab = "X",
  ylab = "Y",
  main = ""
)

# highlight starting point
points(
  x_positions[1],
  y_positions[1],
  pch = 19,
  col = "blue"
)

# highlight end point
points(
  x_positions[length(x_positions)],
  y_positions[length(y_positions)],
  pch = 19,
  col = "orange"
)

# plot legend
legend(
  "topright",
  legend = c("Start", "End"),
  col = c("blue", "orange"),
  pch = 19
)

Below we can see that the journey was not a straight forward one and despite taking 100 randomly chosen steps you’ve ended up surprisingly close to your starting point!

Say you take another walk, in the same landscape the following night.

Once again, at every step you randomly choose between moving right, left, up or down.

So what does the journey look like this time? (nb. set the seed to 80!)

Looking at the pattern of your footsteps, you see a very different journey.

You’ve travelled further from your starting position and your final destination is also further away.

This illustrates something important: individual journeys are unpredictable.

So why are random walks useful?

If individual journeys are unpredictable, you could ask why use random walks at all?

As one journey gives us only one possible outcome, this provides limited information.

However, if we repeat the same random process thousands of times we start to see patterns.

Imagine we send out thousands more people on the muddy night walk.

They start in the same location and again randomly choose the direction of each step they take.

Each person takes a unique journey in the dark, leaving a trail of footprints behind them.

In the daylight it becomes clear where the wanderers have travelled and importantly, where they collectively spent the most time.

The pattern describes where the wanderers tend to be, In other words, the distribution emerges from the pattern of our samples.

We’ll look into this some more in the next post on MCMC!

.