Coupling from the past

Coupling from the past

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 π (π is a probability vector). Suppose that we come up with a probability distribution μ 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 fj for j\in\mathbb Z be independent samples from μ.

Suppose that x is chosen randomly according to π and is independent from the sequence fj. (We do not worry for now where this x is coming from.) Then f − 1(x) is also distributed according to π, because π is M-stationary and our assumption on the law of f. Define

F_j:= f_{-1}\circ f_{-2}\circ\cdots\circ f_{-j}.

Then it follows by induction that Fj(x) is also distributed according to π for every j\in\mathbb N. Now here is the main point. It may happen that for some n\in\mathbb N the image of the map Fn is a single element of S. In other words, Fn(x) = Fn(y) for each y\in S. Therefore, we do not need to have access to x in order to compute Fn(x). The algorithm then involves finding some n\in \mathbb N such that Fn(S) is a singleton, and outputing the element of that singleton. The design of a good distribution μ for which the task of finding such an n and computing Fn is not too costly is not always obvious, but has been accomplished successfully in several important instances[citation needed].

The monotone case

There is a special class of Markov chains in which there are particularly good choices for μ and a tool for determining if | Fn(S) | = 1. (Here |\cdot| denotes cardinality.) Suppose that S is a partially ordered set with order \le, which has a unique minimal element s0 and a unique maximal element s1; that is, every s\in S satisfies s_0\le s\le s_1. Also, suppose that μ may be chosen to be supported on the set of monotone maps f:S\to S. Then it is easy to see that | Fn(S) | = 1 if and only if Fn(s0) = Fn(s1), since Fn is monotone. Thus, checking this becomes rather easy. The algorithm can proceed by choosing n: = n0 for some constant n0, sampling the maps f_{-1},\dots,f_{-n}, and outputing Fn(s0) if Fn(s0) = Fn(s1). If F_n(s_0)\ne F_n(s_1) the algorithm proceeds by doubling n and repeating as necessary until an output is obtained. (But the algorithm does not resample the maps f j which were already sampled; it uses the previously sampled maps when needed.)

References

  • Propp, James Gary; Wilson, David Bruce (1996), Exact sampling with coupled Markov chains and applications to statistical mechanics, "Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995)", Random Structures & Algorithms 9 (1): 223–252, ISSN 1042-9832, MR1611693 
  • Propp, James; Wilson, David (1998), "Coupling from the past: a user's guide", Microsurveys in discrete probability (Princeton, NJ, 1997), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 41, Providence, R.I.: American Mathematical Society, pp. 181–192, MR1630414 

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • The Time Traveler's Wife — This article is about the novel. For the film adaptation, see The Time Traveler s Wife (film). The Time Traveler s Wife   …   Wikipedia

  • The Fight Network — Infobox TV channel name = The Fight Network logofile = TFN.gif logoalt = logosize = launch = September 21, 2005 closed date = picture format = network = owner = TFN Global Inc slogan = country = Canada broadcast area = National headquarters =… …   Wikipedia

  • Coupling (UK TV series) — Coupling Coupling intertitle (series 1–3) Format British sitcom Written by Steven Moffat …   Wikipedia

  • The Office (U.S. TV series) — The Office Genre Sitcom Mockumentary Created by Ricky Gervais Stephen Merchant …   Wikipedia

  • The Boston Globe — Tipo Periódico (diario) Formato Gran formato País …   Wikipedia Español

  • The Dark Energy Survey — DES logo The Dark Energy Survey (DES) is a survey that aims to probe the dynamics of the expansion of the universe and the growth of large scale structure. The collaboration is composed of research institutes and universities from United… …   Wikipedia

  • The Office (US TV series) season 1 — infobox tvseason season name = The Office Season 1 caption = Tagline: An NBC comedy not for everyone. Just anyone that works. dvd release date = August 16, 2005 Region 1April 10, 2006 Region 2 dvd format = Widescreen Anamorphic boxed set country …   Wikipedia

  • The Cosby Show — Not to be confused with Cosby or The Bill Cosby Show. The Cosby Show The Cosby Show logo used for six of the series eight seasons Format Sitcom Created by Ed …   Wikipedia

  • The Boston Globe — Infobox Newspaper name = caption = The February 28, 2008 front page of The Boston Globe type = Daily newspaper format = Broadsheet foundation = 1872 owners = The New York Times Company headquarters = 135 Morrissey Boulevard Boston, Massachusetts …   Wikipedia

  • The Wake (band) — Infobox musical artist Name = The Wake Background = group or band Origin = Glasgow, Scotland Genre = Post punk, Indie pop Years active = 1982 ndash;1994 Label = Factory Records, Sarah RecordsThe Wake were a British post punk and later indie pop… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”