.. _chapter2:

Chapter 2: Monte Carlo Simulation
=================================

.. contents:: Chapter Contents
   :local:
   :depth: 2

Monte Carlo simulation transforms deterministic problems into stochastic experiments, leveraging 
the law of large numbers to solve complex computational challenges. This chapter provides a 
comprehensive foundation in Monte Carlo methods, from the fundamental mathematics of pseudo-random 
number generation to sophisticated sampling techniques that enable efficient simulation of complex 
probability distributions.

We begin by examining the paradox at the heart of computational randomness: how deterministic 
algorithms create sequences that pass statistical tests for randomness. Building on this foundation, 
we explore the two primary paradigms for random variate generation—the inverse transform method 
and rejection sampling—each offering unique advantages for different classes of distributions. 
The chapter culminates with variance reduction techniques that can improve estimator efficiency 
by orders of magnitude and real-world applications demonstrating the power of these methods in 
statistical inference.

Throughout this chapter, we emphasize both theoretical understanding and practical implementation. 
Every algorithm is presented with complete Python code, performance analysis, and diagnostic tools. 
By the chapter's end, you will have built a complete toolkit for Monte Carlo simulation, from 
low-level random number generation to high-level statistical applications.

**Learning Objectives:** Upon completion of this chapter, students will be able to:

**Foundational Understanding**

* **Define** Monte Carlo methods mathematically as expectations with respect to probability distributions and explain their convergence properties via the Strong Law of Large Numbers and Central Limit Theorem
* **Analyze** the O(1/√n) convergence rate of Monte Carlo estimators and its independence from dimensionality
* **Compare** Monte Carlo integration with deterministic quadrature methods in high-dimensional spaces

**Random Number Generation**

* **Implement** pseudo-random number generators including Linear Congruential Generators, Mersenne Twister, and PCG family algorithms
* **Evaluate** PRNG quality using statistical test suites including chi-square, serial correlation, runs, and spectral tests
* **Design** seed management systems for reproducible simulations in parallel computing environments

**Random Variate Generation**

* **Apply** the inverse CDF method for continuous and discrete distributions with closed-form quantile functions
* **Implement** efficient search algorithms (binary search, alias method) for discrete sampling
* **Master** rejection sampling for distributions lacking tractable inverse CDFs
* **Derive** optimal proposal distributions and acceptance bounds for rejection algorithms
* **Transform** uniform random variables to normal distributions using the Box-Muller method

**Advanced Techniques**

* **Implement** variance reduction techniques including antithetic variates, control variates, and importance sampling
* **Analyze** efficiency gains from variance reduction and determine when each technique is appropriate
* **Design** stratified and Latin hypercube sampling schemes for improved space coverage

**Practical Applications**

* **Solve** integration problems in high dimensions where deterministic methods fail
* **Estimate** probabilities and expectations for complex statistical models
* **Implement** bootstrap and permutation tests using Monte Carlo principles (next chapter)
* **Debug** Monte Carlo simulations using convergence diagnostics and visual tests

.. toctree::
   :maxdepth: 2
   :caption: Sections

   ch2_1-monte-carlo-fundamentals
   ch2_2-uniform-random-variates
   ch2_3-inverse-cdf-method
   ch2_4-transformation-methods
   ch2_5-rejection-sampling
   ch2_6-variance-reduction-methods
   ch2_7-chapter-summary