Acquire a solid basic preparation in the main aspects of the stochastic process theory with particular regard to Markov's processes and their applications (Monte Carlo and simulated annealing), the theory of random walks, and the simplest models of interagent 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 evaluation
Oral exam of about 45 minutes