Course Outline: Monte Carlo Methods

I.      Introduction
        A.  What are Monte Carlo methods (MCMs)?
        B.  A review of relevant elementary probability and statistics
        C.  An example: numerical integration
             1.   The curse of dimensionalitycomputational complexity
             2.   Computational complexity vs. deterministic methods
             3.   Convergence and variance
                    a.  Introduction to variance reduction
                         i.    Crude Monte Carlo
                         ii.   Stratified sampling
                         iii.  Importance sampling
                         iv   Control variates
                         v.   Antithetic variates
                         vi.  Other methods for integration
                    b.  Accelerating rates of convergence via random numbers
                         i.    Overview of pseudorandom number generation
                         ii.   Quasirandom number generation and convergence acceleration

II.     MCMs and Linear Operators
        A.  Linear algebra
              1.   Approximate summation
              2.   Approximate matrix-vector multiplication
                    a.  Application to linear system solution via Neumann series
                         i.    Reduction to fixed-point form
                         ii.   Truncation error and absorbing walks
                         iii.  Computational complexity
                         iv.  Advantages and disadvantages
                    b.  Application to eigenvalue problems
                         i.     Power method
                         ii.   Approximate inverse iteration
                         iii.  Computational complexity
                         iv.  Advantages and disadvantages
                    c.  Sequential Monte Carlo and residual correction
               3.  Open problems
         B.  Integral equations
               1.   Integral equations of the second kind
                     a.  Continuous random walks
                     b.  Neumann series and scoring
                     c.  Truncation error and absorbing walks
               2.   The Boltzmann equation
               3.   Importance sampling
         C.  Green's Function Monte Carlo
               1.   The Schrödinger equation
               2.   Random walks
               3.   Importance sampling

III.    Advanced Topics
         A.  Functional integration and Brownian motion
               1.  Brownian motion introduction
               2.  Measures on infinite dimensional spaces
               3.  Functional integration
               4.  The Feynman-Kac formulas
                    a.  Linear parabolic partial differential equations (PDEs)
                    b.  Linear elliptic PDEs
                    c.  Boundary conditions
                         i.   Dirichlet
                         ii.  Neumann
                         iii. Mixed conditions
         B.   Solution of PDEs via stochastic differential equation (SDE) methods
               1.  Numerical solution of SDEs
               2.  Functional evaluation
         C.   Acceleration techniques
               1.   Walk on spheres (WOS)
                     a.  Spherical means and Greens theorem
                     b.  Thickening the boundary: the epsilon-boundary layer
                          i.   The O(epsilon) error introduced
                          ii.  Expected number of steps in the random walk and epsilon
                     c.  Computational complexity
               2.   Walk on the boundary
                     a.  Convex domains
                     b.  Extensions
               3.   Greens Function First Passage (GFFP)
                     a.  Extension of WOS
                     b.  Elimination of the epsilon-boundary layer
                     c.  Creation of a Greens function library
                     d.  The simulation-tabulation method
          D.   Applications
                1.  Permeability computations
                     a.  Penetration depth
                     b.  Relationship with capacitance
                     c.  Open problem: anisotropic computations
                2.  Electrostatics
                     a.  Poisson/Laplace equations
                          i.   Computing the capacitance
                          ii.  Computing charge density
                          iii. Singular computations
                     b.  Biological electrostatics: the Poisson-Boltzmann equation (PBE)
                          i.   The linearized PBEs
                          ii.  The nonlinear PBE
                          iii. Boundary conditions
                          iv.  Derivatives

Return to class homepage.