Introduction to the theory of stochastic processes. Markov chains: ergodic theory, coupling, mixing times, with applications to random walks, card shuffling, and the Monte Carlo method. The Poisson process, continuous time Markov chains, convergence to equilibrium for some simple interacting particle systems
teacher profile teaching materials
2. Classical examples. Random walks on graphs, Birth and death chains, exclusion process. Markov Chain Monte Carlo: Metropolis and Glauber dynamics for the Ising model, colorings and other interacting particle systems.
3. Convergence to equilibrium I. Variation distance and mixing time. Ergodic theorems and coupling techniques. Strong stationary times. The coupon collector problem and card shuffling.
4. Convergence to equilibrium II. Spectral gap and relaxation times. Cheeger inequality, conductance and canonical paths. Comparison method and spectral gap for the exclusion process. Logarithmic Sobolev inequality.
5. Other topics: Glauber dynamics for the Ising model, phase transition, cutoff phenomenon, perfect simulation.
Fruizione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO
Programme
1. Random walks and Markov Chains. Sequence of random variables, random walks, Markov chains in discrete and continuous time. Invariant measures, reversibility.2. Classical examples. Random walks on graphs, Birth and death chains, exclusion process. Markov Chain Monte Carlo: Metropolis and Glauber dynamics for the Ising model, colorings and other interacting particle systems.
3. Convergence to equilibrium I. Variation distance and mixing time. Ergodic theorems and coupling techniques. Strong stationary times. The coupon collector problem and card shuffling.
4. Convergence to equilibrium II. Spectral gap and relaxation times. Cheeger inequality, conductance and canonical paths. Comparison method and spectral gap for the exclusion process. Logarithmic Sobolev inequality.
5. Other topics: Glauber dynamics for the Ising model, phase transition, cutoff phenomenon, perfect simulation.
Core Documentation
D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).Type of delivery of the course
Frontal lecturesType of evaluation
Oral exam of about 45 minutes