The behavior of a Markov network with respect to an absorbing class : the target algorithm
RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 3, pp. 231-245.

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.

DOI: 10.1051/ro/2009019
Classification: 60J22, 90C35, 94C15
Keywords: Markov time of the first passage, stopping rules, Markov complexity, graphs and networks
@article{RO_2009__43_3_231_0,
     author = {Aletti, Giacomo},
     title = {The behavior of a {Markov} network with respect to an absorbing class : the target algorithm},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {231--245},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {3},
     year = {2009},
     doi = {10.1051/ro/2009019},
     mrnumber = {2567986},
     zbl = {1173.60026},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2009019/}
}
TY  - JOUR
AU  - Aletti, Giacomo
TI  - The behavior of a Markov network with respect to an absorbing class : the target algorithm
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 231
EP  - 245
VL  - 43
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2009019/
DO  - 10.1051/ro/2009019
LA  - en
ID  - RO_2009__43_3_231_0
ER  - 
%0 Journal Article
%A Aletti, Giacomo
%T The behavior of a Markov network with respect to an absorbing class : the target algorithm
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 231-245
%V 43
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2009019/
%R 10.1051/ro/2009019
%G en
%F RO_2009__43_3_231_0
Aletti, Giacomo. The behavior of a Markov network with respect to an absorbing class : the target algorithm. RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 3, pp. 231-245. doi : 10.1051/ro/2009019. http://archive.numdam.org/articles/10.1051/ro/2009019/

[1] S. Aki and K. Hirano, Sooner and later waiting time problems for runs in Markov dependent bivariate trials. Ann. Inst. Stat. Math. 51 (1999) 17-29. | MR | Zbl

[2] G. Aletti and E. Merzbach, Stopping markov processes and first path on graphs. J. Eur. Math. Soc. (JEMS) 8 (2006) 49-75. | MR | Zbl

[3] D.L. Antzoulakos and A.N. Philippou, Probability distribution functions of succession quotas in the case of Markov dependent trials. Ann. Inst. Stat. Math. 49 (1997) 531-539. | MR | Zbl

[4] B.C. Arnold, N. Balakrishnan and H.N. Nagaraja, Records. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons Inc., New York (1998). | MR | Zbl

[5] R. Cairoli and R.C. Dalang, Sequential stochastic optimization. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons Inc., New York (1996). | MR | Zbl

[6] M. Ebneshahrashoob and M. Sobel, Sooner and later waiting time problems for Bernoulli trials: frequency and run quotas. Stat. Probab. Lett. 9 (1990) 5-11. | MR | Zbl

[7] M.V. Koutras and V.A. Alexandrou, Sooner waiting time problems in a sequence of trinary trials. J. Appl. Probab. 34 (1997) 593-609. | MR | Zbl

[8] K. Lam and H.C. Yam, Cusum techniques for technical trading in financial markets. Financial Engineering & the Japanese Markets 4 (1997) 257-274. | Zbl

[9] V.T. Stefanov, On some waiting time problems. J. Appl. Probab. 37 (2000) 756-764. | MR | Zbl

[10] V.T. Stefanov and A.G. Pakes, Explicit distributional results in pattern formation. Ann. Appl. Probab. 7 (1997) 666-678. | MR | Zbl

Cited by Sources: