Lecture Notes

• Title: Stochastic processes and simulation in the natural sciences

• Instructor: Giacomo Zanella

• Date: March 4, 2025

Contents

1. Discrete-time Markov chains

   • 1.1 Introduction to Stochastic Processes

   • 1.2 Markov Chains

     • 1.2.1 Chapman-Kolmogorov equations

   • 1.3 Classification of states and recurrence

     • 1.3.1 Communication classes

     • 1.3.2 Transience and recurrence

     • 1.3.3 Random walks in d dimension

   • 1.4 Convergence to stationarity

     • 1.4.1 Stationary distributions

     • 1.4.2 Convergence in distribution

     • 1.4.3 Convergence of asymptotic frequencies

     • 1.4.4 Ergodic averages and law of large numbers for MCs

   • 1.5 Counter-examples where the convergence theorem fails

     • 1.5.1 Infinite state spaces and non-existence of stationary distributions

     • 1.5.2 Lack of irreducibility and hitting times

     • 1.5.3 Time-inhomogeneity and self-reinforcing processes

   • 1.6 Reversibility and detailed balance

2. Illustrative examples and applications of discrete-time Markov chains

   • 2.1 Random walks on graphs and PageRank

   • 2.2 Sequential testing

   • 2.3 Hidden Markov models

3. Continuous-time Markov chains

   • 3.1 Background and tools

     • 3.1.1 Exponential distribution

     • 3.1.2 Hazard rates

     • 3.1.3 First events properties

   • 3.2 Markov property and transition probabilities

     • 3.2.1 Generator/Jump rates

   • 3.3 Examples of CTMCs

     • 3.3.1 Binary chain

     • 3.3.2 Poisson process

     • 3.3.3 Birth process with linear birth

     • 3.3.4 Process with birth, death and immigration

   • 3.4 Kolmogorov differential equations

     • 3.4.1 Kolmogorov backward and forward equations

   • 3.5 Jump chain and holding time construction

   • 3.6 Limiting behavior of CTMCs

   • 3.7 Birth and death processes

   • 3.8 The Poisson Process

     • 3.8.1 One-dimensional, homogeneous case

     • 3.8.2 One-dimensional, non-homogeneous case

     • 3.8.3 General case

Detailed Notes

Discrete-time Markov Chains

1.1 Introduction to Stochastic Processes

• Stochastic processes represent models for random quantities that change or evolve over time.

• Formally defined as a collection of random variables {Xt, t ∈ T} where Xt maps outcomes to states.

1.2 Markov Chains

• Definition: A discrete time stochastic process is a Markov chain if the future state depends only on the present state, not on the prior states.

• Transition Matrix: It characterizes the behavior of the Markov chain with probabilities Pij = Pr(X(t+1) = j | X(t) = i).

• Examples include the Gambler's ruin and random walks.

1.3 Classification of States and Recurrence

1.3.1 Communication Classes

• Two states communicate if each is accessible from the other.

• States partition into classes based on communication.

1.3.2 Transience and Recurrence

• A state is recurrent if, starting from that state, it will eventually return with probability 1; otherwise, it's transient.

1.3.3 Random Walks in d Dimension

• Discusses different recurrence properties in random walks across multiple dimensions.

1.4 Convergence to Stationarity

• Stationary Distribution: A distribution π for a Markov chain that remains invariant over time.

• Convergence theorems establish conditions under which a Markov chain approaches this stationary distribution over time.

1.5 Counter-Examples to Convergence Theorem

• Discusses scenarios such as infinite state spaces where stationary distributions may not exist.

1.6 Reversibility

• A Markov chain is reversible if the probabilities of transitioning between states maintain balance over time.

Illustrative Examples and Applications

2.1 Random Walks on Graphs and PageRank

• PageRank relies on the structure of directed graphs to rank web pages based on the probability of random walks.

2.2 Sequential Testing

• Involves frameworks for comparing the effectiveness of drugs or treatments using randomized trials.

2.3 Hidden Markov Models

• These models involve latent processes and are widely applicable in signal processing.

Continuous-Time Markov Chains

3.1 Background and Tools

3.1.1 Exponential Distribution

• Continuous random variable with a specific distribution characterized by a constant hazard rate.

3.2 Markov Property

• Continuous-time stochastic processes must satisfy a Markov property.

3.3 Examples of CTMCs

• Discusses practical applications of CTMCs such as birth-death processes and Poisson processes.

3.4 Kolmogorov Equations

• Define and derive the differential equations governing the transition probabilities in CTMCs.

3.5 Jump Chain and Holding Time Construction

• Introduces techniques to simulate trajectories of CTMCs using sequences of jump chains and holding times.

3.6 Limiting Behavior

• Discusses how to derive the long-run behavior of CTMCs and identifies limiting distributions.

3.7 Birth and Death Processes

• Explains modeling techniques for populations and queues using birth-death chains.

3.8 Poisson Process

3.8.1 NHPP

• Discusses the non-homogeneous Poisson process and its definition in the context of counting processes.