Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From David J.C. MacKay's Information Theory, Inference, and Learning Algorithms

  1. 32.2 Exact sampling concepts

    Propp and Wilson's exact sampling method (also known as "perfect simulation" or "coupling from the past") depends on three ideas.

    Coalescence of coupled Markov chains ...

    Coupling from the past ...

    Monotonicity ...

    I tried to understand the three ideas, but the explanations there are not formal enough for me to understand what they are trying to say. So I wonder in settings that are as general as possible, such as for stochastic processes or Markov processes or Markov chains, how the concepts are defined or how the ideas are explained? I searched in a few books on Markov chains and Markov processes, but couldn't locate the concepts or ideas due to my limited capability.

  2. For the first idea:

    First, if several Markov chains starting from different initial conditions share a single random-number generator, then their trajectories in state space may coalesce; and, having, coalesced, will not separate again.

    Figure 32.1a-i shows twenty-one Markov chains identical to the one described in section 29.4, which samples from {0, 1,..., 20} using the Metropolis algorithm (figure 29.12, p.370); each of the chains has a different initial condition but they are all driven by a single random number generator; the chains coalesce after about 80 steps.

    ...

    Figure 32.1b shows similar Markov chains, each of which has identical proposal density to those in section 29.4 and figure 32.1a; but in figure 32.1b, the proposed move at each step, 'left' or 'right', is obtained in the same way by all the chains at any timestep, independent of the current state. This coupling of the chains changes the statistics of coalescence. Because two neighbouring paths only merge when a rejection occurs, and rejections only occur at the walls (for this particular Markov chain), coalescence will occur only when the chains are all in the leftmost state or all in the rightmost state.

    enter image description here

    Do "several Markov chains ... share a single random-number generator" for a(i) and "the proposed move at each step, 'left' or 'right', is obtained in the same way by all the chains at any timestep, independent of the current state" for b mean the same?

    If yes, why does the coalescence in figure 32.1 a(i) happen not when the chains are all in the leftmost state or all in the rightmost state?

Thanks!

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.