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.
Mutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO, CAPUTO PIETRO
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).Attendance
OptionalType of evaluation
Oral exam of about 45 minutes teacher profile teaching materials
2. Examples and classical models. Random walks on graphs. Birth and death processes. Exclusion processes. Monte Carlo method: Metropolis algorithms and Glauber dynamics for the Ising model, graph coloring, and other interacting systems.
3. Convergence to equilibrium I. Variation distance, mixing times. Ergodic theorems. Coupling techniques. Strong stationary times. Applications to the coupon collector problem and shuffling a deck of cards.
4. Convergence to equilibrium II. L2-norm convergence. Spectral gap and relaxation time estimates. Cheeger's inequality.
5. Continuous-time Markov chains. Poisson process. Q-matrices and continuous-time transition probabilities. Infinitesimal generator of a continuous-time Markov chain. Explicit construction and graphical representation.
6. Conductance and path method. Comparison method. Spectral gap for the Bernoulli-Laplace process and the exclusion process on d-dimensional torus. Convergence to equilibrium in terms of entropy and logarithmic Sobolev inequalities.
7. Other selected topics. Glauber dynamics for the Ising model: dynamic phase transition for the mean-field model and the lattice model. The cut-off phenomenon. Algorithms for "perfect simulation."
An introduction to Markov processes, by D. Stroock, Springer 2013
Markov Chains, by J.R. Norris, Cambridge University Press 2006
Lectures on finite Markov chains, by L. Saloff-Coste, Lecture Notes in Math. 1665, pp.301-413 (1997).
Mutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO, CAPUTO PIETRO
Programme
1. Random walks and Markov Chains. Sequences of random variables. Random walks. Discrete-time Markov chains. Invariant measure, time-reversal, and reversibility.2. Examples and classical models. Random walks on graphs. Birth and death processes. Exclusion processes. Monte Carlo method: Metropolis algorithms and Glauber dynamics for the Ising model, graph coloring, and other interacting systems.
3. Convergence to equilibrium I. Variation distance, mixing times. Ergodic theorems. Coupling techniques. Strong stationary times. Applications to the coupon collector problem and shuffling a deck of cards.
4. Convergence to equilibrium II. L2-norm convergence. Spectral gap and relaxation time estimates. Cheeger's inequality.
5. Continuous-time Markov chains. Poisson process. Q-matrices and continuous-time transition probabilities. Infinitesimal generator of a continuous-time Markov chain. Explicit construction and graphical representation.
6. Conductance and path method. Comparison method. Spectral gap for the Bernoulli-Laplace process and the exclusion process on d-dimensional torus. Convergence to equilibrium in terms of entropy and logarithmic Sobolev inequalities.
7. Other selected topics. Glauber dynamics for the Ising model: dynamic phase transition for the mean-field model and the lattice model. The cut-off phenomenon. Algorithms for "perfect simulation."
Core Documentation
Markov Chains and Mixing Times, by D. Levine, Y. Peres and E. Wilmer, AMS 2009 - disponibile online pdfAn introduction to Markov processes, by D. Stroock, Springer 2013
Markov Chains, by J.R. Norris, Cambridge University Press 2006
Lectures on finite Markov chains, by L. Saloff-Coste, Lecture Notes in Math. 1665, pp.301-413 (1997).
Type of delivery of the course
blackboard lecturesType of evaluation
oral examination on the material discussed during the lectures 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.
Mutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO, CAPUTO PIETRO
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).Attendance
OptionalType of evaluation
Oral exam of about 45 minutes teacher profile teaching materials
2. Examples and classical models. Random walks on graphs. Birth and death processes. Exclusion processes. Monte Carlo method: Metropolis algorithms and Glauber dynamics for the Ising model, graph coloring, and other interacting systems.
3. Convergence to equilibrium I. Variation distance, mixing times. Ergodic theorems. Coupling techniques. Strong stationary times. Applications to the coupon collector problem and shuffling a deck of cards.
4. Convergence to equilibrium II. L2-norm convergence. Spectral gap and relaxation time estimates. Cheeger's inequality.
5. Continuous-time Markov chains. Poisson process. Q-matrices and continuous-time transition probabilities. Infinitesimal generator of a continuous-time Markov chain. Explicit construction and graphical representation.
6. Conductance and path method. Comparison method. Spectral gap for the Bernoulli-Laplace process and the exclusion process on d-dimensional torus. Convergence to equilibrium in terms of entropy and logarithmic Sobolev inequalities.
7. Other selected topics. Glauber dynamics for the Ising model: dynamic phase transition for the mean-field model and the lattice model. The cut-off phenomenon. Algorithms for "perfect simulation."
An introduction to Markov processes, by D. Stroock, Springer 2013
Markov Chains, by J.R. Norris, Cambridge University Press 2006
Lectures on finite Markov chains, by L. Saloff-Coste, Lecture Notes in Math. 1665, pp.301-413 (1997).
Mutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO, CAPUTO PIETRO
Programme
1. Random walks and Markov Chains. Sequences of random variables. Random walks. Discrete-time Markov chains. Invariant measure, time-reversal, and reversibility.2. Examples and classical models. Random walks on graphs. Birth and death processes. Exclusion processes. Monte Carlo method: Metropolis algorithms and Glauber dynamics for the Ising model, graph coloring, and other interacting systems.
3. Convergence to equilibrium I. Variation distance, mixing times. Ergodic theorems. Coupling techniques. Strong stationary times. Applications to the coupon collector problem and shuffling a deck of cards.
4. Convergence to equilibrium II. L2-norm convergence. Spectral gap and relaxation time estimates. Cheeger's inequality.
5. Continuous-time Markov chains. Poisson process. Q-matrices and continuous-time transition probabilities. Infinitesimal generator of a continuous-time Markov chain. Explicit construction and graphical representation.
6. Conductance and path method. Comparison method. Spectral gap for the Bernoulli-Laplace process and the exclusion process on d-dimensional torus. Convergence to equilibrium in terms of entropy and logarithmic Sobolev inequalities.
7. Other selected topics. Glauber dynamics for the Ising model: dynamic phase transition for the mean-field model and the lattice model. The cut-off phenomenon. Algorithms for "perfect simulation."
Core Documentation
Markov Chains and Mixing Times, by D. Levine, Y. Peres and E. Wilmer, AMS 2009 - disponibile online pdfAn introduction to Markov processes, by D. Stroock, Springer 2013
Markov Chains, by J.R. Norris, Cambridge University Press 2006
Lectures on finite Markov chains, by L. Saloff-Coste, Lecture Notes in Math. 1665, pp.301-413 (1997).
Type of delivery of the course
blackboard lecturesType of evaluation
oral examination on the material discussed during the lectures