Monotonicity Requirements for Efficient Exact Sampling with Markov Chains

P. Lorek, P. Markowski

2017, v.23, Issue 3, 485-514

ABSTRACT

We recall three methods for exact sampling from a stationary distribution of a Markov chain:
the coupling from the past (CFTP) algorithm, a method based on strong stationary duality (SSD), and Fill's rejection algorithm.
Each method, to be applied efficiently, requires a different notion of monotonicity, which is defined with respect to a partial ordering of the state space,
namely realizable monotonicity, M\"obius monotonicity, and stochastic monotonicity. We show full relations between monotonicities.
The applicability of the CFTP algorithm implies the applicability of Fill's rejection algorithm, but does not imply that of the SSD-based method. We also state one open
problem related to these monotonicities.

Keywords: exact simulation, perfect simulation, coupling from the past, Fill's rejection algorithm, strong stationary duality, strong stationary time, coupling, stochastic monotonicity, realizable monotonicity, M\"obius monotonicity, failure rate monotonicity, Siegmund duality

COMMENTS

Please log in or register to leave a comment