Tempi di mixing per le catene di Markov

Abstract

In questo elaborato porremo la nostra attenzione sulla convergenza, per alcune catene di Markov, ad una legge stazionaria. In generale la convergenza si ha per t che tende a infinito, ma vedremo che per alcune catene di Markov è sufficiente un arco temporale limitato per ottenere una buona approssimazione. Questo arco temporale verrà chiamato tempo di mixing e studieremo un modo per stimarlo. Nel primo capitolo daremo la definizione di catena di Markov e di legge invariante e vedremo alcune condizioni che ci assicurano l’esistenza e l’unicità di una legge invariante. Successivamente, nel secondo capitolo, definiremo una distanza che ci permetterà di dimostrare un teorema di convergenza alla legge stazionaria. Infine stimeremo il tempo di mixing tramite il metodo dell’accoppiamento (coupling) in alcuni esempi concreti come il mescolamento delle carte e passeggiate aleatorie su un cubo.

In this thesis we will focus our attention on the convergence, for some Markov chains, to a stationary distribution. In general, convergence occurs as t tends to infinity, but we will see that for some Markov chains a limited time span is sufficient to obtain a good approximation. This time frame will be called mixing time and we will study a way to estimate it. In the first chapter we will give the definition of Markov chain and stationary distribution and we will see some conditions which confirm the existence and uniqueness of a stationary distribution. Subsequently, in the second chapter, we will define a distance that will allow us to prove a convergence theorem to the stationary law. Finally we will estimate mixing time the coupling method in some concrete examples such as card shuffling and random walks on a cube.