Previous: 31st October 2003 - Gaussian processes for density estimation
Next: 14th November 2003 - Active Learning

7th November 2003 - Exact Sampling

Chris Holmes and David MacKay are going to present on exact sampling methods.

Main readings:

Introduction: Chapter 32, Information Theory, Inference, and Learning Algorithms "Exact Monte Carlo Sampling" (pages 413-421)

Chris Holmes's work: perhaps one of these.

For further reading, impressive pictures of exact samples from other distributions, and generalizations of the exact sampling method, browse the perfectly-random sampling website.

For beautiful exact-sampling demonstrations running live in your web-browser, see Jim Propp's website.

While the above give a good intuition for how exact sampling works, they do not give a rigorous explanation of the key "monotonicity" property that is used in most exact sampling methods. For more rigor in this area, see section 2.2 onwards (p.7 onwards) in http://citeseer.nj.nec.com/propp96exact.html (27 pages)

@article{Propp1996,
  title={Exact Sampling with Coupled {M}arkov Chains and Applications to
    Statistical Mechanics},
  author={Propp, J. G. and Wilson, D. B.},
  journal={Random Structures and Algorithms},
  year={1996},
  volume={9},
  number={1-2},
  pages={223-252}
}

Local copy at Gatsby in ~mackay/sample.ps.gz

Iain Murray.