392170 Algorithmic stochastics (V) (WiSe 2025/2026)

Several complex problems arising from biology and computer science (e.g., sequence alignment, gene finding, inference for population sequence data) cannot be solved efficiently and optimally at the same time using deterministic methods. In such cases stochastic methods can be used to make computations feasible and still provide good results.

Building on the foundations of probability theory and statistics, this course lays the basis for stochastic computing (i.e., representation of distributions in the computer, computations with small probabilities, efficient generation of random numbers with given distribution, test of the quality of random number generators). As an important tool, Markov chain Monte Carlo (MCMC) methods are presented via examples (Metropolis-Hastings, Gibbs sampling). Importance sampling methods and simulation of rare events are discussed as well.

Requirements for participation, required level

Basic knowledge of probability theory (stochastics) on the level taught in the Computer Science Bachelor's probability theory and statistics lecture (24-M-INF4 Mathematik für Informatik 4) is strongly recommended. This includes (discrete and continuous probability) distributions, random variables, independence, expectations, variance, joint and conditional distributions.