Random Walk on the Line

Konstantinos Dalkafoukis — Thu, 11 Jul 2024 22:24:30 +0000

Random Walk

“In mathematics, a random walk, sometimes known as a drunkard’s walk, is a random process that describes a path that consists of a succession of random steps on some mathematical space.”

"Random walks have applications to engineering and many scientific fields including ecology, psychology, computer science, physics, chemistry, biology, economics, and sociology. The term random walk was first introduced by Karl Pearson in 1905."

One-dimensional classic random walk

“An elementary example of a random walk is the random walk on the integer number line, which starts at 0 and at each step moves +1 or −1 with equal probability.”

For instance, imagine you are on the x axis of integers and you start from position 0.

Flipping a coin, if it’s heads you move +1 and if it’s tails -1.

First iteration: Flip a coin, if it’s heads go to position 1. If it’s tails go to position -1.

Second iteration: Flip again a coin. If the first coin was heads it means that you are in position 1 which means now if it’s heads you go to position 2 and if it’s tails to position 0. If the first coin was tails it means that you are in position -1 if the coin now is heads you go to position 0 and if it’s tails you go to position -2. And so on.

All possible random walk outcomes after 5 flips of a fair coin

Algorithm implementation

In python this can be written like this

import random

def random_walk_on_the_line(steps=100):
    position = 0
    for _ in range(steps):
        if random.uniform(0, 1) < 0.5:
            position -= 1
        else:
            position += 1
    return position

If you run the above function starting from position 0 after x amount of steps you will be able to see where you landed.
But this is not very useful.

Let’s run this function multiple times and try to see which positions occur more often and which not.

This process is called Monte Carlo Simulation

def monte_carlo_simulation(number_of_executions=1000, walk_steps=100):
    results = {}
    for _ in range(number_of_executions):
        result = random_walk_on_the_line(walk_steps)
        if result not in results:
            results[result] = 1
        else:
            results[result] += 1
    return results

The above code runs random walks according to the number of executions, counts the number of occurrences for each position and returns an object of the form

results = {
  ...
  "position -1": "20 times"
  "position 0": "10 times"
  "position 1": "5 times"
  ...
}

The last step is to transform this into something that we can plot and plot it

def prepare_results_for_plotting(dictionary):
    positions = []
    number_of_occurance = []
    for key, value in dictionary.items():
        positions.append(key)
        number_of_occurance.append(value)
    return positions, number_of_occurance

This takes the results object and creates two arrays of the form

positions = [... ,"position - 1", "position 0", "position 1",... ]
number_of_occurance = [ ...,"20 times", "10 times", "5 times",...]

Having the data in the right format for matplotlib we have one final step to visualise the data

import matplotlib.pyplot as plt

def plot_results(dictionary):
    positions, number_of_occurance = prepare_results_for_plotting(dictionary)
    plt.bar(positions, number_of_occurance)
    plt.ylabel('number of occurances')
    plt.xlabel('positions')
    plt.show()

Last step is to call the above functions

# 100000 discrete walks, 100 steps for every walk
simulation_results = monte_carlo_simulation(100000, 100)
plot_results(simulation_results)

Putting all together in a python file and running it we approach a normal distribution.
Also make sure you have installed matplotlib

“The central limit theorem and the law of the iterated logarithm describe important aspects of the behaviour of simple random walks on Z. In particular, the former entails that as n increases, the probabilities (proportional to the numbers in each row) approach a normal distribution.”

Final Words

I hope it was helpful.

Thanks for reading.

If you have any questions feel free to ask in the comments.

References