Random Walk on the Line
Tags: mathematics, python, probabilitythoery, randomwalk
Published: 2024-07-11 22:24:30

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


<div style="">
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ym8vzkcymr9dbq6y75r3.png" 
 width="100px" height="100px" alt="All possible random walk outcomes after 5 flips of a fair coin"/>
</div>

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

### Algorithm implementation

In python this can be written like this

```python
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

```python
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

```python
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

```python
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

```python
# 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`

![Normal distribution graph](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6s7fcvgzlqmo82d7lxux.png) 


“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
https://en.wikipedia.org/wiki/Random_walk