×

Fill’s algorithm for absolutely continuous stochastically monotone kernels. (English) Zbl 1010.60068

J. A. Fill [Probab. Eng. Inf. Sci. 12, No. 3, 283-302 (1998; Zbl 0978.62013)] introduced a perfect sampling algorithm for finite-state stochastically monotone Markov chains. Fill’s algorithm was extended by J. A. Fill, M. Machida, D. J. Murdoch and J. S. Rosenthal [Random Struct. Algorithms 17, No. 3/4, 290-316 (2000) and in: Monte Carlo methods. Fields Inst. Commun. 26, 37-52 (2000; Zbl 0966.65008)] to generic chains on general (continuous) state spaces (this algorithm is denoted hereafter as FMMR algorithm).
The aim of the present paper is to continue the investigation of the FMMR algorithm for absolutely continuous stochastically monotone kernels, and to show the correctness of the FMMR algorithm in the new framework under a set of (three) regularity conditions. The considered regularity conditions are proved to relax the previously known sufficient hypotheses on the FMMR algorithm. Furthermore, the possible applicability of the FMMR algorithm for the quasi-monotone case is introduced and discussed.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68U20 Simulation (MSC2010)
65C05 Monte Carlo methods
65C10 Random number generation in numerical analysis
65C40 Numerical analysis or methods applied to Markov chains
60G40 Stopping times; optimal stopping problems; gambling theory
PDFBibTeX XMLCite
Full Text: DOI EuDML EMIS