  Inference for belief networks using Gibbs sampling produces a distribution
for unobserved variables that differs from the correct distribution by a
(usually) unknown error, since convergence to the right distribution occurs
only asymptotically. The method of "coupling from the past" samples from
exactly the correct distribution by (conceptually) running dependent Gibbs
sampling simulations from every possible starting state from a time far enough
in the past that all runs reach the same state at time t=0. Explicitly
considering every possible state is intractable for large networks, however. We
propose a method for layered noisy-or networks that uses a compact, but often
imprecise, summary of a set of states. This method samples from exactly the
correct distribution, and requires only about twice the time per step as
ordinary Gibbs sampling, but it may require more simulation steps than would be
needed if chains were tracked exactly.
