Stochastics and Probability

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) ONLINE / FIRST LECTURE: OCT 26, 2020
Exercises / Tutorials: Thursdays, 4. DS (13:00-14:30) ONLINE / FIRST TUTORIAL: OCT 29, 2020

LECTURES AND EXERCISES WILL BE ENTIRELY ONLINE FOR THE WHOLE SEMESTER. They will be held as Zoom live screen-casts with the possibility to ask questions. Links are recurrent as announced here below. In order to keep this as close as possible to a real lecture experience, the webcasts are not recorded.

Webcast link for the lectures (recurrent, same every week): https://us02web.zoom.us/j/87139465557?pwd=T0lkZUxkZ3BlY3dvdlJINGdVUjErUT09
Meeting ID: 871 3946 5557
Password: 450939

Webcast link for the exercise tutorials (recurrent, same every week): https://us02web.zoom.us/j/89261901326?pwd=WjV5aHlvK3V6L2pxVVNHdkRoL0F1dz09
Meeting ID: 892 6190 1326
Password: 973872


Format

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

5 credits


Exam

In presence in February or March 2021. Date and place to be announced.

Since there are more than 10 registered students, module examination consists of a written examination in presence with a duration of 90 minutes.

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)
Items not adhering to these guidelines will be confiscated in their entirety at the beginning of the exam.


Grade scale:

All exams are graded in absolute terms w.r.t. the following pre-defined grade scale that remains constant over the years:

  • The top grade of 1.0 is reached with 80% of the maximum possible points
  • Half of that, i.e., 40% of the maximum possible points, are required to pass
  • Below 40%, or no-show, is a fail.
Between the top grade and the passing threshold, the grading scale is linear. In the end, grades are rounded to the nearest allowed grade according to the exam regulations: 1.0, 1.3, 1.7, 2.0, 2.3, 2.7, 3.0, 3.3, 3.7, 4.0, 5.0. The grades 0.7, 4.3, and 4.7 are not allowed. Any grade above 4.1 is a fail (see exam regulations). The maximum number of points that can be reached in the exam is given by the number of minutes the exam lasts (i.e., a 90 minute exam yields maximum 90 points). Points are distributed amongst the exam questions to reflect the number of minutes a good student would need to solve the problem. This provides some guidance for your time management in the exam. In order to reduce the risk of correction mistakes, all exams are checked by at least two independent, qualified assessors (typically professors or teaches with officially conferred examination rights). The exam review session (see below) is for you to come look at your exam paper and report correction mistakes you found.


Exam Review winter term 2019/20

You can come and look at your exam and ask questions about its correction and the answers given during the exam review times. Due to the current travel and contact restrictions, we offer three exam review dates: one in June, one during the summer break, and one around the beginning of the winter semester 2020/21:

  • June 18, 2020, 2pm, Outdoors at the pond between the BAR building and the Mensa (Maps Link). The review only takes place if there is no rain. In case of rain, a new date will be found. In order to participate, You MUST wear a face mask and you are only allowed to come forward one by one.
  • July 20, 2020, 2pm, Outdoors in the seating area in front of the Center for Systems Biology Dresden, Pfotenhauerstr. 108 (Maps Link). The review only takes place if there is no rain. In case of rain, a new date will be found. In order to participate, You MUST wear a face mask and you are only allowed to come forward one by one.
  • October 19, 2020, 2pm, Outdoors in the seating area in front of the Center for Systems Biology Dresden, Pfotenhauerstr. 108 (Maps Link). The review only takes place if there is no rain. In case of rain, a new date will be found. In order to participate, You MUST wear a face mask and you are only allowed to come forward one by one.
IMPORTANT: All students attending an exam review must fill in and sign the exam review form they are going to receive during the review. Undocumented exam reviews are not permitted. You must participate in person.


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: Rushikesh Shinde


Instruction language: ENGLISH


Lecture notes are available as PDF here.
Below is the weekly syllabus and the exercise/solution handouts:

  • Oct 26, 2020: Lecture 1 (Sbalzarini) - Probability refresher, conditional probabilities, Bayes' rule, random variables, discrete and continuous probability distributions, scale-free distributions (Blackboard 01 PDF, Exercise 01 PDF, Tutorial Notes PDF, Solution 01 PDF, Solution Jupyter Notebook)
  • Nov 2, 2020: 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 (Blackboard 02 PDF, Exercise 02 PDF, Solution 02 PDF, Solution Jupyter Notebook)
  • Nov 9, 2020: Lecture 3 (Sbalzarini) - Discrete-time stochastic processes, discrete Markov chains and their matrix (Blackboard 03 PDF, Exercise 03 PDF, Solution 03 PDF, Solution Jupyter Notebook)
  • Nov 16, 2020: Lecture 4 (Sbalzarini) - Law of large numbers, Monte Carlo methods, example: MC integration, importance sampling (Blackboard 04 PDF, Exercise 04 PDF, Solution 04 PDF, Solution Jupyter Notebook)
  • Nov 23, 2020: Lecture 5 (Zechner) - Monitoring variance, variance reduction (Exercise 05 PDF)
  • Nov 30, 2020: Lecture 6 (Zechner) - Rao-Blackwell, Markov Chain Monte Carlo (MCMC), detailed balance, convergence criteria, acceleration methods
  • Dec 7, 2020: Lecture 7 (Zechner) - Classic MCMC samplers 1: Gibbs sampling
  • Dec 14, 2020: Lecture 8 (Zechner) - Classic MCMC samplers 2: Metropolis-Hastings, convergence dagnostics, stopping conditions
  • Jan 4, 2020: Lecture 9 (Sbalzarini) - Monte-Carlo optimization: stochastic gradient descent, simulated annealing, evolution strategies, CMA-ES
  • Jan 11, 2021: Lecture 10 (Zechner) - Random Walks, Brownian motion in 1,2,3,n-dim, connection to diffusion, continuum limit of random walks
  • Jan 18, 2021: Lecture 11 (Zechner) - Stochastic calculus, Ito calculus, Ornstein-Uhlenbeck process (analytical)
  • Jan 25, 2021: Lecture 12 (Sbalzarini) - numerical methods for SDE: Euler-Maruyama, Milstein, strong and weak convergence
  • Feb 1, 2021: Lecture 13 (Zechner) - Master equation, Fokker-Planck, Kolmogorov forward, Example: chemical kinetics
  • Optional: Lecture 14 (Sbalzarini) - Graphical representation and classification of reaction networks, exact stochastic simulation algorithms: first-reaction method, direct method
Suggested Literature

Feller - an introduction to probability theory and its applications, Wiley+Sons, 1957.
Robert & Casella - Monte Carlo statistical methods, Springer, 2004.