Numerical Computation of Large Deviations Exponents via Simulation

P. W. Glynn

Proceedings of the 1996 Allerton Conference on Communication, Control, and Computing, 790-797 (1996)

Consider the problem of numerically computing the exponential rate at which the tail of the hitting time of a Markov chain to a given set decreases to zero. One approach involves computing the solution to an eigenvalue problem. In this paper, we use a regenerative representation for the exponential rate constant to construct an associated simulation-based estimator. A strong law and central limit theorem for the estimator are also presented.