Stochastic Modeling and Simulation
Upon completing the module, the students master the basics of stochastic modelling and simulation. We first discuss discrete-time models, followed by two classic examples, and then continuous-time models.
Conditional probabilities, normal distributions, and scale-free distributions; Markov chains and their matrix representation, mixing times and Perron-Frobenius theory; Applications of Markov chains, such as the PageRank algorithm; Monte Carlo Methods: Convergence, Law of Large Numbers, Variance Reduction, Importance Sampling, Markov Chains Monte-Carlo Using Metropolis-Hastings & Gibbs Samplers; Random processes and Brownian motion: properties in 2, 3 and more dimensions, connection to the diffusion equation, Levy processes and anomalous diffusion; Stochastic differential equations (SDEs): Nonlinear transformations of Brownian motion (Ito calculus), Ornstein-Uhlenbeck process and other solvable equations; Examples from population dynamics, genetics, protein kinetics, etc.; Numerical simulation of SDEs: strong and weak error, Euler-Maruyama scheme, Milstein scheme.
Program / Module
M.Sc. Computational Modeling and Simulation
Module: CMS-COR-SAP - Stochastics and Probability
Lecture: Mondays, 4. DS (13:00-14:30) in APB-E008 (computer science building) / FIRST LECTURE: OCT 8
Exercises / Tutorials: Thursday, 5.DS (14:50 - 16:20) in APB-E009/U
2 SWS lecture, 1 SWS exercise, 1 SWS tutorial, self-study
Wednesday, February 20, 2019, 09:20-10:50h, CHE/089/E (chemistry building)
If there are more than 10 registered students, the module examination consists of a written examination, with a duration of 90 minutes. If there are 10 or fewer registered students, it consists of an oral examination as an individual examination performance amounting to 30 minutes; this will be announced to the enrolled students at the end of the enrollment period.
At the exam, the following may be used:
- 4 A4 sheets (8 pages if you print duplex) of hand-written summary. We recommend writing the summary by hand, but it can also be machine-written. In the latter case, the font size must be 8 points or larger throughout.
- A standard pocket calculator (devices with network or bluetooth access, as well as devices capable of storing and displaying documents are not allowed)
Registration to the course
For students of the Master program "Computational Modeling and Simulation: via CampusNet SELMA
For students of the Computer Science programs: via jExam
Lecture: Prof. Ivo F. Sbalzarini & Dr. Christoph Zechner
Exercises: David Gonzales
Teaching language: ENGLISH
Lecture notes are available as PDF here.
Below is the weekly syllabus and the exercise/solution handouts:
- Lecture 1 (Sbalzarini) - Probability refresher, conditional probabilities, Bayes' rule, random variables, discrete and continuous probability distributions, scale-free distributions (Lecture Notes PDF, Exercise 1 PDF, Solution 1 PDF)
- Lecture 2 (Sbalzarini) - transformation of random variables, pseudo- and quasi-random numbers, low discrepancy sequences, transformation algorithms: inversion, Box-Muller, accept-reject method, composition-rejection method (Lecture Notes PDF, Exercise 2 PDF, Solution 2 PDF)
- Lecture 3 (Sbalzarini) - Discrete-time stochastic processes, discrete Markov chains and their matrix (Lecture Notes PDF, Exercise 3 PDF, Solution 3 PDF)
- Lecture 4 (Zechner) - Law of large numbers, Monte Carlo methods, example: MC integration, importance sampling (Lecture Notes PDF, Exercise 4 PDF, Solution 4 PDF)
- Lecture 5 (Zechner) - Monitoring variance, variance reduction (Lecture Notes PDF, Exercise 5 PDF, Solution 5 PDF)
- Lecture 6 (Zechner) - Rao-Blackwell, Markov Chain Monte Carlo (MCMC), detailed balance, convergence criteria, acceleration methods (Lecture Notes PDF, Exercise 6 PDF, Solution 6 PDF)
- Lecture 7 (Zechner) - Classic MCMC samplers 1: Gibbs sampling (Lecture Notes PDF, Exercise 7 PDF, Solution 7 PDF)
- Lecture 8 (Sbalzarini) - Classic MCMC samplers 2: Metropolis-Hastings, convergence dagnostics, stopping conditions (Lecture Notes PDF, Exercise 8 PDF, Solution 8 PDF)
- Lecture 9 (Sbalzarini) - Monte-Carlo optimization: stochastic gradient descent, simulated annealing, evolution strategies, CMA-ES (Lecture Notes PDF, Exercise 9 PDF, Solution 9 PDF)
- Lecture 10 (Zechner) - Random Walks, Brownian motion in 1,2,3,n-dim, connection to diffusion, continuum limit of random walks (Lecture Notes PDF, Exercise 10 PDF, Solution 10 PDF)
- Lecture 11 (Zechner) - Stochastic calculus, Ito calculus, Ornstein-Uhlenbeck process (analytical) (Lecture Notes PDF, Exercise 11 PDF, Solution 11 PDF)
- Lecture 12 (Sbalzarini) - numerical methods for SDE: Euler-Maruyama, Milstein, strong and weak convergence (Lecture Notes PDF, Exercise 12 PDF, Solution 12 PDF)
- Lecture 13 (Zechner) - Master equation, Fokker-Planck, Kolmogorov forward, Example: chemical kinetics (Lecture Notes PDF, Exercise 13 PDF, Solution 13 PDF)
- Lecture 14 (Sbalzarini) - Graphical representation and classification of reaction networks, exact stochastic simulation algorithms: first-reaction method, direct method. (Lecture Notes PDF, Exercise 14 PDF, Solution 14 PDF)
Feller - an introduction to probability theory and its applications, Wiley+Sons, 1957.
Robert & Casella - Monte Carlo statistical methods, Springer, 2004.