Catene di Markov: applicazioni e sviluppi

La presente tesi ha lo scopo di descrive alcune importanti applicazioni delle catene di Markov, introdotte all’inizio del XX secolo da Andrej Andreevich Markov, matematico e statistico russo. Egli ideò un particolare processo stocastico senza memoria, detto processo markoviano o catena di Markov, che ha contribuito a far progredire in modo sostanziale la teoria della probabilità, in quanto ha portato ad importanti risultati di utilità pratica ed ancora oggi costituisce una parte essenziale delle applicazioni del calcolo delle probabilità, dimostrando di essere un argomento moderno e all'avanguardia. Nei primi capitoli presentiamo un’introduzione ai processi di Markov a tempo discreto; sono esposte le nozioni di base e i risultati principali riguardanti le catene di Markov, utili per questo elaborato. Successivamente si passa ad esaminare alcune importanti applicazioni delle stesse in ambiti diversi tra loro. Le catene di Markov e le loro proprietà ergodiche sono utilizzate nella progettazione e nell’analisi di numerosi algoritmi di ottimizzazione e conteggio per svariati problemi. Inoltre, i modelli stocastici di tipo Markoviano, ottenuti come varianti o estensioni delle catene di Markov, sono utilizzati in numerose aree di ricerca, per esempio nella progettazione di algoritmi di esplorazione della rete web (Pagerank), in biologia computazionale, in particolare, nelle analisi statistiche di sequenze di DNA, nello sviluppo di strumenti per il riconoscimento di segnali vocali e facciali.