Metodi Monte Carlo basati su catene di Markov

This master's thesis investigates Monte Carlo (MC) and Markov Chain Monte Carlo (MCMC) methods, with particular focus on their efficiency in sampling from complex distributions and analyzing convergence rates. Following an introductory section covering probabilistic foundations and classical MC methods (illustrated through π estimation), the work examines MCMC algorithms, paying special attention to the Metropolis algorithm for non-uniform distributions and its application to sampling independent sets in graphs. The core of the thesis focuses on convergence analysis, introducing key concepts including variation distance, mixing time, cutoff phenomena, and coupling techniques. These methodologies are applied to concrete cases such as card shuffling, random walks on circles, and the Ehrenfest model for particle diffusion. The results demonstrate the universality of MCMC approaches in both combinatorial and physical contexts, revealing how Markov chain design and convergence analysis critically determine algorithmic efficiency.

Questa tesi magistrale indaga i metodi Monte Carlo (MC) e Markov Chain Monte Carlo (MCMC), approfondendone l’efficienza nel campionamento da distribuzioni complesse e l’analisi della velocità di convergenza. Dopo una sezione introduttiva sui preliminari probabilistici e sul metodo MC classico (illustrato tramite la stima di pi greco), si esaminano gli algoritmi MCMC, con particolare attenzione all’algoritmo di Metropolis per distribuzioni non uniformi e alla sua applicazione al campionamento di insiemi indipendenti in grafi. Il cuore della tesi verte sullo studio della convergenza, introducendo strumenti quali variation distance, mixing time, fenomeno del cutoff e tecniche di coupling. Queste metodologie sono applicate a casi concreti come il mescolamento di mazzi di carte, random walk su circonferenze ed il modello di Ehrenfest per la diffusione di particelle. I risultati evidenziano l’universalità degli approcci MCMC in ambiti combinatrici e fisici, dimostrando come la progettazione della catena di Markov e l’analisi della convergenza condizionino l’efficienza algoritmica.