Monte Carlo Methods and Applications Course ID 15627 Description 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. 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 Required Background Knowledge 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. Course Relevance 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. Yet foundational and practical aspects of such methods are not currently covered in depth by any course at CMU. This course complements the existing curriculum, helping to better prepare students to apply randomness to problem solving in both academic and industrial settings. Course Goals 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.) Learning Resources The primary resource for the course are a collection of course notes written by the instructors. Students will also be given ancillary references to classic texts (e.g., Øksendal and Pharr et al). Assessment Structure The assessment breakdown is as follows: (37%) written exercises (37%) coding assignments (20%) final project (6%) class participation There will be four (4) assignments over the first half of the semester, which help establish an understanding of basic principles and how they are applied computationally. A final project during the second half of the semester enables students to go deeper in one particular application area of interest---we will suggest a variety of projects, but students are free to design their own. Each assignment is comprised of complementary written and coding components. Written exercises guide students through derivation of basic knowledge needed to develop and implement algorithms in the coding part. To help make the course accessible to non-CS majors, coding exercises will be carried out in Python, via web-based Jupyter notebooks. For the final project, students will implement an existing algorithm in their chosen topic area; more ambitious students are encouraged to think about how to improve on existing algorithms. In addition to an implementation, the final report for each project must include a writeup that motivates the problem, describes the algorithmic solution and any relevant implementation details, provides plots/data that verify correctness of the implementation, and visualizes results of running the algorithm. The course also encourages student-instructor and student-student engagement with material through in-class discussions, as well as discussions through Piazza and a private class Discord; activity in these settings will be used to evaluate the class participation grade. Extra Time Commitment The main extra time commitments are written/coding exercises, and studying for midterm/final exams. The estimated number of out-of-class hours is four hours/week. Course Link http://www.cs.cmu.edu/~kmcrane/random/
