[Music] hey everyone welcome back so in this video we're going to be talking about a very cool concept in data science and one that gets used a lot called the monte carlo method you know i like to keep it really practical on this channel so we're going to go through two real examples and then we'll finish by talking about the advantages and also most importantly the disadvantages of using a monte carlo method to solve your problem versus some other way to solve your problem so let's jump right into the first example so this is kind of a toy example we are throwing darts into this square whose sides have length two so you throw a dart and it's guaranteed to be somewhere in the square but it is random where it's going to be you're just throwing a dart randomly and you can see there's also a circle inside of the square the circle has radius one and the natural question of course is if i throw a dart into the square what's the probability that the dart is in the circle i think most of us after we've taken a geometry and probability course it's pretty natural how to answer this question because the probability of throwing it in the circle is just proportional to the area of the circle so if we divide the area of the circle by the area of the square we should get our answer and what would that be the area of the circle is pi r squared or pi 1 squared which is just pi and divide that by the area of the square which is 2 times 2 which is 4. so our answer is pi divided by 4. okay so pi over 4 is the answer now let's consider a different way to solve this problem that doesn't take into account that we know anything about geometry at all we're going to solve this purely in a simulation based way and i've written the pseudo code for that down here in green now let's go through the code because i want to make sure to understand the code for both this one and the next one so that we understand how you would actually write the code for a monte carlo simulation monte carlo method so we're going to set big n equal to 1 million this is going to be the number of points that we are going to sample from the square and each point is going to represent a simulated dart throw we're going to set this variable circ equal to zero this is going to be a running total of how many of those darts or how many of the sampled points also live inside the circle and you can see that after we're done after we do this simulation we're simply going to divide circ by n because that's going to give us the fraction of points the fraction of darts that i randomly threw that end up in the circle which is exactly what we want that's exactly the probability that we're after it's just that we solved it geometrically very naturally before but now we're going to solve it purely in terms of simulation i think this is a very intuitive thing for a lot of people maybe this is even the first thing you thought of to solve the problem let's just look at the pseudo code really quickly so we're going to say for i in 1 to n again we're doing a million samples and this is important because the more samples we do the closer we are going to get to the truth which is pi over 4.
if we only took 10 samples we're probably not going to get that close 100 samples is better but maybe not enough doing a million samples should be sufficient but of course we also know that more samples means more runtime more on that later so we're going to say for i and 1 to n we're going to sample the x and y coordinate from negative 1 to 1. so x and y are both independently going to be numbers that are sampled from between negative 1 and 1 uniformly y between negative 1 and 1 so i arbitrarily just define a coordinate system where the center of this diagram is the origin and so if you kind of extrapolate from there then the left hand side of the square is at negative one the right hand side of the square is a positive one and same thing for the y direction so sampling x and y from negative 1 to 1 is going to exactly uniformly sample within the square now the final question is does the point that i just uniformly sampled for a certain iteration of this for loop also live inside the circle and we know that something lives in a circle if it's x squared plus y squared is less than or equal to the radius of the circle the radius of the circle here is one so we simply need to check the condition that if x squared plus y squared is less than or equal to one that means it lives in the circle then circ plus equals one circus again the running total of the number of darts we throw that live inside the circle so go ahead and pause go over the explanation again or write it down convince for yourself or even code it if you want and you'll see that at the end of the day circ is the number of points that we simulated that live in the circle n is the total number of points that we simulated so this division here makes a lot of sense and now i actually coded this myself and i'm going to throw the answer up on the screen here for the estimate i got from the simulation and you can see it's extremely close to the true value and it doesn't take too long to compute even for 1 million samples so this is a good way to solve the problem if we truly had no idea how to solve it any other way so we'll have a little bit more to say about this when we talk about the pros and cons but let's move on to the next example because i think this one better highlights why we would choose to use a monte carlo method because this problem wasn't too hard so it is difficult to justify writing code for it but let's look at a harder problem where if we just don't know what to do we can still get a really close answer using monte carlo method so example number two says that i play a game where the probability of winning a round so probability of win is equal to little p for each round so for any given round of the game the probability that i win that round is p now this game ends when i lose two times in a row so for example if i play the first round and i win second round i lose and the third round i lose the game is over and i've played three total rounds the question is if this is how the game works what is the expected number of rounds that i'm going to play another way to say that is on average how many rounds of this game do i play until it's over until i get those two losses in a row now before i go on i mean you can even think for yourself how would i solve this problem what tools would i use what formula would i write how would i think about it and before we get to the solution here i think the natural way to solve it and the way i first you know kind of started writing equations down was okay we know an expected value is simply one times the probability that i play one round plus two times the probability that i play only two rounds plus three times the probability i play three rounds and on and on so maybe if i add up all these numbers in this kind of infinite sum i'll see some kind of pattern and i can get it into a nice closed form now i indeed tried that but it was a little bit difficult the math got a little bit out of hand maybe you'll have better luck with it but then you know a little while later i had this new idea and i want to emphasize that even though i'm sharing this as a very simple looking solution it took me a really long time to arrive at it it took me a long time to think about it and even when i did think about it it takes some time to work through all the algebra here so do keep in mind that there is a big time cost to solving this problem in a purely kind of algebraic theoretical way but let's look at the solution that i came up with and see why it works so we're going to let little e be the expected number of rounds that you're going to play that is the quantity that we're after of course now it turns out that you can break this up into three very simple cases the first case where you win the first round so let's say you just start playing the game and you win the first round now that's as if the game started from scratch because that is basically saying that now whatever comes after i haven't had any losses yet so i'm basically starting the game from scratch it's as if nothing happened and that event where i win the first round happens with probability p by definition and what is the expected number of rounds that i play in that case well it's going to be 1 because i did take that first round which i won plus e so it's kind of kind of difficult to understand this i would say it's not super easy but i'm defining this quantity e in a recursive way where you see e on the left hand side and you see it show up in the right hand side of the equation as well but again the first part of the sum is saying there's probability p that i win the first round in that case it's like the game starts from scratch so the expected number of rounds in that situation would be one plus e e because i'm starting the game from scratch now let's look at the two other cases another case is if i get loss loss so i begin the game i get a loss i unfortunately get another loss and the game is over this is the easiest of the three cases to understand the probability of this is one minus p times one minus p again by definition and what is the expected number of rounds well it could only be two because once i've gotten those two losses it's over so i put two here and the final case would be if i get a loss first and then i get a win that happens with probability one minus p times p so that again is getting a loss followed by getting a win and what's the expected number of rounds i play in that situation well i've already played two rounds to get the loss and the win so that's two and then to that i add little e little e again because i'm starting from scratch i got a win on the second round so it's like i'm starting everything from scratch now if you do all the algebra you can solve for e it's not too difficult you'll get the closed form solution that little e is equal to two minus p divided by one minus p squared now i wanna be really clear here this math here if you didn't follow it it's okay the main point i wanted to get across is that it took me a while to explain this to you it took me a while to work out the algebra and it took me a long time to even arrive at the fact that this could be the solution to the problem now what if instead of doing all that what if instead of thinking about it at all we just coded it we took advantage of the high computing power we have nowadays and we just took these rules that we were given in blue and coded up a solution and then estimated the solution that way so i want to explain the code to you again this is pseudo code but it wouldn't be too hard for you to write this yourself so i'm going to initialize the rounds to be empty this is going to store the number of rounds that i play on various simulations for i in 1 to 1 million so i'm again doing 1 million trials 1 million simulations of this game and on each simulation i'm going to see how many rounds i got i got to play so what do i do inside the for loop i set r equals zero r is going to be the number of rounds i played on this simulation so currently it's zero nothing and n loss is going to be zero this is the number of losses that i have gotten in a row so far now we have an inner while loop here so while the number of losses is not equal to 2 again that's straight from the definition of the problem while i have not hit two losses in a row r plus equals one so this says that update the number of rounds i've played by one so this just keeps going as long as i don't have two losses in a row then i'm going to simulate a random number between zero and one and then i'm going to check if this random number is less than p p again is the probability of winning a round so for example if p was equal to one half and this random number that i chose in this step is less than one half then we would say that i won the round and therefore we reset and loss to be zero because when you win a round of this game the number of losses you have in a row by definition is now zero however else which means that we did not win that round then we would update and loss to be plus equals one that means that i do have one extra loss in a row and we just keep going and eventually n loss is going to be equal to two because i got two losses in a row i do rounds dot append r so again rounds is a big list that throughout this whole simulation it's collecting the number of rounds that i played in each game so we append this little r to rounds and at the very end of the day at the very end of this for loop after i've done my million simulations of this game i return the average of rounds so the bar you see on top is an average and that's exactly what i want what is the expected number of rounds that i play in this game if these are the rules of the game so let's take a look at the results of this monte carlo method if p is equal to one half which is the probability of winning then the true is going to be six computed straight from this analytical formula we derived and i've showed the results of the monte carlo simulation here so we see we get extremely close to the truths but do notice that it took me about 10 seconds to get there so it wasn't super fast 10 seconds is not a long time you can sit there it goes by in a flash but notice that it took quite a bit longer to do a million rounds of this monte carlo simulation than this much easier monte carlo simulation and we'll touch on that point again in a moment okay so this was our second example and the big takeaway i want you to get from this is not you know this example at all this is not a probability solving video this is a video which is trying to show you that some problems can require a lot of thinking clever problem solving kind of bashing your head on the paper for a while can't get the answer but if all you're after is that number all you're after is the expected number of rounds for some given value of p then you might as well just code a solution this didn't take too long to write and then you'll get pretty close to that answer and if you want to get even closer just make the number of rounds bigger you can get even closer arbitrarily close as you want if you're willing to wait that long for your process to finish so monte carlo methods can be a very easy way to get the answer to a problem which is otherwise difficult to solve and that's a great segue into talking about what mc is mc is monte carlo what it is and what it is not because so far everything i've told you makes it sound awesome but we like to think about things from every angle on this channel so let's talk about pros and cons now to close the video so as we were saying monte carlo is easy even if you haven't thought of a clever way to solve the problem you can just code it yourself and get the answer to some arbitrary degree of precision and kind of to talk about that more let's say that it's a problem in a subject area that you're not familiar with like genetics or stock trading or something as long as you have the rules of the problem it doesn't really matter if you're a subject matter expert or not you can just code this and get the answer anyways so it helps people who are in maybe not necessarily the same field still arrive at practical results to these problems so that is one of the big pros of monte carlo methods and this easy i put in quotes because sometimes the code you write does get kind of long kind of out of control so you have to be careful there but it can be easier than going through the calculus or linear algebra or whatever you need to solve the problem analytically and i also put sometimes fast it took not too long to get my answer but it's not always going to be fast and that leads me into these next two points which i'll talk more about and this is what monte carlo methods are not so it isn't always fast so i just said it was sometimes fast now i'm saying it's not always fast but the point i want to get across is that it seemed reasonably fast for our examples here but it really depends on the exact problem you have even if we look at this problem still if we look at a p-value that's not one-half if you look at something bigger than a half you're going to see problems start to arise and to get an idea of that i've graphed this equation so this equation is again the analytical solution to our problem number 2 here and this graph looks like this what this is telling me is that as the probability goes from zero to one the expected number of rounds i'm going to play this game goes to infinity that is not good news for the monte carlo simulation if p is indeed large what that means is that when i'm inside this loop this is going to run for a long time if p is large because it's barely ever going to see two losses in a row indeed if i put up the full table of results here for p is equal to one half p is equal to 0. 75 and p is equal to 0.
9 you see this big issue of how long it's taking it's still getting close to the truth in all cases but it is taking longer and longer and longer to get me the answer in fact if i push this to the extreme p is equal to 0. 99999 this is going to take me hours or even days to finish depending on how big i've set p and that can be seen analytically here it's going up like this it's not going up linearly or anything nice like that it's going up in this very nasty exponential type curve so that's why monte carlo methods are not always fast they can be fast depending on the exact parameters you put in but depending on the complexity of the problem or the exact parameters you put in they can take a really long time and become impractical to use and kind of just a side note on that i didn't write this but for different values of p notice that this whole monte carlo loop was only for a single value of p so after i do this whole loop and i wait 10 seconds i get the answer for p is equal to one half but what if i want the answer for p is equal to one fourth or p is equal to 0.
