No CrossRef data available.
Article contents
ASYMPTOTIC VARIANCE OF PASSAGE TIME ESTIMATORS IN MARKOV CHAINS
Published online by Cambridge University Press: 27 February 2007
Abstract
We consider the problem of estimating passage times in stochastic simulations of Markov chains. Two types of estimator are considered for this purpose: the “simple” and the “overlapping” estimator; they are compared in terms of their asymptotic variance. The analysis is based on the regenerative structure of the process and it is shown that when estimating the mean passage time, the simple estimator is always asymptotically superior. However, when the object is to estimate the expectation of a nonlinear function of the passage time, such as the probability that the passage time exceeds a given threshold, then it is shown that the overlapping estimator can be superior in some cases. Related results in the Reinforcement Learning literature are discussed.
- Type
- Research Article
- Information
- Probability in the Engineering and Informational Sciences , Volume 21 , Issue 2 , April 2007 , pp. 217 - 234
- Copyright
- © 2007 Cambridge University Press
References
REFERENCES
Bertsekas, D.P. &
Tsitsiklis, J.N.
(1996).
Neuro-dynamic programming.
Nashua, NH:
Athena Press.
Calvin, J.M. &
Nakayama, M.K.
(1998).
Using permutations in regenerative simulations to reduce
variance.
ACM Transactions on Modelling and Computer Simulation
8(2):
153–193.Google Scholar
Cao, X.R. &
Chen, H.F.
(1997).
Perturbation realization, potentials, and sensitivity analysis of
Markov processes.
IEEE Transactions on Automatic Control
42(10):
1382–1393.Google Scholar
Cho, G.E. &
Meyer, C.D.
(2000).
Markov chain sensitivity measured by mean first passage
times.
Linear Algebra and its Applications
316:
21–28.Google Scholar
Cramér, H.
(1946).
Mathematical methods of statistics.
Princeton, NJ:
Princeton University Press.
Glynn, P.W. &
Iglehart, D.L.
(1989).
Importance sampling for stochastic simulations.
Management Science
35(11):
1367–1392.Google Scholar
Harrison, P.G. &
Knottenbelt, W.J.
(2002).
Passage time distributions in large Markov chains. In
Proceedings ACM SIGMETRICS, June 2002, Marina Del Rey, CA,
pp.
77–85.
Heidergott, B. &
Hordijk, A.
(2003).
Taylor series expansions for stationary Markov chains.
Advances in Applied Probability
35:
1046–1070.Google Scholar
Karamichalakou, C. &
Zazanis, M.A.
(2000). Asymptotic variance properties of
passage time estimators for Markov chains. Technical report, Athens
University of Economics and Business, Athens, Greece.
Kemperman, J.H.B.
(1961).
The passage problem for a stationary Markov chain.
Chicago:
University of Chicago Press.
Meyer, C.D.
(1994).
Sensitivity of the stationary distribution of a Markov chain.
SIAM Journal of Matrix Analysis and Applications
15:
715–728.Google Scholar
Nakayama, M.K.,
Goyal, A., &
Glynn, P.W.
(1994).
Likelihood ratio sensitivity analysis for Markovian models of highly
dependable systems.
Operations Research
42:
137–157.Google Scholar
Prakasa Rao, B.L.S.
(1987).
Asymptotic theory of statistical inference.
New York:
Wiley.
Ross, S.M. &
Schechner, Z.
(1985).
Using simulation to estimate first passage distribution.
Management Science
31(2):
224–234.Google Scholar
Shahabuddin, P.
(1994).
Importance sampling for highly reliable Markovian systems.
Management Science
40(3):
333–352.Google Scholar
Singh, S.P. &
Sutton, R.S.
(1996).
Reinforcement learning with replacing eligibility traces.
Machine Learning
22:
123–158.Google Scholar
Syski, R.
(1992).
Passage times for Markov chains.
Amsterdam:
IOS Press.