Monte Carlo Method

Definition (Monte Carlo Method)

Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to obtain numerical results.

Basic Problem of Monte Carlo

Given a pmf/pdf $\pi(x)$ , and a function $f(x)$ , estimate $\mu=\int f(x)\pi(x)dx$ where $\int$ is replaced by $\sum$ for discrete components.

Equivalently

Given $X\sim \pi$ find $\mu=E[f(x)]$ .

Naive Monte Carlo

Draw i.i.d samples $X_1,\cdots,X_n$ from $\pi(x)$ .
Estimate $\mu$ by the sample average $\hat\mu_R=\frac{1}{R}\sum^R_{i=1}f(X_i)$

Justifications:
SLLN: $\hat\mu\to\int f(x)\pi(x)dx$ w.p.1.
Decay of Variance: $Var(\hat\mu_R)=\frac{Var(f(X_1))}{R}\xrightarrow{R\to\infty}0$
1. Where $Var(f(X_1))=\frac{\hat {Var}(f(X_1)}{R}$ with $\hat{Var}(f(X_1)) = \frac{1}{R-1}\sum_{i=1}^R(f(x_i)-\hat\mu_R)^2$ is the Sample Variance

Generating Random Variables

The first step of the Monte Carlo is generating RVs. Once such method is the inversion method:

Lemma (Inversion Method)

Assume that we are able to generate i.i.d. random variables which is uniformly distributed between $(0,1)$ . Let $U\sim Unif(0,1)$ and $F$ be a one-dimensional cdf. Denote $X=F^{-1}(U), \ \text{where }F^{-1}(u)=\inf\{x\in\mathbb{R}: \ F(x)\ge u\}$ Then $X$ has the distribution F.

Consider a discrete distribution with finite support on $a_1<\cdots<a_K$ , and $\pi(a_i)=p_i, \ \text{for } 1\le i\le K$ where $\sum_{i=1}^Kp_i=1$ .
Generate $U\sim Unif(0,1)$ , and let $F^{-1}(U)=X=a_i \iff \sum_{j=1}^{i-1}p_j< U\le\sum_{j=1}^ip_j$

Monte Carlo Method

Basic Problem of Monte Carlo

Equivalently

Naive Monte Carlo

Justifications:

Generating Random Variables