• Markov chain
• Markov process
• metastability
• nearly reducible Markov chain
• numerical analysis
• fundamental matrix
• commitor probability
• GTH
• state reduction

La comprensione dei fenomeni modellati dalle catene di Markov passa per l’analisi
di quattro elementi chiave: la distribuzione stazionaria, la matrice fondamentale, la
media dei tempi di primo passaggio e la probabilità committor. La composizione di questi elementi
che possiamo considerare ’fondanti’, ci permette di accedere a un ampio spettro
di informazioni di notevole utilità pratica. Nelle applicazioni reali, tuttavia, non è
raro incontrare situazioni in cui la matrice di transizione è mal-condizionata come
nel caso di problemi che presentano metastabilità, in cui, cioè, lo spazio degli stati
ha una struttura clusterizzata in componenti fortemente connesse, difficilmente
raggiungibili tra loro. Per questo tipo di problemi i metodi numerici tradizionali
hanno prestazioni deludenti, in particolare i metodi diretti possono rivelarsi poco
accurati e computazionalmente ’costosi’ mentre i metodi iterativi mostrano generalmente
una convergenza molto lenta. In questa tesi vedremo come i metodi basati
sulla riduzione dello spazio degli stati si sono rivelati oltremodo efficienti per aggirare
le problematiche legate al mal-condizionamento e possono essere facilmente
adattati alla struttura del problema per ridurre i costi computazionali aggregando
tra loro gli stati di una stessa componente metastabile. Dopo aver riassunto le nozioni
fondamentali sulle catene di Markov, introducendo formalmente il concetto di
metastabilità e di matrici quasi riducibili, descriviamo le proprietà principali degli
elementi che abbiamo definito ’fondanti’(Sez. 1 e 2). Nella sezione 3, dopo aver
riepilogato i principali metodi classici utilizzati in letteratura per determinare le
informazioni di nostro interesse, presentiamo i metodi ’state reduction’, fornendo
una interpretazione algebrica e descrivendo gli algoritmi usati per la sperimentazione.
Infine, nella sezione 4, verifichiamo i vantaggi di un approccio state reduction
mostrando i risultati ottenuti applicando i metodi descritti a situazioni con forte
metastabilità.

The comprehension of phenomena modeled by Markov chains passes through four 'foundling' quantities: the stationary distribution, the fundamental matrix, the mean first passage times matrix and the committor probabilities. In Markov chain theory it is not uncommon to encounter ill-conditioned matrices for which the computation of the key quantities above is difficult from a numerical point of view. This is the case of nearly reducible matrices that arise from the study of situations that present metastability, that is when the state space is clustered in strongly connected separated sets, hardly accessible from each other. For those problems direct methods are computationally expensive for high dimensional processes, while iterative methods tipically show a slow convergence. In the present work we are going to see how state reduction methods can be adapted to control the issues related to both ill-conditioned problems and high dimensional problems. After resuming the basics of Markov chains, introducing the concept of metastability, we describe the main properties of the key features of a Markov chain. Then we talk about the numerical methods, recalling the classic methods and presenting the state reduction algorithms. The experimentation of the methods ends the paper.