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.
Curriculum
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.
D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).
Additional reference (in Italian)
Luca Leuzzi, Enzo Marinari, Giorgio Parisi
CALCOLO DELLE PROBABILITÀ: un trattatello per principianti volenterosi
Mutuazione: 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
Main reference:D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).
Additional reference (in Italian)
Luca Leuzzi, Enzo Marinari, Giorgio Parisi
CALCOLO DELLE PROBABILITÀ: un trattatello per principianti volenterosi
Type of delivery of the course
traditional classroom lessons with the help of exercises on the blackboard; any disbursement even at a distance will be confirmed by the teacherAttendance
OptionalType of evaluation
Oral exam of about 45 minutes 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.
D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).
Additional reference (in Italian)
Luca Leuzzi, Enzo Marinari, Giorgio Parisi
CALCOLO DELLE PROBABILITÀ: un trattatello per principianti volenterosi
Mutuazione: 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
Main reference:D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).
Additional reference (in Italian)
Luca Leuzzi, Enzo Marinari, Giorgio Parisi
CALCOLO DELLE PROBABILITÀ: un trattatello per principianti volenterosi
Type of delivery of the course
traditional classroom lessons with the help of exercises on the blackboard; any disbursement even at a distance will be confirmed by the teacherAttendance
OptionalType of evaluation
Oral exam of about 45 minutes 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.
D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).
Additional reference (in Italian)
Luca Leuzzi, Enzo Marinari, Giorgio Parisi
CALCOLO DELLE PROBABILITÀ: un trattatello per principianti volenterosi
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
Main reference:D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).
Additional reference (in Italian)
Luca Leuzzi, Enzo Marinari, Giorgio Parisi
CALCOLO DELLE PROBABILITÀ: un trattatello per principianti volenterosi
Type of delivery of the course
traditional classroom lessons with the help of exercises on the blackboard; any disbursement even at a distance will be confirmed by the teacherAttendance
OptionalType of evaluation
Oral exam of about 45 minutes