# Monte Carlo Methods and Applications
### CMU 21-387 | 15-327 | 15-627 | 15-860 FALL 2024
**[math.cmu.edu/~mcm-cmu](https://math.cmu.edu/~mcm-cmu)**
[Home](index.html) — [Course Info](#info) — [Schedule](#schedule) — [Assignments](#assignments) — [Resources](#resources) — [Course Policies](#policies)
**Instructors:** Keenan Crane (CSD/RI) and Gautam Iyer (MSC)
**Location:**
**Date and time:** Tuesday / Thursday, 12:30am–1:50pm
**Units:** **9** (3 in-class/6 outside)
### Course Info
The Monte Carlo method uses random sampling to solve computational problems that would otherwise be intractable, and enables computers to model complex systems in nature that are otherwise too difficult to simulate. This course provides a first introduction to Monte Carlo methods from complementary theoretical and applied points of view, and will include implementation of practical algorithms. Topics include random number generation, sampling, Markov chains, Monte Carlo integration, stochastic processes, and applications in computational science. Students need a basic background in probability, multivariable calculus, and some coding experience in any language. Coding assignments will be done in [Python 🐍](https://www.python.org/).
**Key Topics:** definitions of randomness, random number generation, randomness testing and quality measures, curse of dimensionality, sampling and aliasing, Markov chains, Monte Carlo methods, stochastic processes, sample generation algorithms, applications of random numbers in computation
#### Course Overview
Random numbers are a basic tool for achieving robustness, scalability, and correctness in the design of algorithms. Moreover, randomness is an essential part of models used to describe the behavior of systems found throughout science, technology, and engineering. The Monte Carlo method in particular was recognized by SIAM as one of the [most important 10 algorithms of the 20th century](http://pi.math.cornell.edu/~web6140/). This course complements the existing curriculum, helping to better prepare students to apply randomness to problem solving in both academic and industrial settings.
The goal of this course is to enable students to identify situations where random sampling provides the best solution to a computational/algorithmic problem, and to train them in the practical implementation of associated methods. Students should also acquire the mathematical background needed to derive new algorithms from first principles, rather than purely applying existing techniques, and to analyze the correctness and efficiency of these algorithms. (For example, they should be able to determine whether a given Monte Carlo estimator is unbiased, and measure the empirical efficiency of such algorithms in terms of statistics such as variance.)
A secondary goal of this course is to expose students to a collection of application areas in computer science and the broader sciences where randomness can be profitably applied. In computer science, this set includes problems in computer systems/networking, programming languages, theoretical computer science, artificial intelligence/machine learning, and computer graphics. In the broader sciences, this includes partial differential equations arising in physics/chemistry/biology/etc., and stochastic models appearing in mathematical finance.
#### Learning Objectives
* Identify situations where random sampling provides the best solution to a computational/algorithmic problem.
* Implement the associated methods.
* Acquire the mathematical background needed to derive new algorithms from first principles.
* Analyze the correctness and efficiency of these algorithms.
* Become familiar with a collection of application areas in computer science and the broader sciences where randomness can be profitably applied.
#### Prerequisite Knowledge
_What prior knowledge must students have in order to be successful in this course?_
Students must have basic knowledge of coding (in any language), as well as basic knowledge of probability and multivariable calculus. CMU courses satisfy the prerequisites are listed below; please contact the instructors if you believe you've taken a different course that fulfills the requirement.
**Probability:** 15-259 or 21-325 or 36-218 or 36-219 or 36-225 or 36-235 or 18-465
**Multivariable Calculus:** 21-254 or 21-256 or 21-259 or 21-266 or 21-268 or 21-269
### Lectures
_[For slide-based lectures, lecture titles will link to slides. For chalkboard-based lectures, see the [brief lecture notes](https://www.math.cmu.edu/~gautam/c/2024-387/notes/index.html) and “live notes” taken in-class.]_
- **27 Aug (Tue)** —
[Introduction](https://www.math.cmu.edu/~gautam/c/2024-387/notes/01-intro.html), [Basic Sampling Algorithms](https://www.math.cmu.edu/~gautam/c/2024-387/notes/02-sampling.html) [[live notes](live-notes/Lecture01.pdf)]
- **29 Aug (Thu)** —
[Inversion and Rejection Sampling](https://www.math.cmu.edu/~gautam/c/2024-387/notes/02-sampling.html) [[live notes](live-notes/Lecture02.pdf)]
- **03 Sep (Tue)** —
[Introduction to Numerical Python](https://www.math.cmu.edu/~gautam/c/2024-387/notes/04-numpy.html) and [MCMC](https://www.math.cmu.edu/~gautam/c/2024-387/notes/05-mcmc.html) [[live notes](live-notes/Lecture03.pdf)]
- **05 Sep (Thu)** —
[Using Metropolis Hastings on the Ising Model](https://www.math.cmu.edu/~gautam/c/2024-387/notes/06-metropolis-hastings.html) [[live notes](live-notes/Lecture04.pdf)]
- **10 Sep (Tue)** —
[Markov Chains: Irreducibility, and Stationary Distributions](https://www.math.cmu.edu/~gautam/c/2024-387/notes/07-markov-chains.html) [[live notes](live-notes/Lecture05.pdf)]
- **12 Sep (Thu)** —
[Markov Chains: Aperiodicity, and TV convergence](https://www.math.cmu.edu/~gautam/c/2024-387/notes/07-markov-chains.html) [[live notes](live-notes/Lecture06.pdf)]
- **17 Sep (Tue)** —
[Markov Chains: Convergence to the Stationary Distribution](https://www.math.cmu.edu/~gautam/c/2024-387/notes/07-markov-chains.html) [[live notes](live-notes/Lecture07.pdf)]
- **19 Sep (Thu)** —
[Markov Chains: Page Rank, Ergodicity and Mixing](https://www.math.cmu.edu/~gautam/c/2024-387/notes/08-mixing-times.html) [[live notes](live-notes/Lecture08.pdf)]
- **24 Sep (Tue)** —
[Simulated Annealing and Tempering](https://www.math.cmu.edu/~gautam/c/2024-387/notes/10-simulated-annealing.html) [[live notes](live-notes/Lecture09.pdf)]
- **26 Sep (Thu)** —
[Traps near local minima](https://www.math.cmu.edu/~gautam/c/2024-387/notes/10-simulated-annealing.html) and [Detailed Balance](https://www.math.cmu.edu/~gautam/c/2024-387/notes/09-metropolis-hastings2.html) [[live notes](live-notes/Lecture10.pdf)]
- **01 Oct (Tue)** —
[Metropolis Hastings Revisited](https://www.math.cmu.edu/~gautam/c/2024-387/notes/09-metropolis-hastings2.html) [[live notes](live-notes/Lecture11.pdf)]
- **03 Oct (Thu)** —
Diffusion Models
- **08 Oct (Tue)** —
[Basic Monte Carlo Integration](slides/MCMA-FA24-BasicMonteCarloIntegration.pdf)
Definition of basic Monte Carlo estimator, bias vs. consistency, measures of quality, sample variance, convergence rate, examples.
- **10 Oct (Thu)** —
[Convergence of Monte Carlo Integration](slides/MCMA-FA24-ConvergenceOfMonteCarloIntegration.pdf)
Tail bounds, Markov's inequality, Chebyshev's inequality, weak law of large numbers, Fourier transform, characteristic functions, convolution
- **22 Oct (Tue)** —
[Variance Reduction I](slides/MCMA-FA24-VarianceReductionI.pdf)
definition of efficiency, control variates, stratified sampling
- **24 Oct (Thu)** —
[Variance Reduction II](slides/MCMA-FA24-VarianceReductionII.pdf)
importance sampling, quasi-Monte Carlo
- **29 Oct (Tue)** —
[Numerics and Random Numbers](slides/MCMA-FA24-NumericsRandomNumbers.pdf)
floating point, parallel implementation, measures of randomness pseudorandom number generators
- **31 Oct (Thu)** —
[Sample Generation](slides/MCMA-FA24-SampleGeneration.pdf)
special distributions, discrete distributions, alias table
- **07 Nov (Thu)** —
[Sample Generation II](slides/MCMA-FA24-SampleGeneration.pdf)
continuous distributions, inversion method, rejection method, resampling
- **12 Nov (Tue)** —
[Ordinary Differential Equations](slides/MCMA-FA24-SDEs.pdf)
ordinary differential equations (ODEs), numerical integrators (forward Euler, backward Euler, symplectic Euler), stability analysis
- **14 Nov (Thu)** —
[Stochastic Differential Equations](slides/MCMA-FA24-SDEs.pdf)
Brownian motion & diffusion processes, numerical integrators (Euler-Maruyama), application: molecular dynamics simulation
- **19 Nov (Tue)** —
[MCMC Algorithms](slides/MCMA-FA24-MCMCAlgorithmsI.pdf)
continuous state Markov chains, aperiodicity, irreducibility, detailed balance
- **21 Nov (Thu)** —
[Metropolis-Hastings](slides/MCMA-FA24-MCMCAlgorithmsI.pdf)
Metropolis-Hastings on continuous state space, convergence, burn-in
- **26 Nov (Tue)** —
[Langevin Monte Carlo](slides/MCMA-FA24-LangevinMonteCarlo.pdf)
statistical mechanics, entropy, Boltzmann distribution, underdamped/overdamped Langevin equation, Langevin Monte Carlo (LMC), Metropolis Adjusted Langevin Algorithm (MALA)
- **03 Dec (Tue)** —
Poisson Processes (Guest Lecturer: [Ioannis Gkioulekas](https://www.cs.cmu.edu/~igkioule/))
- **05 Dec (Thu)** —
Quantum Monte Carlo (Guest Lecturer: [Ryan O'Donnell](https://www.cs.cmu.edu/~odonnell/))
### Assignments
**All assignments are due at 11:30am Eastern time (NOT midnight!)**
A new one will post every week on Tuesday, unless announced otherwise.
The distribution of the scores on the homework can be found [here](https://www.math.cmu.edu/~mcm-cmu/2024/auth/)
- [Assignment 1](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw1.html), _due: Sep 3_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw1.html) and [detailed solutions by Thomas](https://www.math.cmu.edu/~gautam/c/2024-387/auth/sol1-thomas.pdf).
- [Assignment 2](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw2.html), _due: Sep 10_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw2.html).
- [Assignment 3](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw3.html), _due: Sep 17_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw3.html).
- [Assignment 4](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw4.html), _due: Sep 24_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw4.html).
- [Assignment 5](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw5.html), _due: Oct 1_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw5.html).
- [Midterm](https://www.math.cmu.edu/~gautam/c/2024-387/hw/midterm.html), _due: Oct 8_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/midterm.html)
- [Assignment 6](assignments/Assignment06.pdf), _due: Oct 22_.
- [Assignment 7](assignments/Assignment07.pdf), _due: Nov 1_.
- [Assignment 8](assignments/Assignment08.pdf) [[code]](assignments/Assignment08-code.zip), _due: Nov 8_.
- [Assignment 9](assignments/Assignment09.pdf) [[code]](assignments/Assignment09-code.zip), _due: Nov 26_.
- [Final](final/MCMA-Final-2024.pdf) [[data]](final/GSPC.csv), _due: Friday, Dec 13 at 5pm EST_. [solutions](final/MCMA-Final-2024-Solutions.pdf)
### Resources
#### Office Hours
- Mon 3:00–4:50PM **TA** Mario Tutuncu-Macias (room Citadel Teaching Commons)
- Mon 5:00–6:50PM **TA** Jiannan Jiang (Wean 6213)
- Wed 3:00–4:50PM **Instructor** Keenan Crane (Smith 217)
- Thu 3:00–4:50PM **Instructor** Gautam Iyer (Wean 8115)
- Fri 3:00–4:50PM **TA** Thomas Horstkamp (Wean 7215)
#### Infrastructure
- **General announcements** — sent via [email](https://lists.andrew.cmu.edu/mailman/listinfo/math-cs-montecarlo).
- **Discussion** — via the [CMU Math Discourse server](https://zym.math.cmu.edu/c/f2024-387). You will need to log in via your AndrewID to post.
- **Live chat** — via the [Monte Carlo CMU FA23](https://www.math.cmu.edu/~mcm-cmu/2024/auth/) Discord server.
If you joined late, please [add yourself to the mailing list](https://lists.andrew.cmu.edu/mailman/listinfo/math-cs-montecarlo), and email the instructors your Andrew ID.
This will allow you access to the [private website](https://www.math.cmu.edu/~mcm-cmu/2024/auth/) which contains the Gradescope code, Discord server link and solutions.
#### Notes and References
##### Notes
- [Lecture notes for black board lectures](https://www.math.cmu.edu/~gautam/c/2024-387/notes/index.html) (This only contains statements of important results from the blackboard lectures by Gautam; explanations, motivation and proofs will be done in class and are not in these notes.)
- [Lecture notes from 2023](https://www.math.cmu.edu/~gautam/c/2024-387/pdfs/mc.pdf) (This is roughly what Gautam covered in half of the 2023 version of this course. Again this only contains statements and definitions; the motivation / proofs were done in class.)
##### Recommended References
- [A First Course in Monte Carlo Methods](https://arxiv.org/pdf/2405.16359), D. Sanz-Alonso, O. Al-Ghattas.
- [Monte Carlo Theory, Methods and Examples](https://artowen.su.domains/mc/), Art Owen
- [Markov Chains](https://www.statslab.cam.ac.uk/~james/Markov/), James Norris
- [Physically Based Rendering](https://www.pbr-book.org/) _Chapters 13 & 7_, Pat Hanrahan, Greg Humphreys, Wenzel Jakob, Matt Pharr
- [Robust Monte Carlo Methods for Light Transport Simulation](http://graphics.stanford.edu/papers/veach_thesis/) _Chapters 2 & 11_, Eric Veach
##### Past semesters
- [Monte Carlo Methods and Applications FA2023](mcma-fa2023.html)
### Course Policies
#### Assignments & Submission
- Weekly short assignments, typically assigned Tuesday and due the following Tuesday.
- **Written exercises**
- all work must be submitted digitally (_no paper!_)
- either typeset (via [LaTeX](https://www.overleaf.com/learn/latex/Learn_LaTeX_in_30_minutes)) or scans/photos of written work
- **Coding exercises**
- all coding is in [Python 🐍](https://www.python.org/)
- Python is **not** a prerequisite, but you should have _some_ coding experience (in any language)
- Submit via [Gradescope](https://www.gradescope.com/courses/830878), `21387` in the *Math* department.
- If you joined late, email us your Andrew ID.
We will give you access to the [private website](https://www.math.cmu.edu/~mcm-cmu/2024/auth/), which contains the Gradescope code required to add yourself to Gradescope.
#### Late Days & Dropped Assignments
- Assignments due at 11:30 am Eastern time on due date (one hour before class starts)
- **11:30 am is not midnight!** 🤪
- Two assignments can be dropped without penalty
- if you don’t drop any, we’ll just take best N-2 scores
- Can use five late days throughout semester, and turn in up to five assignments 24h late.
- _if no more late days remain, late work gets a zero!_
- Late days & drops _already_ account for sick days, late adds, job interviews, conference travel, etc.
- Cannot be used for midterm & final
- Please don’t bug TAs/instructors about extra late days and drops! 🥵
#### Waitlist & Late Add
- Don't be fooled by the waitlist: we have _never once_ had a situation where an eligible student has not ultimately been able to get a spot in the class. The room is big, and people inevitably drop. Please just hang in there.
- If you're on the waitlist and hope to join the class, **please still show up to lecture, and complete / hand in the assignments!** Doing so will only make life easier once you are officially enrolled in the class.
- If there are free spots in the class but you're still stuck on the waitlist, there is likely an administrative block (e.g., you don't officially meet the prereqs, or are signed up for too many hours). Good to check with your advisor.
- Note that _instructors do not have the ability to move students off the waitlist directly_—we have to coordinate with the course administrators. We do periodically clear the waitlist, so again, please just hang tight if things aren't getting updated immediately.
- If you are adding the course late for any other reason, please make sure to:
- Review the slides/notes from the lectures you missed, which are linked from the [schedule](#schedule). If you have trouble understanding the material from the slides alone, the [Monte Carlo book by Owen](https://artowen.su.domains/mc/) provides all the essentials (and much more!).
- Complete the [assignments](#assignments) you missed. Like any other assignments, these are covered by the policy on [late days and dropped assignments](#latedays).
- Chat with your peers, the TAs, and the instructors in [office hours](#officehours), on [Discord, and on Discourse](#infrastructure) to help fill in the gaps in your understanding.
- Note that **instructors will not do one-on-one makeup sessions on missed material** (sorry!). But again, please take full advantage of the resources above, which should be enough to get you up to speed.
#### Collaboration Policy
- _Encouraged_ to work with anyone/everyone!
- Must write up final solutions _100% on your own_ (including code)
- e.g., erase the board, walk home, write up solutions
- **Copying any part of someone else’s solutions is considered cheating**
- any instance of cheating will result in an immediate “R” for the class
- both/all parties will be considered cheating, no questions asked
#### Grades
- **Weekly assignments** — 70%
- each assignment worth the same amount
- _can_ collaborate
- _can_ use late days & drops
- **Midterm & final** — 15% each
- cumulative
- _not_ collaborative
- _cannot_ use late days & drops
#### Accommodations for Students with Disabilities
If you have a disability and have an accommodations letter from the
Disability Resources office, I encourage you to discuss your
accommodations and needs with me as early in the semester as
possible. I will work with you to ensure that accommodations are
provided as appropriate. If you suspect that you may have a
disability and would benefit from accommodations but are not yet
registered with the Office of Disability Resources, I encourage you
to contact them at [access@andrew.cmu.edu](mailto:access@andrew.cmu.edu).
#### Student Wellness
As a student, you may experience a range of challenges that can
interfere with learning, such as strained relationships, increased
anxiety, substance use, feeling down, difficulty concentrating
and/or lack of motivation. These mental health concerns or stressful
events may diminish your academic performance and/or reduce your
ability to participate in daily activities. CMU services are
available, and treatment does work. You can learn more about
confidential mental health services available on campus
[here](http://www.cmu.edu/counseling). Support is always available
(24/7) from Counseling and Psychological Services: 412-268-2922.
**Date and time:** Tuesday / Thursday, 12:30am–1:50pm
**Units:** **9** (3 in-class/6 outside)
### Course Info
The Monte Carlo method uses random sampling to solve computational problems that would otherwise be intractable, and enables computers to model complex systems in nature that are otherwise too difficult to simulate. This course provides a first introduction to Monte Carlo methods from complementary theoretical and applied points of view, and will include implementation of practical algorithms. Topics include random number generation, sampling, Markov chains, Monte Carlo integration, stochastic processes, and applications in computational science. Students need a basic background in probability, multivariable calculus, and some coding experience in any language. Coding assignments will be done in [Python 🐍](https://www.python.org/).
**Key Topics:** definitions of randomness, random number generation, randomness testing and quality measures, curse of dimensionality, sampling and aliasing, Markov chains, Monte Carlo methods, stochastic processes, sample generation algorithms, applications of random numbers in computation
#### Course Overview
Random numbers are a basic tool for achieving robustness, scalability, and correctness in the design of algorithms. Moreover, randomness is an essential part of models used to describe the behavior of systems found throughout science, technology, and engineering. The Monte Carlo method in particular was recognized by SIAM as one of the [most important 10 algorithms of the 20th century](http://pi.math.cornell.edu/~web6140/). This course complements the existing curriculum, helping to better prepare students to apply randomness to problem solving in both academic and industrial settings.
The goal of this course is to enable students to identify situations where random sampling provides the best solution to a computational/algorithmic problem, and to train them in the practical implementation of associated methods. Students should also acquire the mathematical background needed to derive new algorithms from first principles, rather than purely applying existing techniques, and to analyze the correctness and efficiency of these algorithms. (For example, they should be able to determine whether a given Monte Carlo estimator is unbiased, and measure the empirical efficiency of such algorithms in terms of statistics such as variance.)
A secondary goal of this course is to expose students to a collection of application areas in computer science and the broader sciences where randomness can be profitably applied. In computer science, this set includes problems in computer systems/networking, programming languages, theoretical computer science, artificial intelligence/machine learning, and computer graphics. In the broader sciences, this includes partial differential equations arising in physics/chemistry/biology/etc., and stochastic models appearing in mathematical finance.
#### Learning Objectives
* Identify situations where random sampling provides the best solution to a computational/algorithmic problem.
* Implement the associated methods.
* Acquire the mathematical background needed to derive new algorithms from first principles.
* Analyze the correctness and efficiency of these algorithms.
* Become familiar with a collection of application areas in computer science and the broader sciences where randomness can be profitably applied.
#### Prerequisite Knowledge
_What prior knowledge must students have in order to be successful in this course?_
Students must have basic knowledge of coding (in any language), as well as basic knowledge of probability and multivariable calculus. CMU courses satisfy the prerequisites are listed below; please contact the instructors if you believe you've taken a different course that fulfills the requirement.
**Probability:** 15-259 or 21-325 or 36-218 or 36-219 or 36-225 or 36-235 or 18-465
**Multivariable Calculus:** 21-254 or 21-256 or 21-259 or 21-266 or 21-268 or 21-269
### Lectures
_[For slide-based lectures, lecture titles will link to slides. For chalkboard-based lectures, see the [brief lecture notes](https://www.math.cmu.edu/~gautam/c/2024-387/notes/index.html) and “live notes” taken in-class.]_
- **27 Aug (Tue)** —
[Introduction](https://www.math.cmu.edu/~gautam/c/2024-387/notes/01-intro.html), [Basic Sampling Algorithms](https://www.math.cmu.edu/~gautam/c/2024-387/notes/02-sampling.html) [[live notes](live-notes/Lecture01.pdf)]
- **29 Aug (Thu)** —
[Inversion and Rejection Sampling](https://www.math.cmu.edu/~gautam/c/2024-387/notes/02-sampling.html) [[live notes](live-notes/Lecture02.pdf)]
- **03 Sep (Tue)** —
[Introduction to Numerical Python](https://www.math.cmu.edu/~gautam/c/2024-387/notes/04-numpy.html) and [MCMC](https://www.math.cmu.edu/~gautam/c/2024-387/notes/05-mcmc.html) [[live notes](live-notes/Lecture03.pdf)]
- **05 Sep (Thu)** —
[Using Metropolis Hastings on the Ising Model](https://www.math.cmu.edu/~gautam/c/2024-387/notes/06-metropolis-hastings.html) [[live notes](live-notes/Lecture04.pdf)]
- **10 Sep (Tue)** —
[Markov Chains: Irreducibility, and Stationary Distributions](https://www.math.cmu.edu/~gautam/c/2024-387/notes/07-markov-chains.html) [[live notes](live-notes/Lecture05.pdf)]
- **12 Sep (Thu)** —
[Markov Chains: Aperiodicity, and TV convergence](https://www.math.cmu.edu/~gautam/c/2024-387/notes/07-markov-chains.html) [[live notes](live-notes/Lecture06.pdf)]
- **17 Sep (Tue)** —
[Markov Chains: Convergence to the Stationary Distribution](https://www.math.cmu.edu/~gautam/c/2024-387/notes/07-markov-chains.html) [[live notes](live-notes/Lecture07.pdf)]
- **19 Sep (Thu)** —
[Markov Chains: Page Rank, Ergodicity and Mixing](https://www.math.cmu.edu/~gautam/c/2024-387/notes/08-mixing-times.html) [[live notes](live-notes/Lecture08.pdf)]
- **24 Sep (Tue)** —
[Simulated Annealing and Tempering](https://www.math.cmu.edu/~gautam/c/2024-387/notes/10-simulated-annealing.html) [[live notes](live-notes/Lecture09.pdf)]
- **26 Sep (Thu)** —
[Traps near local minima](https://www.math.cmu.edu/~gautam/c/2024-387/notes/10-simulated-annealing.html) and [Detailed Balance](https://www.math.cmu.edu/~gautam/c/2024-387/notes/09-metropolis-hastings2.html) [[live notes](live-notes/Lecture10.pdf)]
- **01 Oct (Tue)** —
[Metropolis Hastings Revisited](https://www.math.cmu.edu/~gautam/c/2024-387/notes/09-metropolis-hastings2.html) [[live notes](live-notes/Lecture11.pdf)]
- **03 Oct (Thu)** —
Diffusion Models
- **08 Oct (Tue)** —
[Basic Monte Carlo Integration](slides/MCMA-FA24-BasicMonteCarloIntegration.pdf)
Definition of basic Monte Carlo estimator, bias vs. consistency, measures of quality, sample variance, convergence rate, examples.
- **10 Oct (Thu)** —
[Convergence of Monte Carlo Integration](slides/MCMA-FA24-ConvergenceOfMonteCarloIntegration.pdf)
Tail bounds, Markov's inequality, Chebyshev's inequality, weak law of large numbers, Fourier transform, characteristic functions, convolution
- **22 Oct (Tue)** —
[Variance Reduction I](slides/MCMA-FA24-VarianceReductionI.pdf)
definition of efficiency, control variates, stratified sampling
- **24 Oct (Thu)** —
[Variance Reduction II](slides/MCMA-FA24-VarianceReductionII.pdf)
importance sampling, quasi-Monte Carlo
- **29 Oct (Tue)** —
[Numerics and Random Numbers](slides/MCMA-FA24-NumericsRandomNumbers.pdf)
floating point, parallel implementation, measures of randomness pseudorandom number generators
- **31 Oct (Thu)** —
[Sample Generation](slides/MCMA-FA24-SampleGeneration.pdf)
special distributions, discrete distributions, alias table
- **07 Nov (Thu)** —
[Sample Generation II](slides/MCMA-FA24-SampleGeneration.pdf)
continuous distributions, inversion method, rejection method, resampling
- **12 Nov (Tue)** —
[Ordinary Differential Equations](slides/MCMA-FA24-SDEs.pdf)
ordinary differential equations (ODEs), numerical integrators (forward Euler, backward Euler, symplectic Euler), stability analysis
- **14 Nov (Thu)** —
[Stochastic Differential Equations](slides/MCMA-FA24-SDEs.pdf)
Brownian motion & diffusion processes, numerical integrators (Euler-Maruyama), application: molecular dynamics simulation
- **19 Nov (Tue)** —
[MCMC Algorithms](slides/MCMA-FA24-MCMCAlgorithmsI.pdf)
continuous state Markov chains, aperiodicity, irreducibility, detailed balance
- **21 Nov (Thu)** —
[Metropolis-Hastings](slides/MCMA-FA24-MCMCAlgorithmsI.pdf)
Metropolis-Hastings on continuous state space, convergence, burn-in
- **26 Nov (Tue)** —
[Langevin Monte Carlo](slides/MCMA-FA24-LangevinMonteCarlo.pdf)
statistical mechanics, entropy, Boltzmann distribution, underdamped/overdamped Langevin equation, Langevin Monte Carlo (LMC), Metropolis Adjusted Langevin Algorithm (MALA)
- **03 Dec (Tue)** —
Poisson Processes (Guest Lecturer: [Ioannis Gkioulekas](https://www.cs.cmu.edu/~igkioule/))
- **05 Dec (Thu)** —
Quantum Monte Carlo (Guest Lecturer: [Ryan O'Donnell](https://www.cs.cmu.edu/~odonnell/))
### Assignments
**All assignments are due at 11:30am Eastern time (NOT midnight!)**
A new one will post every week on Tuesday, unless announced otherwise.
The distribution of the scores on the homework can be found [here](https://www.math.cmu.edu/~mcm-cmu/2024/auth/)
- [Assignment 1](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw1.html), _due: Sep 3_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw1.html) and [detailed solutions by Thomas](https://www.math.cmu.edu/~gautam/c/2024-387/auth/sol1-thomas.pdf).
- [Assignment 2](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw2.html), _due: Sep 10_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw2.html).
- [Assignment 3](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw3.html), _due: Sep 17_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw3.html).
- [Assignment 4](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw4.html), _due: Sep 24_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw4.html).
- [Assignment 5](https://www.math.cmu.edu/~gautam/c/2024-387/hw/hw5.html), _due: Oct 1_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/hw5.html).
- [Midterm](https://www.math.cmu.edu/~gautam/c/2024-387/hw/midterm.html), _due: Oct 8_. [brief solutions](https://www.math.cmu.edu/~gautam/c/2024-387/auth/midterm.html)
- [Assignment 6](assignments/Assignment06.pdf), _due: Oct 22_.
- [Assignment 7](assignments/Assignment07.pdf), _due: Nov 1_.
- [Assignment 8](assignments/Assignment08.pdf) [[code]](assignments/Assignment08-code.zip), _due: Nov 8_.
- [Assignment 9](assignments/Assignment09.pdf) [[code]](assignments/Assignment09-code.zip), _due: Nov 26_.
- [Final](final/MCMA-Final-2024.pdf) [[data]](final/GSPC.csv), _due: Friday, Dec 13 at 5pm EST_. [solutions](final/MCMA-Final-2024-Solutions.pdf)
### Resources
#### Office Hours
- Mon 3:00–4:50PM **TA** Mario Tutuncu-Macias (room Citadel Teaching Commons)
- Mon 5:00–6:50PM **TA** Jiannan Jiang (Wean 6213)
- Wed 3:00–4:50PM **Instructor** Keenan Crane (Smith 217)
- Thu 3:00–4:50PM **Instructor** Gautam Iyer (Wean 8115)
- Fri 3:00–4:50PM **TA** Thomas Horstkamp (Wean 7215)
#### Infrastructure
- **General announcements** — sent via [email](https://lists.andrew.cmu.edu/mailman/listinfo/math-cs-montecarlo).
- **Discussion** — via the [CMU Math Discourse server](https://zym.math.cmu.edu/c/f2024-387). You will need to log in via your AndrewID to post.
- **Live chat** — via the [Monte Carlo CMU FA23](https://www.math.cmu.edu/~mcm-cmu/2024/auth/) Discord server.
If you joined late, please [add yourself to the mailing list](https://lists.andrew.cmu.edu/mailman/listinfo/math-cs-montecarlo), and email the instructors your Andrew ID.
This will allow you access to the [private website](https://www.math.cmu.edu/~mcm-cmu/2024/auth/) which contains the Gradescope code, Discord server link and solutions.
#### Notes and References
##### Notes
- [Lecture notes for black board lectures](https://www.math.cmu.edu/~gautam/c/2024-387/notes/index.html) (This only contains statements of important results from the blackboard lectures by Gautam; explanations, motivation and proofs will be done in class and are not in these notes.)
- [Lecture notes from 2023](https://www.math.cmu.edu/~gautam/c/2024-387/pdfs/mc.pdf) (This is roughly what Gautam covered in half of the 2023 version of this course. Again this only contains statements and definitions; the motivation / proofs were done in class.)
##### Recommended References
- [A First Course in Monte Carlo Methods](https://arxiv.org/pdf/2405.16359), D. Sanz-Alonso, O. Al-Ghattas.
- [Monte Carlo Theory, Methods and Examples](https://artowen.su.domains/mc/), Art Owen
- [Markov Chains](https://www.statslab.cam.ac.uk/~james/Markov/), James Norris
- [Physically Based Rendering](https://www.pbr-book.org/) _Chapters 13 & 7_, Pat Hanrahan, Greg Humphreys, Wenzel Jakob, Matt Pharr
- [Robust Monte Carlo Methods for Light Transport Simulation](http://graphics.stanford.edu/papers/veach_thesis/) _Chapters 2 & 11_, Eric Veach
##### Past semesters
- [Monte Carlo Methods and Applications FA2023](mcma-fa2023.html)
### Course Policies
#### Assignments & Submission
- Weekly short assignments, typically assigned Tuesday and due the following Tuesday.
- **Written exercises**
- all work must be submitted digitally (_no paper!_)
- either typeset (via [LaTeX](https://www.overleaf.com/learn/latex/Learn_LaTeX_in_30_minutes)) or scans/photos of written work
- **Coding exercises**
- all coding is in [Python 🐍](https://www.python.org/)
- Python is **not** a prerequisite, but you should have _some_ coding experience (in any language)
- Submit via [Gradescope](https://www.gradescope.com/courses/830878), `21387` in the *Math* department.
- If you joined late, email us your Andrew ID.
We will give you access to the [private website](https://www.math.cmu.edu/~mcm-cmu/2024/auth/), which contains the Gradescope code required to add yourself to Gradescope.
#### Late Days & Dropped Assignments
- Assignments due at 11:30 am Eastern time on due date (one hour before class starts)
- **11:30 am is not midnight!** 🤪
- Two assignments can be dropped without penalty
- if you don’t drop any, we’ll just take best N-2 scores
- Can use five late days throughout semester, and turn in up to five assignments 24h late.
- _if no more late days remain, late work gets a zero!_
- Late days & drops _already_ account for sick days, late adds, job interviews, conference travel, etc.
- Cannot be used for midterm & final
- Please don’t bug TAs/instructors about extra late days and drops! 🥵
#### Waitlist & Late Add
- Don't be fooled by the waitlist: we have _never once_ had a situation where an eligible student has not ultimately been able to get a spot in the class. The room is big, and people inevitably drop. Please just hang in there.
- If you're on the waitlist and hope to join the class, **please still show up to lecture, and complete / hand in the assignments!** Doing so will only make life easier once you are officially enrolled in the class.
- If there are free spots in the class but you're still stuck on the waitlist, there is likely an administrative block (e.g., you don't officially meet the prereqs, or are signed up for too many hours). Good to check with your advisor.
- Note that _instructors do not have the ability to move students off the waitlist directly_—we have to coordinate with the course administrators. We do periodically clear the waitlist, so again, please just hang tight if things aren't getting updated immediately.
- If you are adding the course late for any other reason, please make sure to:
- Review the slides/notes from the lectures you missed, which are linked from the [schedule](#schedule). If you have trouble understanding the material from the slides alone, the [Monte Carlo book by Owen](https://artowen.su.domains/mc/) provides all the essentials (and much more!).
- Complete the [assignments](#assignments) you missed. Like any other assignments, these are covered by the policy on [late days and dropped assignments](#latedays).
- Chat with your peers, the TAs, and the instructors in [office hours](#officehours), on [Discord, and on Discourse](#infrastructure) to help fill in the gaps in your understanding.
- Note that **instructors will not do one-on-one makeup sessions on missed material** (sorry!). But again, please take full advantage of the resources above, which should be enough to get you up to speed.
#### Collaboration Policy
- _Encouraged_ to work with anyone/everyone!
- Must write up final solutions _100% on your own_ (including code)
- e.g., erase the board, walk home, write up solutions
- **Copying any part of someone else’s solutions is considered cheating**
- any instance of cheating will result in an immediate “R” for the class
- both/all parties will be considered cheating, no questions asked
#### Grades
- **Weekly assignments** — 70%
- each assignment worth the same amount
- _can_ collaborate
- _can_ use late days & drops
- **Midterm & final** — 15% each
- cumulative
- _not_ collaborative
- _cannot_ use late days & drops
#### Accommodations for Students with Disabilities
If you have a disability and have an accommodations letter from the
Disability Resources office, I encourage you to discuss your
accommodations and needs with me as early in the semester as
possible. I will work with you to ensure that accommodations are
provided as appropriate. If you suspect that you may have a
disability and would benefit from accommodations but are not yet
registered with the Office of Disability Resources, I encourage you
to contact them at [access@andrew.cmu.edu](mailto:access@andrew.cmu.edu).
#### Student Wellness
As a student, you may experience a range of challenges that can
interfere with learning, such as strained relationships, increased
anxiety, substance use, feeling down, difficulty concentrating
and/or lack of motivation. These mental health concerns or stressful
events may diminish your academic performance and/or reduce your
ability to participate in daily activities. CMU services are
available, and treatment does work. You can learn more about
confidential mental health services available on campus
[here](http://www.cmu.edu/counseling). Support is always available
(24/7) from Counseling and Psychological Services: 412-268-2922.