The behavior of a Markov network with respect to an absorbing class: the target algorithm
RAIRO - Operations Research (2009)
- Volume: 43, Issue: 3, page 231-245
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topAletti, Giacomo. "The behavior of a Markov network with respect to an absorbing class: the target algorithm." RAIRO - Operations Research 43.3 (2009): 231-245. <http://eudml.org/doc/250620>.
@article{Aletti2009,
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.
},
author = {Aletti, Giacomo},
journal = {RAIRO - Operations Research},
keywords = {Markov time of the first passage; stopping rules; Markov
complexity; graphs and networks.; Markov complexity; graphs and networks},
language = {eng},
month = {7},
number = {3},
pages = {231-245},
publisher = {EDP Sciences},
title = {The behavior of a Markov network with respect to an absorbing class: the target algorithm},
url = {http://eudml.org/doc/250620},
volume = {43},
year = {2009},
}
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
DA - 2009/7//
PB - EDP Sciences
VL - 43
IS - 3
SP - 231
EP - 245
AB -
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.
LA - eng
KW - Markov time of the first passage; stopping rules; Markov
complexity; graphs and networks.; Markov complexity; graphs and networks
UR - http://eudml.org/doc/250620
ER -
References
top- 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.
- G. Aletti and E. Merzbach, Stopping markov processes and first path on graphs. J. Eur. Math. Soc. (JEMS)8 (2006) 49–75.
- 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.
- 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).
- 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).
- 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.
- M.V. Koutras and V.A. Alexandrou, Sooner waiting time problems in a sequence of trinary trials. J. Appl. Probab.34 (1997) 593–609.
- K. Lam and H.C. Yam, Cusum techniques for technical trading in financial markets. Financial Engineering & the Japanese Markets4 (1997) 257–274.
- V.T. Stefanov, On some waiting time problems. J. Appl. Probab.37 (2000) 756–764.
- V.T. Stefanov and A.G. Pakes, Explicit distributional results in pattern formation. Ann. Appl. Probab.7 (1997) 666–678.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.