This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ahamed, T. P. I. Articles by Juneja, S. Search for Related Content

Adaptive Importance Sampling Technique for Markov Chains Using Stochastic Approximation

Department of Electrical Engineering, T. K. M. College of Engineering, Kollam 691005, India
School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India
School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India
imthi4{at}rediffmail.com
borkar{at}tifr.res.in
juneja{at}tifr.res.in

For a discrete-time finite-state Markov chain, we develop an adaptive importance sampling scheme to estimate the expected total cost before hitting a set of terminal states. This scheme updates the change of measure at every transition using constant or decreasing step-size stochastic approximation. The updates are shown to concentrate asymptotically in a neighborhood of the desired zero-variance estimator. Through simulation experiments on simple Markovian queues, we observe that the proposed technique performs very well in estimating performance measures related to rare events associated with queue lengths exceeding prescribed thresholds. We include performance comparisons of the proposed algorithm with existing adaptive importance sampling algorithms on some examples. We also discuss the extension of the technique to estimate the infinite horizon expected discounted cost and the expected average cost.

Subject classifications: probability; Markov processes; queues; Markovian; simulation; efficiency.
History: Received January 2003; revision received September 2003; revision received March 2004; revision received January 2005; accepted March 2005.

This article has been cited by other articles:

				E. Woudt, P.-T. de Boer, and J.-K. van Ommeren Improving Adaptive Importance Sampling Simulation of Markovian Queueing Models using Non-parametric Smoothing SIMULATION, December 1, 2007; 83(12): 811 - 820. [Abstract] [PDF]