Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 6 (2001) > Paper 8 open journal systems 


How to Combine Fast Heuristic Markov Chain Monte Carlo with Slow Exact Sampling

Antar Bandyopadhyay, University of California, Berkeley
David J. Aldous, University of California, Berkeley


Abstract
Given a probability law $pi$ on a set S and a function $g : S rightarrow R$, suppose one wants to estimate the mean $bar{g} = int g dpi$. The Markov Chain Monte Carlo method consists of inventing and simulating a Markov chain with stationary distribution $pi$. Typically one has no a priori bounds on the chain's mixing time, so even if simulations suggest rapid mixing one cannot infer rigorous confidence intervals for $bar{g}$. But suppose there is also a separate method which (slowly) gives samples exactly from $pi$. Using n exact samples, one could immediately get a confidence interval of length O(n-1/2). But one can do better. Use each exact sample as the initial state of a Markov chain, and run each of these n chains for m steps. We show how to construct confidence intervals which are always valid, and which, if the (unknown) relaxation time of the chain is sufficiently small relative to m/n, have length O(n-1 log n) with high probability.


Full text: PDF

Pages: 79-89

Published on: July 28, 2001
Bibliography
  1. D.J. Aldous and J.A. Fill. (2001), Reversible Markov chains and random walks on graphs. Book in preparation. Math. Review number not available.
  2. N. Alon and J. H. Spencer. (1992), The Probabilistic Method. Wiley. Math. Review 93h:60002
  3. E. Behrends. (2000), Introduction to Markov Chains, with special emphasis on rapid mixing. Veiweg. Math. Review 2000j:60083
  4. M. H. Chen, Q. M. Shao, and J.G. Ibrahim. (2000), Monte Carlo Methods in Bayesian Computation. Springer-Verlag. Math. Review 2000k:65014
  5. P. Diaconis and L. Saloff-Coste. (1998), What do we know about the Metropolis algorithm ? J. Comput. System Sci. 57 20-36. Math. Review 2000b:68094
  6. S.T. Garren and R.L. Smith. (2000), Estimating the second largest eigenvalue of a Markov transition matrix. Bernoulli 6 215--242. Math. Review 2001b:60087
  7. W.R. Gilks, S. Richardson, and D.J. Spiegelhalter, editors. (1996), Markov Chain Monte Carlo in Practice. London, Chapman and Hall. Math. Review 97d:62006
  8. P. Lezaud. (1998), Chernoff-type bound for finite Markov chains. Ann. Appl. Probab. 8 849--867. Math. Review 99f:60061
  9. J.S. Liu. (2001), Monte Carlo Strategies in Scientific Computing. Springer. Math. Review number not available.
  10. D. Randall and A. Sinclair. (2000), Self-testing algorithms for self-avoiding walks. J. Math. Phys. 41 1570--1584. Math. Review 2001c:82033
  11. C.P. Robert, editor. (1998), Discretization and MCMC Convergence Assessment. Number 135 in Lecture Notes in Statistics. Springer-Verlag. Math. Review 99m:65012
  12. C.P. Robert and G. Casella. (1999), Monte Carlo Statistical Methods. Springer-Verlag. Math. Review 2001g:62020















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X