This two-part course builds upon the programming skills that you learned in our Introduction to Interactive Programming in Python course. We will augment those skills with both important programming practices and critical mathematical problem solving skills. These skills underlie larger scale computational problem solving and programming. The main focus of the class will be programming weekly mini-projects in Python that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 1 of this course, the programming aspect of the class will focus on coding standards and testing. The mathematical portion of the class will focus on probability, combinatorics, and counting with an eye towards practical applications of these concepts in Computer Science. Recommended Background - Students should be comfortable writing small (100+ line) programs in Python using constructs such as lists, dictionaries and classes and also have a high-school math background that includes algebra and pre-calculus.
Monte Carlo Methods
Loading...
來自 Rice University 的課程
Principles of Computing (Part 1)
332 個評分
從本節課中
Probability, randomness, and objects/references
This we will learn how to use probability and randomness to solve problems.
與講師見面
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[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.
