e/Coupling from the past

Information
has gloss	eng: Among Markov chain Monte Carlo (MCMC) algorithms, coupling from the past is a method for sampling from the stationary distribution of a Markov chain. Contrary to many MCMC algorithms, coupling from the past gives in principle a perfect sample from the stationary distribution. It was invented by James Propp and David Wilson in 1996. The basic idea Consider a finite state irreducible aperiodic Markov chain M with state space S and (unique) stationary distribution \pi (\pi is a probability vector). Suppose that we come up with a probability distribution \mu on the set of maps f:S\to S with the property that for every fixed s\in S, its image f(s) is distributed according to the transition probability of M from state s. An example of such a probability distribution is the one where f(s) is independent from f(s) whenever s\ne s, but it is often worthwhile to consider other distributions. Now let f_j for j\in\mathbb Z be independent samples from \mu.
lexicalization	eng: coupling from the past
instance of	e/Monte Carlo method