This website is for FALL 2023.
The most recent version is at math.cmu.edu/~mcm-cmu
**[geometry.cs.cmu.edu/montecarlo](http://geometry.cs.cmu.edu/montecarlo)**
[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:** Scott Hall (SH) 105
**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 link to slides. For chalkboard-based lectures, “blackboard notes” link to a lecture outline written ahead of time, and “live notes” link to notes taken (live) in class that flesh out the details of proofs, etc.]_
- **29 Aug (Tue)** —
[Overview](slides/Lecture01-Overview-CMUMonteCarloFA23.pdf)
broad picture of Monte Carlo methods, historical comments, motivating applications, problems with deterministic sampling, course outline framed via Monte Carlo estimator
- **31 Aug (Thu)** —
[Monte Carlo Integration I](slides/Lecture02-BasicMonteCarlo-CMUMonteCarloFA23.pdf)
Review of basic probability, definition of Monte Carlo estimator, bias vs. consistency, measures of quality, sample variance, convergence rate, numerical demonstrations.
- **05 Sep (Tue)** —
Coding Monte Carlo Methods:
[1st example](first-mc-example.html) ([download](first-mc-example.ipynb)),
[Fun 2nd example](substitution-cipher.html)
setting up Python, implementing basic Monte Carlo methods, estimating &mpi;, evaluating sample variance/RMSE
- **07 Sep (Thu)** —
Monte Carlo Integration II ([§2 in blackboard notes](pdf/mc.pdf))
Cost of quadrature / Monte Carlo integration, variance estimates, law of large numbers, central limit theorem
- **12 Sep (Tue)** —
[Variance Reduction I](slides/Lecture05-VarianceReduction-CMUMonteCarloFA23.pdf)
definition of efficiency, control variates, stratified sampling, importance sampling, quasi-Monte Carlo
- **14 Sep (Thu)** —
[Variance Reduction II](slides/Lecture05-VarianceReduction-CMUMonteCarloFA23.pdf)
uniform sampling, pseudorandom number generation, tests of randomness, sampling discrete distributions (CDF, inversion)
- **19 Sep (Tue)** —
[Sample Generation](slides/Lecture06-BasicSampleGeneration-CMUMonteCarloFA23.pdf)
, sampling continuous distributions, special distributions (normal, exponential), rejection sampling, stratified sampling, curse of dimensionality revisited
- **21 Sep (Thu)** —
Introduction to Markov Chain Monte Carlo
([§3.1, §3.2 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture08-MCMC-intro/Lecture08-MCMC-intro.pdf))
Examples of sampling in high dimensions, the Metropolis-Hastings algorithm
- **26 Sep (Tue)** —
Markov Chains I
([§3.2, §3.3.1 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture09-MarkovChainsI/Lecture09.pdf))
Markov chains, stationary distribution, irreducibility
- **28 Sep (Thu)** —
Markov Chains II
([§3.3.2, §3.3.3 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture10-MarkovChainsII/Lecture10.pdf))
Aperiodicity, convergence, detailed balance, Metropolis chains
- **03 Oct (Tue)** —
[Stochastic Differential Equations I](slides/Lecture11-StochasticDifferentialEquations-CMUMonteCarloFA23.pdf)
ordinary differential equations (ODEs), Brownian motion & basic properties, drifted motion, basic stochastic differential equations (SDEs), numerical integrators (forward Euler, Euler-Maruyama), application: molecular dynamics simulation
- **05 Oct (Thu)** —
[Partial Differential Equations](slides/Lecture12-PDEsStochasticProcesses-CMUMonteCarloFA23.pdf)
definition of PDEs, elliptic/parabolic/hyperbolic, linearity, order, boundary conditions, finite difference methods
- **10 Oct (Tue)** —
[PDEs & Stochastic Processes](slides/Lecture12-PDEsStochasticProcesses-CMUMonteCarloFA23.pdf)
connections between random walks and PDEs, Feynman-Kac representation, Fokker-Planck equation
- **10 Oct (Tue)** —
Stochastic Calculus 1
([§4.1, §4.2 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture14-StochasticCalculusI/Lecture14.pdf))
Introduction, Brownian Motion
- **12 Oct (Thu)** —
Stochastic Calculus 2
([§4.2, §4.3 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture15-StochasticCalculusII/Lecture15.pdf))
Itô integrals
- **24 Oct (Tue)** —
Stochastic Calculus 3
([§4.4, §4.5 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture16-StochasticCalculusIII/Lecture16.pdf))
Itô formula
- **26 Oct (Thu)** —
Stochastic Calculus 4
Joint quadratic variation, and intuition behind Itô's formula
([§4.5 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture17-StochasticCalculusIV/Lecture17.pdf))
- **31 Oct (Tue)** —
Stochastic Differential Equations
([§4.6 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture18/Lecture18.pdf))
Diffusions, generators, connections to PDEs
- **02 Nov (Thu)** —
Stochastic Differential Equations II
([§4.6 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture19/Lecture19.pdf))
Kolmogorov forward / backward equations
- **09 Nov (Thu)** —
Algorithms in High Dimensions I
([§4.7 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture20/Lecture20.pdf))
Langevin Monte Carlo (LMC), Metropolis Adjusted Langevin Monte Carlo (MALA).
- **14 Nov (Tue)** —
[Simulated Annealing and Applications](notes/simulated-annealing)
([§5 in blackboard notes](pdf/mc.pdf),
[live notes](notes/Lecture21/Lecture21.pdf))
Simulated Annealing
- **16 Nov (Thu)** —
[Walk on Spheres I](slides/Lecture22-WalkOnSpheresI-CMUMonteCarloFA23.pdf) ([video](https://www.youtube.com/watch?v=bZbuKOxH71o))
Basic walk on spheres algorithm, hitting time, Kakutani's principle, motivation & challenges in solving geometrically complicated PDEs
- **21 Nov (Tue)** —
[Walk on Spheres II](slides/Lecture23-WalkOnSpheresII-CMUMonteCarloFA23.pdf)
Walk on X algorithms, stochastic processes beyond Brownian motion, potential theory, boundary integral equation, derivative estimators, Bessel process, parabolic PDEs, reflecting Brownian motion & Neumann boundary conditions, walk on stars, variable coefficients, acceleration techniques, applications in geometry processing & physical simulation
- **28 Nov (Tue)** —
Guest Lecture ([Xiaoyue Cui and Maureen Stolzer](http://www.cs.cmu.edu/~durand/Lab/personnel2.html)): [MCMC Protein Evolution](slides/Lecture24-ProteinEvolution-CMUMonteCarloFA23.pdf)
- **30 Nov (Thu)** —
Guest Lecture ([Ioannis Gkioulekas](https://www.cs.cmu.edu/~igkioule/)): Rendering & Computational Imaging ([live notes](notes/Lecture25/Lecture25.pdf))
- **05 Dec (Tue)** —
Guest Lecture ([Gilbert Bernstein](http://www.gilbertbernstein.com/)): Probabilistic Programming Languages
- **07 Dec (Thu)** —
Guest Lecture ([Jun-Yan Zhu](https://www.cs.cmu.edu/~junyanz/)): Generative Image Synthesis
### Assignments
**All assignments are due at 10:30am Eastern time (NOT midnight!)**
The distribution of the scores on the homework can be found [here](https://www.math.cmu.edu/~mcm-cmu/auth/)
- [Assignment 1](assignments/Assignment01.html) _(due date: TBD at 10:30am)_ — Getting Set Up
- [Assignment 2](assignments/Assignment02.html) _(due date: TBD at 10:30am)_ — Monte Carlo Integration [[solutions]](https://www.math.cmu.edu/~mcm-cmu/auth/Assignment02-SolutionsForStudents.html)
- [Assignment 3](assignments/Assignment03.html) _(due date: TBD at 10:30am)_ — Variance Reduction
- [Assignment 4](assignments/Assignment04.html) _(due date: TBD at 10:30am)_ — Sample Generation
- [Assignment 5](assignments/Assignment05.html) _(due date: TBD at 10:30am)_ — Markov Chain Monte Carlo
- [**Midterm**](midterm/midterm-fa2023.html) [[solutions]](midterm/midterm-fa2023-solutions.html) _(due date: TBD at 10:30am)_
- [Assignment 6](assignments/Assignment06.html) _(due date: TBD at 10:30am)_ - Deterministic & Stochastic Differential Equations
- [Assignment 7](assignments/Assignment07.html) _(due date: TBD at 10:30am)_ - Itô integrals [[solutions]](https://www.math.cmu.edu/~mcm-cmu/auth/Assignment07.html)
- [Assignment 8](assignments/Assignment08.html) _(due date: TBD at 10:30am)_ - Diffusions / LMC [[solutions]](https://www.math.cmu.edu/~mcm-cmu/auth/Assignment08.html)
- [Assignment 9](assignments/Assignment09.html) _(due date: TBD at 10:30am)_ - Diffusions / Stationary distributions [[solutions]](https://www.math.cmu.edu/~mcm-cmu/auth/Assignment09.html)
- [Assignment 10](assignments/Assignment10.html) _(due date: TBD at 10:30am)_ - Simulated Annealing
- Assignment 11 - [[written]](assignments/Assignment11.pdf) [[coding]](assignments/Assignment11.html) _(due date: TBD at 10:30am)_ - Walk on Spheres
- **Final** _(due date: TBD at 10:30am on Gradescope)_
* [Written](final/MCMA-Final-2023.pdf) [[solutions]](final/MCMA-Final-2023-Solutions.pdf)
* [Coding](final/mcmc-generate-words.html) [[stripped-down version]](final/mcmc-generate-words-stripped.ipynb) [[data file]](final/frequencies.npz) [solutions](final/mcmc-generate-words.ipynb)
### Resources
#### Office Hours
- **Instructor** Gautam Iyer — office hours TBD
- **Instructor** Keenan Crane — office hours TBD
- **TA** TBD — office hours TBD
- **TA** TBD — office hours TBD
- **TA** TBD — office hours TBD
- **TA** TBD — office hours TBD
#### Infrastructure
- **General announcements** — sent via email. If you joined late, please [add yourself to the mailing list](https://lists.andrew.cmu.edu/mailman/listinfo/math-cs-montecarlo).
- **Discussion** — via the [CMU Math Discourse server](https://zym.math.cmu.edu/c/f2023-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/auth/) Discord server.
#### Notes and References
##### Notes
- [Lecture notes for black board lectures](pdf/mc.pdf) (This only contains statements of important results from the blackboard lectures by Gautam; explanations, motivations and proofs will be done in class and are not in these notes.)
##### Recommended References
- [Monte Carlo Theory, Methods and Examples](https://artowen.su.domains/mc/), Art Owen
- Simulation and the Monte Carlo Method by Rubinstein and Kroese.
- [Markov Chains](https://www.statslab.cam.ac.uk/~james/Markov/), James Norris
- [Stochastic Differential Equations](https://link.springer.com/book/10.1007/978-3-642-14394-6), Bernt Øksendal
- [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/592187), `21387` in the *Math* department.
- If you joined late, add yourself to Gradescope using the code [here](https://www.math.cmu.edu/~mcm-cmu/auth/)
#### Late Days & Dropped Assignments
- Assignments due at 10:30 am Eastern time on due date (one hour before class starts)
- **10: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
- _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
- **Take-home 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.