Teorema ergodico per catene di Markov e algoritmo PageRank di Google

Le catene di Markov sono processi stocastici a tempo discreto, la cui evoluzione non è deterministica ma probabilistica ed è caratterizzata dal fatto che la probabilità di passare da uno stato ad un altro non dipende dal percorso fatto fino a quel momento (cioè da tutti gli stati attraversati fino a quel momento), ma dipende esclusivamente dallo stato attuale. Nell'elaborato viene presentato un fondamentale risultato riguardante il comportamento asintotico di una particolare classe di catene di Markov a tempo discreto, ossia il Teorema ergodico. Tale risultato ci consentirà di affermare che, per tempi sufficientemente grandi, la probabilità di raggiungere un certo stato finale non dipende dallo stato di partenza. Questi risultati saranno usati per descrivere l'algoritmo PageRank di Google, sviluppato tra il 1996 e il 1998 da Sergey Brin e Larry Page, che permette di quantificare l'importanza di una pagina web e, di conseguenza, stabilire un ordine in cui presentare tali pagine.