[MUSIC] In Monte Carlo methods, you perform a bunch of random trials in order to figure out the expectation that some event, or multiple events, will actually occur. Now, why would you do that? Well, usually you do this in situations where it is difficult or impossible to directly compute the answer, or perhaps directly computing the answer would take far too long Okay. Now why is this called the Monte Carlo methods? [LAUGH] Well, it's, because of the similarity to going to a casino and basically playing and recording the result of a bunch of, of gambling games, okay, and in that situation you're basically randomly sampling,the probabilities of winning and losing those games, okay? And perhaps such casinos appear in Monte Carlo, alright, now, in the real world what kind of of situations do we use this in? Generally Monte Carlo methods are used for you know, sort of physical or mathematical problems and the the major classes of problems are optimisation problems, figuring out probability, distributions and numerical integration, all right? So let's take a look at how this works. This program uses Monte Carlo simulations, to determine the expected value of getting exactly three of a kind when you roll five dice. Now, I could compute the exact probability here, but it's actually a little bit difficult to do so. So we can use Monte Carlo methods to make our lives a little easier. But because can compute it directly, we can also check the answer. Now, the answer isn't completely obvious, because I did search the web a little bit to see if other people are able to do, and there are actually a lot of wrong answers out there. Okay, so we'll be able to confirm that the right answer actually is the right answer alright, so how do we do this? Well, we need to have a notion of what is a trial and what is an event, okay? Here a trial is one roll of these five dice. So you can see I have a function called compute trial, that rolls five dice. Basically, it picks five random numbers between one and six and returns them in a list, okay? Now what is an event? An event is that I got exactly three of a kind. So I have a function here called check event that checks this. It looks through the five dice and sees if there are three of a kind of any number alright. Now, I use these two functions in one simulation step, so what is one simulation step? I compute a trial, so I roll the dice, and I check if the event has occurred, alright? And my simulation step function here returns true or false. True if the even occurred during this step, false if it did not alright? And then we have now our Monte Carlo function alright. All right we're just doing the basic Monte Carlo simulation where it takes as input the number of trials that I'd like to run. And then there's just a loop here that iterates for that many trials, each time I run one simulation step, and if the event happens I increment my counter if it does not I don't okay. And so now the expected probability that the event will occur, is simply the number of times the event did occur divided by the number of trials, and that's what this Monte Carlo function returns. Okay, so, I have my Monte Carlo function that performs the simulation, how do we actually run it? Well, you can see I have a run function here which is going to run the simulation for different numbers of trials, so we can see what happens. You can see in the comment that I also have put the actual probability of getting three of a kind when you roll five dice that number is .1929, alright? So basically one out of every five times you can probably expect to get three of a kind, okay. Now you'll notice I pick a number of trials between 10 and 100,000. Now before we run anything I want to you think about this for a minute, okay. Do you expect to get more accurate results running 10 trials or 100,000 trials? Why? Okay, so let's run this, let's see what actually happens. Okay, I cut the video so you didn't have to wait for it to actually complete here. But you can see what happened, right, with ten trials I get a wildly incorrect result, 0.4. Alright, then it gets a little bit better, 0.18, and then oscillates around and finally converges to about 0.19373, which is actually very close to the expected probability. Okay, so you can see as I run more trials, things get a little bit more accurate. Now there's no way that, no reason why it needs to look exactly like this In fact it's going to look different every time, so let's run it again. Okay, you can see that this time I got different results. With only ten trials it says 0.1, but then with 100,000 trials I have 0.19375, which again is very close to the actual probability. Okay, so there's no reason why you should believe that this, that the results should look any particular way. The one thing though is that as you run larger and larger numbers of trials, I would expect the simulation to yield more accurate results. And you can see about 100,000 trials here, this simulation is pretty consistently accurate about giving me a number that is very close to the real probability of rolling three of a kind. So the example I've used here to motivate Monte Carlo methods is actually pretty simplistic, and in fact, I can directly compute the answer, I gave you the answer, even, right? But that allowed us to see that this method actually does produce the expected results. But things really get interesting when you have a problems for which you can't directly compute the answer, and that's where Monte Carlo methods really become invaluable, right? And they get used in lots of places. They get used in the physical sciences. They get used in engineering. They get used in computational biology. You can even use them in finance, you can imagine using Monte Carlo methods to evaluate the expected value of an investment portfolio alright, now, when you use Monte Carlo methods, you have to be careful. You have to start thinking about what you're doing, alright, and making sure that you use enough trials so that you're goinig to get an accurate, accurate result, okay? You need to make sure that these trials are correct, that you are randomly picking from all of the possibilities in the right way, okay? And you also have to make sure that the way that you're doing this is accurately simulating, the phenomenon that you're trying to model okay? But if you do all these things, we now have this method that allows us to just randomly try a couple times well, a bunch of times, alright? And if you try this enough, you can actually figure out the expected value of some event occurring, rather than having to directly compute this, alright? And this is an extremely powerful technique.
