Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-05T16:10:24.290Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  22 July 2009

Giacomo Aletti
Giacomo Aletti*
Affiliation:
ADAMSS Centre & Dipartimento di Matematica, Università di Milano, 20133 Milan, Italy; [email protected]
Get access

Abstract

In this paper, we face a generalization ofthe problem of finding the distribution of how longit takes to reach a “target” set T of states inMarkov chain. The graph problems of finding the number of paths thatgo from a state to a target set and of finding the n-length path connectionsare shown to belong to this generalization.This paper explores how the statespace of the Markov chain can be reduced by collapsing togetherthose states that behave in the same way for the purposes ofcalculating the distribution ofthe hitting time of T.We prove the existence and the uniqueness of aoptimal 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 onsome classical problems to demonstrate the deeper understanding that ismade possible by this approach.

Keywords

Markov time of the first passagestopping rulesMarkovcomplexitygraphs and networks.
Type
Research Article
Information
RAIRO - Operations Research , Volume 43 , Issue 3: ROADEF 06 , July 2009 , pp. 231 - 245
Copyright
© EDP Sciences, ROADEF, SMAI, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aki, S. and Hirano, K., Sooner and later waiting time problems for runs in Markov dependent bivariate trials. Ann. Inst. Stat. Math. 51 (1999) 17–29. CrossRef
Aletti, G. and Merzbach, E., Stopping markov processes and first path on graphs. J. Eur. Math. Soc. (JEMS) 8 (2006) 49–75. CrossRef
Antzoulakos, D.L. and Philippou, A.N., Probability distribution functions of succession quotas in the case of Markov dependent trials. Ann. Inst. Stat. Math. 49 (1997) 531–539. CrossRef
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).
Ebneshahrashoob, M. and Sobel, M., Sooner and later waiting time problems for Bernoulli trials: frequency and run quotas. Stat. Probab. Lett. 9 (1990) 5–11. CrossRef
Koutras, M.V. and Alexandrou, V.A., Sooner waiting time problems in a sequence of trinary trials. J. Appl. Probab. 34 (1997) 593–609. CrossRef
Lam, K. and Yam, H.C., Cusum techniques for technical trading in financial markets. Financial Engineering & the Japanese Markets 4 (1997) 257–274. CrossRef
Stefanov, V.T., On some waiting time problems. J. Appl. Probab. 37 (2000) 756–764. CrossRef
Stefanov, V.T. and Pakes, A.G., Explicit distributional results in pattern formation. Ann. Appl. Probab. 7 (1997) 666–678.