Introduction to Probability, Second Edition, 2nd Edition

12

Markov chain Monte Carlo

We have seen throughout this book that simulation is a powerful technique in probability. If you can’t convince your friend that it is a good idea to switch doors in the Monty Hall problem, in one second you can simulate playing the game a few thousand times and your friend will just see that switching succeeds about 2/3 of the time. If you’re unsure how to calculate the mean and variance of an r.v. X but you know how to generate i.i.d. draws $X_1,X_2,\dots ,X_n$ from that distribution, you can approximate the true mean and true variance using the sample mean and sample variance of the simulated draws:

$\begin{array}{lll}\hfill E\left(X\right)& \approx \frac{1}{n}\left(X_1+\cdots +X_n\right)={\bar{X}}_n,& \\ \hfill \text{Var}\left(X\right)& \approx \frac{1}{n-1}\sum _{j=1}^n{\left(X_j-{\bar{X}}_n\right)}^2.& \end{array}$

The law of large numbers tells us that these approximations will ...