Outline

1. Questions?
2. Coding Example
3. Introduction to Monte Carlo

Poll

Coding Example: CRUD Simulation

Now, let's do some simulations with the CRUD example.

Go to https://github.com/BEE4750/class-exercises and clone (you may have already done this).

If you've already cloned, make sure it's up to date with a git pull –- I made some changes over the weekend.

Monte Carlo Methods

Last week, we used Monte Carlo estimation for frequencies of sums of multiple dice.

Monte Carlo Methods

Monte Carlo Methods

In this case, we used Monte Carlo to estimate a very simple quantity (which we didn't need it for), but it's a very powerful category of methods.

Monte Carlo estimation is a very useful method for calculating complex and high-dimensional integrals, since an integral is an $n$-dimensional area:

1. Sample uniformly from the domain;
2. Compute how many samples are in the area of interest.

Monte Carlo (Formally)

We can formalize this common use of Monte Carlo estimation as the computation of the expected value of a random quantity $Y$:

$$\mu = \mathbb{E}[Y]$$

To do this, generate $n$ independent and identically distributed values $Y_1, \ldots, Y_n$. Then the sample estimate is

$$\tilde{\mu} = \frac{1}{n}\sum_{i=1}^n Y_i$$

Monte Carlo (Formally)

More generally, we want to compute some quantity $Y=f(X)$, where $X$ is distributed according to some probability distribution $p(x)$ and $f(x)$ is a real-valued function over a domain $D$.

Then $\mu = \mathbb{E}(Y) = \int_D f(x)p(x)dx.$

But the method is more general even than that: $X$ need not be continuous (like rolling dice).

And this isn't limited to scalars: so long as $f(x)$ is sufficiently well-behaved, the law of large numbers ensures that Monte Carlo estimation will work.

The Large of Law Numbers

If

(1) $Y$ is a random variable and its expectation exists and

(2) $Y_1, \ldots, Y_n$ are independently and identically distributed

Then by the weak law of large numbers:

$$\lim_{n \to \infty} \mathbb{P}\left(\left|\tilde{\mu}_n - \mu\right| \leq \varepsilon \right) = 1$$

The Large of Law Numbers

If

(1) $Y$ is a random variable and its expectation exists and

(2) $Y_1, \ldots, Y_n$ are independently and identically distributed

Then by the weak law of large numbers:

$$\lim_{n \to \infty} \mathbb{P}\left(\left|\tilde{\mu}_n - \mu\right| \leq \varepsilon \right) = 1$$

In other words, eventually we will get within an arbitrary error of the true expectation. But how large is large enough?

Monte Carlo Sample Mean

Notice that the sample mean $\tilde{\mu}_n$ is itself a random variable.

With some assumptions (the mean of $Y$ exists and $Y$ has finite variance), the Monte Carlo sample mean $\mathbb{E}[\tilde{\mu}_n]$ is

$$\frac{1}{n}\sum_{i=1}^n \mathbb{E}[Y_i] = \frac{1}{n} n \mu = \mu$$

This means that the Monte Carlo estimate is an unbiased estimate of the mean.

Monte Carlo Sample Error

Next, we'd like to know more about the error of this estimate for a given sample size.

The variance of this estimator is

$$\tilde{\sigma}_n^2 = \text{Var}\left(\tilde{\mu}_n\right) = \mathbb{E}\left((\tilde{\mu}_n - \mu)^2\right) = \frac{\sigma_Y^2}{n}$$

So as $n$ increases, the standard error decreases:

$$\tilde{\sigma}_n = \frac{\sigma_Y}{\sqrt{n}}$$

Monte Carlo Sample Error

In other words, if we want to decrease the Monte Carlo error by 10x, we need 100x additional samples. This is not an ideal method for high levels of accuracy.

Monte Carlo is an extremely bad method. It should only be used when all alternative methods are worse.

– Sokal, Monte Carlo Methods in Statistical Mechanics, 1996

Monte Carlo Sample Error

In other words, if we want to decrease the Monte Carlo error by 10x, we need 100x additional samples. This is not an ideal method for high levels of accuracy.

Monte Carlo is an extremely bad method. It should only be used when all alternative methods are worse.

– Sokal, Monte Carlo Methods in Statistical Mechanics, 1996

The thing is, though –- for a lot of problems, all alternative methods are worse!

Poll

When To Use Monte Carlo?

Converging at a rate of $1/\sqrt{n}$ is not great. But:

When To Use Monte Carlo?

Converging at a rate of $1/\sqrt{n}$ is not great. But:

• All models are wrong, and so there always exists some irreducible model error. Can we reduce the Monte Carlo error enough so it's less than the model error and other uncertainties?

When To Use Monte Carlo?

Converging at a rate of $1/\sqrt{n}$ is not great. But:

• All models are wrong, and so there always exists some irreducible model error. Can we reduce the Monte Carlo error enough so it's less than the model error and other uncertainties?

• We often need a lot of simulations. Do we have enough computational power?

When To Use Monte Carlo?

If you can compute your answers analytically, you probably should. But for real problems, we often can't, and problems that are analytically tractable are often so stylized that we want to test them across a variety of uncertainties to make sure we didn't over-simplify.