On the choice of alternative measures in importance sampling with Markov chains

Andradottir, Sigrun; Heyman, Daniel P.
May 1995
Operations Research;May/Jun95, Vol. 43 Issue 3, p509
Academic Journal
In the simulation of Markov chains, importance sampling involves replacing the original transition matrix, say P, with a suitably chosen transition matrix Q that tends to visit the states of interest more frequently. The likelihood ratio of P relative to Q is an important random variable in the importance sampling method. It always has expectation one, and for any interesting pair of transition matrices P and Q, there is a sample path length that causes the likelihood ratio to be close to zero with probability close to one. This may cause the variance of the importance sampling estimator to be larger than the variance of the traditional estimator. We develop sufficient conditions for ensuring the tightness of the distribution of the logarithm of the likelihood ratio for all sample path lengths, and we show that when these conditions are satisfied, the likelihood ratio is approximately lognormally distributed with expected value one. These conditions can be used to eliminate some choices of the alternative transition matrix Q that are likely to result in a variance increase. We also show that if the likelihood ratio is to remain well behaved for all sample path lengths, the alternative transition matrix Q has to approach the original transition matrix P as the sample path length increases. The practical significance of this result is that importance sampling can be difficult to apply successfully in simulations that involve long sample paths.


Related Articles

  • A Survey of the Coupon Collector’s Problem with Random Sample Sizes. Kobza, John; Jacobson, Sheldon; Vaughan, Diane // Methodology & Computing in Applied Probability;Dec2007, Vol. 9 Issue 4, p573 

    This paper surveys the coupon collector’s waiting time problem with random sample sizes and equally likely balls. Consider an urn containing m red balls. For each draw, a random number of balls are removed from the urn. The group of removed balls is painted white and returned to the urn....

  • The Invariance Principle for p- $$ \ifmmode\expandafter\vec\else\expandafter\vecabove\fi{\theta } $$ Chain. Hu, Di He; Xiao, Zheng Yan // Acta Mathematica Sinica;Jan2007, Vol. 23 Issue 1, p41 

    There are two parts in this paper. In the first part we construct the Markov chain in random environment (MCRE), the skew product Markov chain and p– $$ \ifmmode\expandafter\vec\else\expandafter\vecabove\fi{\theta } $$ chain from a random transition matrix and a two–dimensional...


    No abstract available.

  • Almost sure central limit theorem for partial sums of Markov chain. Zhuang, Guangming; Peng, Zuoxiang; Tan, Zhongquan // Chinese Annals of Mathematics;Jan2012, Vol. 33 Issue 1, p73 

    The authors prove an almost sure central limit theorem for partial sums based on an irreducible and positive recurrent Markov chain using logarithmic means, which realizes the extension of the almost sure central limit theorem for partial sums from an i.i.d. sequence of random variables to a...

  • Binary consecutive covering arrays. Godbole, A.; Koutras, M.; Milienos, F. // Annals of the Institute of Statistical Mathematics;Jun2011, Vol. 63 Issue 3, p559 

    k × n array with entries from a q-letter alphabet is called a t-covering array if each t × n submatrix contains amongst its columns each one of the q different words of length t that can be produced by the q letters. In the present article we use a probabilistic approach based on an...

  • Plug-in Estimator of the Entropy Rate of a Pure-Jump Two-State Markov Process. Regnault, Philippe // AIP Conference Proceedings;12/8/2009, Vol. 1193 Issue 1, p153 

    The entropy of a distribution with finite support is widely used in all applications involving random variables. A natural equivalent for random processes is the entropy rate. For ergodic pure-jump finite-state Markov processes, this rate is an explicit function of the stationary distribution...

  • The Exact and Near-Exact Distributions of the Likelihood Ratio Statistic for the Block Sphericity Test. Marques, Filipe J.; Coelho, Carlos A. // AIP Conference Proceedings;9/30/2010, Vol. 1281 Issue 1, p1237 

    Using a suitable decomposition of the null hypothesis of the test of sphericity for k blocks of pi variables, into a sequence of conditionally independent null hypotheses we show that it is possible to obtain the expression of the likelihood ratio test statistic, the expression for the h-th null...

  • A formula for the Perron vector of astochastic matrix. Al'pin, Yu. A. // Journal of Mathematical Sciences;Mar2010, Vol. 165 Issue 5, p499 

    The paper suggests a new linear-algebraic proof of a formula for the Perron vector (stationary distribution) of a stochastic matrix, known in the theory of Markov chains. Bibliography: 5 titles.

  • Bayesian analysis of extreme events with threshold estimation. Behrens, Cibele N.; Lopes, Hedibert F.; Gamerman, Dani // Statistical Modelling: An International Journal;2004, Vol. 4 Issue 3, p227 

    The aim of this paper is to analyse extremal events using generalized Pareto distributions (GPD), considering explicitly the uncertainty about the threshold. Current practice empirically determines this quantity and proceeds by estimating the GPD parameters on the basis of data beyond it,...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics