Importance Sampling for Markov Chains: Asymptotics for the Variance

Abstract

In this paper, we apply the Perron-Frobenius theory for non-negative matrices to the analysis of variance asymptotics for simulations of finite state Markov chains to which im sampling is applied. The results show that we can typically expect the variance to grow (at least) exponentially rapidly in the length of the time horizon simulated. The exponential rate constant is determined by the Perron-Frobenius eigenvalue of a certain matrix. Applications to cumulative costs, terminal costs, steady-state costs, and the like ratio gradient estimator are presented. In addition, the implications for general discrete-event simulations are presented. Keywords: importance sampling Markov chains, discrete-event simulation

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1991
Accession Number
ADA249804

Entities

People

  • Peter W. Glynn

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • California
  • Eigenvalues
  • Estimators
  • Markov Chains
  • Markov Processes
  • Mathematics
  • New York
  • Operations Research
  • Probability
  • Probability Distributions
  • Simulations
  • Statistical Algorithms
  • Steady State
  • Stochastic Processes
  • United States

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Calculus or Mathematical Analysis
  • Computational Modeling and Simulation