The Monte Carlo Method

now many times when you're solving mathematical problems you'll want to obtain an analytical solution to that particular problem analytical solutions are basically just exact solutions to a particular problem things are more you have an equation you have to solve then the analytical solution for that question will probably just be y equals to something in terms of X the answer is accept however sometimes finding the analytical solution to a mathematical problem isn't always the best way to approach the problem maybe because one it might take way too long to come up with the analytical solution or maybe sometimes it's just plain impossible to come up with the answer or solution to a particular problem and so many times in order to solve mathematical problems we have to go about it in a different way and instead finding an approximate solution to those particular problems finding the numerical solutions to those problems now these numerical solutions most of the times are just going to be estimates or the actual solution so the mathematical problem but many of the times these solutions themselves are ready accurate enough and can be found in a much quicker time than trying to find the analytical solutions those mathematical problems not different mathematical problems there are many different ways that you can approach it and obtain a numerical solution however these different methods will have different degrees of accuracy and most of the time we'll also take a different amount of time in order to obtain a solution a lot of the time the more accurate methods of obtaining numerical solution will actually take a longer computational time and vice-versa but in this particular video I want to talk about one particular way that we can obtain you miracle solutions to mathematical problems now this method Falls more towards this side of the numerical methods of spectrum it's rather quick however it's actually a lot less accurate than many other different ways of obtaining numerical solutions and it involves generating random numbers and a bit of probability and it's called the Monte Carlo method now the Monte Carlo method was named after a city Monte Carlo which is a part of a country called Monaco which is southeast of France now Monte Carlo is really well known to their casinos and if you sort of think about it you know you could you can probably see why the Monte Carlo method which involves random numbers with named after a city which is well known the casinos and randomness and probability of playing carding now there's a couple of different variations of the Monte Carlo methods depending on the type of mathematical problem that you have at hand however all these different variations tend to follow a very similar general set of steps which goes have been like this firstly you have to come up with a domain for your random set of numbers between which range can you're randomly generated numbers forward under secondly you have to generate random inputs generate random numbers which will fall under your domain that you're really specified earlier certainly you take these numbers that you've just found out and do a deterministic computation with them or basically for example plug them into a particular equation so that you get out some sort of an output and lastly you haven't paid the numbers that you've got and then analyze it and get a numerical answer as appropriate now the Monte Carlo method itself isn't that particularly accurate the percentage errors in this method will equal to one divided by the square root of the number of random samples that you generate however it's rather quick especially when you have data with high number degrees of freedom now what do I mean by this well let's may have a problem that deals with moving particles the particle itself will have some quarters in space an X Y Z coordinate and that itself is already three degrees of freedom but then it will also have to be moving and so we'll have three more components for its velocity and that's another three degrees of freedom so the particle itself will have six degrees of freedom and in order to find amiracle solutions for problems such as this one it's actually better to use Monte Carlo methods compared to other numerical methods that you could probably use now all this looks rather confusing doesn't it so let's show you how the Monte our method works using an example now one big use the Monte Carlo method in mathematics is to do numerical integration now assuming you have a random shape like this and you want to find the area of this random shape what you can do is you can put this shape onto a piece of paper and then start throwing darts at it assuming all the darts you throw actually ends up on the piece of paper the probability of that axe ending up on the shape or equals the proportion of the paper that is taken up by the shape is set what you're doing is you're finding the experimental probability that the dart actually lands within the shape and using that experimental probability to come up with proportions of the area taken up by the shape and then hence the area or the shape except an approximation of the shape of an area is set and this in a way is how Monte Carlo method works with numerical integration now since integration is just finding the area under a graph you can use this very same thought into numerically integrating a function with the Monte Carlo method and so now give you an example maybe let's say we have some function R we want to integrate maybe something like natural log of x divided by X and you want to integrate this from 1 to 10 how do you integrate this now this particular problem can actually be solved analytically using calculus however for this video we're more interested in the numerical solutions to this problem so let's try to solve the problem using the Monte Carlo method so first let's look at the graph for this equation the graph of this equation actually looks a bit like this and this is the area under the graph that were interested in so how do I use the Monte Carlo method to integrate this numerically well first I have to come up with some sort of a domain for the random points that we'll be generating so let me draw a box over this graph like this and so I'll say that all the points I generate all have to lie somewhere within this box so what I can do is I can generate random points within the box and then check whether this generative point actually falls under the graph now in order for me to obtain an accurate numerical solution I have to do this many many times maybe say for example a million times and then after generating a million points I can then take these million points and then do some calculations where they're finding the proportion of the points that falls under the grass and then hence be able to find the area under the graph and then be able to find the answer to the integral problem that I've been after now of course if I want to do a million randomly generated points it's going to take me forever if I do it by hand and this is why I'll hand it over to my computer spend over there he's going to show you how to do it on computer yay it's just way too hot so I'm going to do now to be demonstrating how to perform the Monte Carlo method on the computer are basically going to just take the instructions I already told you earlier and translating those instructions into lines of code on the computer and for demonstration purposes I'm going to be writing all my code in Python because it's a very simple language and if the only computer language that I actually know so before I even do anything first of all then import a few modules so I'm going to import a module called math and I'm going to import another module called random now the next I'm going to do is I'm going to find two different counters right so the first counter is going to just be like the counter that count how many points been generated and firstly I set it to equal to zero and the second one is just going to be how many of them is actually inside the area which I'll call in area again we'll set that to be zero at first now that bit is the actual interesting it's the bit that actually like get into the real juice of like the multicolor method I'm going to do is I'm going to define something called a wire loop right so we're just going to say that wild count is still less than 1 million so what the while loop is forward that as long as the conditions is met as long as the count is still less than a million the instructions that under the wire loop will still be run continuously will still be moved through so because we want a million samples we're not going to stop the loop until we have a million random point until the count actually reaches 1 million as on each loop all we have to do is we have to generate a random point and then see if that random point actually lies under the area or not and it does lie under the area we add one to the counter for in area and so how do we do this well first of all we have to generate the random point right so the random point will have two bits will have an x coordinate and we'll have all Y coordinates so I'll generate those two components separately so first we're going to generate the x coordinate which I'll call X chord and can generate this random coordinate we're going to use a function called random we're going to use a random function it's going to be random Don uniform and we're going to set a lower bound and an upper bound for the random number that can be generated I mean look back at the diagram for the box that I drew right earlier this video you'll see that the lower bound and the upper bound is going to be one and tenth the x coordinates so I'm just going to put that into me one and ten back now let's do something similar for the Y coins so we look at the graph again we'll see that the lower bound for the Whitewater is just going to be zero I'll be upper bound the graph so between x equals 1 and x equals 10 the highest value that Y can be will be 1 over e and so that will be the upper bound for the y coordinate of a randomly generated point and so just put that in to our code the upper bound for the y coordinate will be 1 divided by the number E and so now we have our randomly generated point which has got both an x coordinate one corner and so we have to do next is we have to check whether this point lies underneath the curve or not how do we do that so let's visualize this let me bring back the image from earlier of the curve so let's say we have eight point as lying somewhere within the boss the randomly generated point now if you take your x corner and then put it into the function you'll get out of Y value just corresponds to a certain point on that curve and so to see if you're randomly generated point lies underneath the curve or not you just have to take your randomly generated y coordinate and compare it against that value that is given out by the function if you're randomly generated why chorded is lower than the value get out of the function it means that the point lies underneath the curve so let's put that into mind of codes right if the y coordinate of the point is less than the function which will be as I defined earlier function and that particular value of x or at the X corners then what we can do is we can add one to the counter which count how many points lies within the area or the variable in area so if this condition is satisfied we're going to add one to in area so that's going to be in area but equal one and nothing we have to also do is we have to also add one to count so that we can keep track of how many times we are really completed the loop and so now what I have if I have a randomly generated point and we already checked for that point lies underneath the curve or not and we're going to be performing this entire operation here a million times or until the count is actually at a million then we stop this process so after a million loops we're going to have some number of points which lies underneath the graph which is already being tallied what next do we do with this information well the probability of a randomly generated point line underneath the graph or equal to the area underneath the graph or the integral that we're interested in divided by the total amount of area that the points could have landed on which is the air of the rectangle the box that we drew earlier and then now this probability can also be found experimentally which is the whole bit of us randomly generating points and seeing where they land in the very first place and so the probability of the point landing underneath the graph can be found experimentally and I'll just be the proportions of the randomly generated point that we have which lives underneath they draw as we can be arranged this a bit and so we'll get at the area under the graph or we can sell the integral that we're actually interested in or equal to the number of points that action land underneath the graph divided by the total number of points that we generated times the area of the boss at two points could have existed the total area of the box would just be 9 times 1 over E which is equal to 9 okay and I'll just put that into my code that the area of the box will just equal to 9 divided by and so now in order for us to find the area of the integral all I have to do is I just have to take the area's box and multiplied by the proportion of the points that lies underneath the graph alright so the proportion of the point that lies underneath the graph or equal to how many point lies within the area or in area divided by the total number of points that we have which is the count which should be a million and we're going to multiply that by the total area of the box and so here's the moment of truth I'm going to run this code and we'll see how it goes so let's do this what does it give us the answer it gives me two point six five zero so let's only consider the first three decimal places so your answer this integral call is the Monte Carlo method as I read it earlier is going to equal to two point six five one two three decimal places and the error at the percentage error will be zero point one percent which is one divided by the square root of a million ghulami point wheat manually generated and how does this fair the actual answer [Music] looks right to me [Music] now the Monte Carlo method has loads and loads of other applications not just numerical integration Monte Carlo method also has many other uses outside of mathematics applied into other fields from physics and engineering all the way to statistics for teaming finance except I don't have time to explain all those uses because that's an end the video somewhere so I'm going to end it right here thank you very much for watching this video and I hope you have a great time and also you can't give up

Channel: RandomMathsInc

Views: 41,419

Rating: 4.93646 out of 5

Keywords: monte, carlo, method, random, numbers, generation, physics, monaco, city, pi, day, numerical, analytical, integration, differentiation, python, demonstration, code, randommathsinc, finance, uses, dart, probability, computer, deterministic, mathematics

Id: q6gJ2T0NSwM

Length: 16min 0sec (960 seconds)

Published: Mon Aug 14 2017