## 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.

**Contents**

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

**Time/Place**

**Winter Term**

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

**Format**

2 SWS lecture, 1 SWS exercise, 1 SWS tutorial, self-study

5 credits

**Exam**

**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

Teachers

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)

**Suggested Literature**

Feller - an introduction to probability theory and its applications, Wiley+Sons, 1957.

Robert & Casella - Monte Carlo statistical methods, Springer, 2004.