Random Walk

“In mathematics, arandom walk, sometimes known as adrunkard’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 thex axis of integers and you start fromposition 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 toposition 1. If it’s tails go toposition -1.

Second iteration: Flip again a coin. If the first coin was heads it means that you are inposition 1 which means now if it’s heads you go toposition 2 and if it’s tails toposition 0. If the first coin was tails it means that you are inposition -1 if the coin now is heads you go toposition 0 and if it’s tails you go toposition -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

importrandomdefrandom_walk_on_the_line(steps=100):position=0for_inrange(steps):ifrandom.uniform(0,1)<0.5:position-=1else:position+=1returnposition

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

defmonte_carlo_simulation(number_of_executions=1000,walk_steps=100):results={}for_inrange(number_of_executions):result=random_walk_on_the_line(walk_steps)ifresultnotinresults:results[result]=1else:results[result]+=1returnresults

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

defprepare_results_for_plotting(dictionary):positions=[]number_of_occurance=[]forkey,valueindictionary.items():positions.append(key)number_of_occurance.append(value)returnpositions,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

importmatplotlib.pyplotaspltdefplot_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 walksimulation_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 installedmatplotlib

“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