A Random Walk & Monte Carlo Simulation || Python Tutorial || Learn Python Programming

variety is the spice of life and walking is good exercise if you combine these two things you get a random walk as the name suggests and a random walk your direction is chosen at random at each step along the way today we will use Python to solve a random walk puzzle using Monte Carlo simulations this concludes my gamble and will preamble suppose you live in a city where the streets are arranged in a perfect grid you decide to go for a walk at each intersection you choose your next direction randomly your four choices are north south east or west and backtracking is permitted once you are finished with your walk you check to see how far away you are from where you began if you are more than four blocks away you will pay for a transport back home otherwise it will just walk what is the longest random walk you can take so that on average you will end up four blocks or fewer from home we will begin by writing a function to simulate a random walk of n blocks we will write this function twice the first version will be clear simple and straightforward in the second version we will use some Python shortcuts to cut the length of the function in half to begin import the random module we will call our function random walk and the input n will be the number of blocks to walk write a short doc string describing the purpose of this function your position in the grid will have an x and y coordinate initially x equals 0 and y equals 0 we will now take the random walk to do this we will use a for loop with n steps to pick a random step we will use the choice function we will choose from a list of the four possible directions north south east or west if the random step is north then increase the y-coordinate by one if itself decrease the y-coordinate by one if it's East increase the x-coordinate and now the only remaining alternative is West so for the final else block decreased the x-coordinate by one at this point the walk is over so he returned the coordinates as a tuple to test this function let's take 25 random walks each 10 blocks long for each walk we will display the coordinates and the distance from home the distance from home is the sum of the absolute values of the x and y coordinates this is because the sign is for Direction not distance for example suppose you ended up at x equals negative 10 or x equals 10 in both cases you are 10 blocks from home the sign only indicates if you are east or west from your starting position now run everything looks to be in order before solving the puzzle let's write a second version of this function that is more compact we will call this function random walk 2 we will perform our solemn programmers duty and write a docstring as before let's initialize x and y in python this can be done in one line this assigns the first zero to X and the second zero to y once more we will use a for loop to simulate the end blocks previously we randomly chose a letter and then use the letter to update the x and y coordinates this time we will randomly choose a pair of numbers DX and dy which will contain the values we will add or subtract from x and y we use DX and dy as abbreviations for difference in X and difference in Y now we randomly choose a direction if north is chosen the x-coordinate does not change but the y-coordinate increases by one if South is chosen X is again unchanged and Y decreases by one for east x increases by one and Y is unchanged and finally for West we subtract one from X and leave Y unchanged we now use DX and dy to update X&Y X plus equals DX is shorthand for x equals x plus DX we update Y the same way and finally return x + y let's now test this function to see if it behaves as expected like before we will take 25 random walks each walk will be for 10 blocks and we will print the final coordinates along with the distance from home run no errors and no surprises let's now return to the original puzzle what's the longest random walk you can take so that on average you will end up 4 blocks or fewer from home in other words there is less than a 50% chance you'll pay for transport home this can be solved mathematically but instead we will use the Monte Carlo method this technique is named after the city of Monte Carlo a gambling town on the Mediterranean Sea you will never find a more wretched hive of scum and villainy here instead of solving the problem mathematically we will conduct thousands of random trials and compute the percentage of random walks that end in a short walk home to get an accurate number we will take 10,000 random walks for each walk size let's estimate the probability you will walk home for walks of length 1 to 30 blocks don't forget the range function stops before the final number let's create a counter called no transport to keep track of the number of random walks that end for blocks or fewer from home let's now begin our Monte Carlo loop of 10,000 samples first get a random walk of length walkling next compute the distance from home if the distance is less than or equal to for increment the no transport counter we can now compute the percent of random walks that ended with a walk home it's just the fraction of the 10,000 random walks which required no transport and finally print out the results for this walk size run fascinating the longest walk with a greater than 50% chance of walking home is a walk of size 22 blocks let's run this simulation one more time and to increase our confidence let's use 20,000 random walks to estimate the probability there you have it we get the same answer by the way your numbers will be slightly different from these that's because Monte Carlo methods use random samples and different simulations should give slightly different results observe that walks with an even number of blocks leave you closer to home that walks one block shorter in general even walks and closer to home than odd walks I encourage you to discuss and analyze this phenomenon in the comments below random walks are a fascinating subject they are used to model many different problems from the motion of molecules in a fluid to the movements of stock markets as a challenge try to find the longest random walk which will on average leave you less than five blocks from home and as a courtesy please consider subscribing to Socratic ax the more support we have the less random our release schedule [Music]

Channel: Socratica

Views: 556,619

Rating: 4.9302096 out of 5

Keywords: Socratica, SocraticaCS, python, python programming, CSV, CSV Module, random walk, random walks, monte carlo, monte carlo simulation, monte carlo simulations, monte carlo method, socraticapython, how to program in python, programming in python, monte carlo python, montecarlo simulation, learn python, python tutorial, python tutorial for beginners

Id: BfS2H1y6tzQ

Length: 7min 54sec (474 seconds)

Published: Mon Mar 06 2017