Perfect simulation and monotone stochastic bounds

We combine monotone bounds of Markov chains and the coupling from the past to obtain an exact sampling of a strong stochastic bound of the steady-state distribution for a Markov chain. Stochastic bounds are sufficient to bound any positive increasing rewards on the steady-state such as the loss rates and the average size or delay. We show the equivalence between st-monotonicity and event monotonicity when the state space is endowed with a total ordering and we provide several algorithms to transform a system into a set of monotone events. As we deal with monotone systems, the coupling technique requires less computational efforts for each iteration. Numerical examples show that we can obtain very important speedups.