Consider a random variable $X \sim p$ (the pdf if $X$ is continuous, and the pmf if discrete), defined over the sample space $\Omega$. **Monte Carlo** gives an estimate to the expectation $\hat{\theta}\approx \theta = \mathbb{E}[\phi(X)]$of some function of it $\phi(X)$. - Since the expectation for $X$ continuous is $\mathbb{E}[\phi(X)]=\int _{\Omega}\phi(x)p(x) \, dx $Monte Carlo is also an algorithm for estimating integrals. - In particular, $\mathbb{P}[X \in D]$ for some $D \subseteq \Omega$ can be estimated with $\phi(X)=\mathbb{1}_{X \in D}$ and uniform $X \sim U(\Omega)$. > [!algorithm] Monte Carlo Method > The **Monte Carlo method** estimates $\mathbb{E}[\phi(X)]$ by: >- (1) Sample $X_{1},\dots,X_{n} \overset{iid.}{\sim}p$. > - (2) Return the **Monte Carlo estimator** $\hat{\theta}=\frac{1}{n}\sum_{i=1}^{n}\phi(X_{i})$ ### Properties of Monte Carlo - *Unbiasedness*: if $\hat{\theta}$ is the Monte Carlo estimator, $\mathbb{E}[\hat{\theta}]=\theta$. - *Consistency*: as sample size $n \to \infty$, $\hat{\theta} \to \theta\,\,\mathrm{a.s.}$. - *Asymptotic normality*: asymptotically $\frac{\sqrt{ n }}{\sigma}(\hat{\theta}-\theta)\xrightarrow{d} N(0,1)$where $\sigma^{2}=\mathrm{Var}(\phi)$, and hence $\sigma^{2} / n=\mathrm{Var}(\hat{\theta})$. > [!proof]- > Unbiasedness is immediate from linearity of the expectation. > > Consistency is the strong law of large numbers applied to $\hat{\theta}$ as the sample mean of $\phi(X_{i})$. > > Asymptotic normality is the CLT applied to $\hat{\theta}$. ### Accuracy Measures The target's variance $\mathrm{Var}(\phi(X))$ can be unbiasedly estimated by: $S^{2}_{\phi}=\frac{1}{n-1}\sum_{i=1}^{n}(\phi(X_{i})-\hat{\theta})^{2}$ > [!proof]- Proof outline > Proof of unbiasedness is just a standard proof that a sample variance $S^{2}_{\phi}$ is an unbiased estimator of the population variance $\mathrm{Var}(\phi)$. Using the asymptotic normality, $\mathbb{P}\left( |\hat{\theta}-\theta|< \frac{z\sigma}{\sqrt{ n }} \right) \to 2\Phi(z)-1$So setting $z$ to be the appropriate percentiles (e.g. $97.5\%$ for a $95\%$ CI), the asymptotic confidence interval for ${\theta}$ is $\left( \hat{\theta} \pm \frac{z\sigma}{\sqrt{ n }} \right) \approx \left( \hat{\theta} \pm \frac{zS_{\phi}}{\sqrt{ n }} \right)$where again $S_{\phi}$ is the sample standard deviation, which approximates the unknown $\sigma=\mathrm{std}(\phi(X))$.