MS-C2111 - Stochastic Processes, Lecture, 23.10.2023-13.12.2023

Topic outline

• Course Log
  Lectures are held in lecture room D (Y122). There are now 12 chapters of the updated lecture notes available. Please let Eveliina know if there are some misprints, mistakes, of confusion in the lecture notes!
  

  
  

  What has been going on? Here will appear Lecture topics & Additional materials:
  

  Lecture 1 (23.10.): Chapter 1 in Lecture notes (similar to old Lecture notes)

  • Markov chains (MC, X) & Markov property
  • Transition matrix (P), transition diagram 
  • Examples (weather; more examples in exercises!)
  • Distribution (\mu_t), computing it using powers of transition matrix P
  • Transition probabilities for many steps / given path
  • Occupancy matrix (G): expected time spent in one state, see exercises and Lecture 3

  
  

  Additional material: Some example Mathematica codes (NB: the syntax is very specific to Wolfram Mathematica -- don't try to use as such elsewhere...):
  

  • Predicting weather (nb)
    
  • Path probabilities (nb)
  • Occupancy matrix (nb)
  • Simple weather simulation (nb)

  
  

  Lecture 2 (25.10.): Chapter 2 in Lecture notes (similar to old Lecture notes)
  

  • Limit distribution (\mu_\infty)
  • Invariant distribution (\pi), balance equations 
  • Limit distribution is also invariant distribution
  • When does limit distribution exist?
  • Irreducibility and aperiodicity
  • Irreducible MC has unique invariant distribution
  • Irreducible and aperiodic MC has unique limit distribution that is also its unique invariant distribution
  • (NB. We assume MC has finite state space)

  
  

  Additional material: Some example Mathematica codes:
  

  • Brand loyalty model (nb)
  • Ehrenfest model (nb)
  • Getting stuck (nb)
  • General example (nb)

  
  

  Lecture 3 (30.10.): Chapter 3 in Lecture notes (has the same content as old Lecture notes differently written)

  • Ergodicity for irreducible MC's: time-averages become space-averages in the long run
  • Ergodicity of long-term time-averages (ergodic theorem)
  • Ergodicity of long-term relative frequencies
  • Cost models: Markov additive processes
  • Ergodicity for Markov additive processes 
    

  
  

  Additional material: Some example Mathematica codes:
  

  • Inventory model (nb)

  
  

  Lecture 4 (1.11.): Chapter 4 in Lecture notes (similar to old Lecture notes)
  

  • Passage times and hitting times
  • Calculation of expected passage time
  • Calculation of hitting probabilities
  • Gambler's ruin
  • (We assume MC has finite state space)

  
  

  Additional material: Some example Mathematica codes:
  

  • Gambler's ruin (nb)
  • Hitting probability - general recursion (nb)
  • Expected passage time - general recursion (nb)

  
  

  Lecture 5 (6.11.): Chapter 5 in Lecture notes (similar to old Lecture notes, a bit extended)
  

  • Countable state spaces: What is different?
  • Question: Existence/non-existence of invariant (and limit) distribution?
  • Reversibility and detailed balance equations
  • Markov chain convergence theorem
  • Birth-death process and Random Walk on non-negative integers

  
  

  Lecture 6 (8.11.): Chapter 6 in Lecture notes (new, but contains some parts of Chapter 6 in old Lecture notes)
  

  • Generating functions: what are they good for?
  • Probability generating function (\phi) and its key properties: continuity, convexity, differentiability
  • Expected value and variance from derivatives of \phi
  • Multiplicativity property of probability generating function
  • Multiplicativity for random numbers of iid random variables
    

  
  

  (NB: If you are following video recordings from an earlier edition of this course, this lecture is not available there. Please check out the lecture notes carefully)

  
  

  Lecture 7 (13.11.): Chapter 7 in Lecture notes (similar to Chapter 6 in old Lecture notes, a bit reduced)
  

  • Branching processes (Galton-Watson processes, X)
  • Probability generating function of X
  • Definition using offspring distribution (Y \sim p), tree structure
  • Expected population size in terms of E[Y]
  • Finding extinction probability using properties of the probability generating function of Y (fixed point equation)

  
  

  Lecture 8 (15.11.): Chapter 8 in Lecture notes (similar to Chapter 7 in old Lecture notes)
  

  • Point processes on real intervals and their counting processes
  • The ubiquitous Poisson process
  • Waiting times of Poisson Processes are exponentially distributed
  • They have the memoryless property (and they are unique with that property)

  
  
  Lecture 9 (20.11.): Chapter 9 in Lecture notes (similar to Chapter 8 in old Lecture notes)
  
  

  • Variants of Poisson processes:
  • Superposed Poisson Process (sum of independent PP)
  • Compound Poisson Process (PP with random jump sizes)
  • Thinned Poisson Process

  
  

  Lecture 10 (22.11.): Chapter 10 in Lecture notes (similar to parts of Chapters 9-10 in old Lecture notes)

  • Markov property and MC in continuous time
  • (Note: We always assume time-homogeneity in this course.)
  • Semigroup of transition matrices (P_t)_t: suffices to know P_s for some small time s>0
  • Generator matrix of MC
    
  • Behavior in the long run, statistical equilibrium

  
  

  Lecture 11 (27.11.): Chapter 11 in Lecture notes (similar to parts of Chapters 9-10 in old Lecture notes)

  • Continuing to study continuous-time MC more precisely
  • Jump probabilities and jump rates
  • What is the generator matrix (Q) exactly? Matrix exponential semigroup.
  • Build continuous-time MC from underlying discrete-time MC and Poisson process
  • Poisson modulated chains (and overclocking)

  
  

  Lecture 12 (29.11.): Chapter 12 in Lecture notes (completely new)
  

  • Monte Carlo approximation of integrals
  • Markov chain Monte Carlo (MCMC) methods
  • Metropolis-Hastings algorithm
  • Glauber dynamics for colorings and spin models
  • Convergence, total variation distance, and mixing times