In this paper, we face a generalization of the problem of finding the distribution of how long it takes to reach a "target" set T of states in Markov chain. The graph problems of finding the number of paths that go from a state to a target set and of finding the n-length path connections are shown to belong to this generalization. This paper explores how the state space of the Markov chain can be reduced by collapsing together those states that behave in the same way for the purposes of calculating the distribution of the hitting time of T. We prove the existence and the uniqueness of a optimal projection for this aim which extends the results given in [G. Aletti and E. Merzbach, J. Eur. Math. Soc. (JEMS) 8 (2006) 49–75], together with the existence of a polynomial algorithm which reaches this optimum. Some applied examples are presented. Markov complexity is defined an tested on some classical problems to demonstrate the deeper understanding that is made possible by this approach.

The behavior of a Markov network with respect to an absorbing class: the target algorithm / G. Aletti. - In: RAIRO RECHERCHE OPERATIONNELLE. - ISSN 0399-0559. - 43:3(2009), pp. 231-245.

The behavior of a Markov network with respect to an absorbing class: the target algorithm

G. Aletti
Primo
2009

Abstract

In this paper, we face a generalization of the problem of finding the distribution of how long it takes to reach a "target" set T of states in Markov chain. The graph problems of finding the number of paths that go from a state to a target set and of finding the n-length path connections are shown to belong to this generalization. This paper explores how the state space of the Markov chain can be reduced by collapsing together those states that behave in the same way for the purposes of calculating the distribution of the hitting time of T. We prove the existence and the uniqueness of a optimal projection for this aim which extends the results given in [G. Aletti and E. Merzbach, J. Eur. Math. Soc. (JEMS) 8 (2006) 49–75], together with the existence of a polynomial algorithm which reaches this optimum. Some applied examples are presented. Markov complexity is defined an tested on some classical problems to demonstrate the deeper understanding that is made possible by this approach.
Graphs and networks; Markov complexity; Markov time of the first passage; Stopping rules
Settore MAT/06 - Probabilita' e Statistica Matematica
http://www.rairo-ro.org/articles/ro/pdf/2009/03/ro0616.pdf
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/67503
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact