Hit and run as a unifying device

Andersen, Hans C.; Diaconis, Persi

Journal de la Société française de statistique & Revue de statistique appliquée, Tome 148 (2007) no. 4, pp. 5-28.

Nous présentons une généralisation des algorithmes de «hit and run» en Markov chain Monte Carlo. Cette généralisation est ‘équivalente' aux méthodes de type data augmentation et auxiliary variables. La classe d'algorithmes ainsi obtenue contient comme cas particuliers l'échantillonnage de Gibbs et les block spin dynamics de Swendsen et Wang. Cette unification permet aux théorèmes, exemples et heuristiques développés dans l'un ou l'autre de ces contextes de venir éclairer de façon intéressante les approches ainsi mises en parallèle.

We present a generalization of hit and run algorithms for Markov chain Monte Carlo problems that is ‘equivalent' to data augmentation and auxiliary variables. These algorithms contain the Gibbs sampler and Swendsen-Wang block spin dynamics as special cases. The unification allows theorems, examples, and heuristics developed in one domain to illuminate parallel domains.

Mots clés : Markov chain Monte Carlo algorithms, hit and run, data augmentation, auxiliary variables, Swedsen-Wang algorithm, Burnside process

[1] Aldous D., and Fill J. (2007). “Reversible Markov chains and random walks on graphs”, monograph in preparation, drafts available online.

[2] Andersen H. C. (1980). “Molecular dynamics simulations at constant pressure and/or temperature”, J. Chem. Phys. 72, 2384-2393 (1980).

[3] Belisle C., Boneh A., and Caron R. (1998). “Convergence properties of hit and run samplers”, Comm. Statist-Stochastic Models 14, 767-800. | MR | Zbl

[4] Belisle C., Romeijn H., and Smith R. (1993). “Hit and run algorithms for generating multivariate distributions”, Math. Oper. Res. 18, 255-266. | MR | Zbl

[5] Berti P., Platelli L., and Rigo P. (2007). “Trivial intersection of $\sigma$-fields and Gibbs sampling”, to appear Annals of Probability. | MR | Zbl

[6] Besag J., and Green P. (1993). “Spatial statistics and Bayesian computation” (with discussion), J. Roy. Statist. Soc. B 16, 395-407. | MR | Zbl

[7] Blackwell D., and Ryll-Nardzewski C. (1963). “Non-existence of everywhere proper conditional distributions”, Ann. Math. Statist. 34, 223-225. | MR | Zbl

[8] Blanchet J., and Meng X. (2007). “Exact sampling, regeneration and minorization conditions”, preprint, Dept. of Statistics, Harvard University.

[9] Boneh A., and Golan A. (1979). “Constraints redundancy and feasible region boundedness by random feasible point generator (RGPG)”, Third European Congress on Operations Research - EURO III, Amsterdam.

[10] Borgs C., Chayes J., Frieze A., Kim J., Tetali P., Vigoda E., and Vu V. (1999). “Torpid mixing of some MCMC algorithms in statistical physics”, Proc. 40th IEEE Symp. on Foundations of Computer Science (FOCS) 218-229. | MR

[11] Borgs C., Chase J., Dyer M., and Tetali P. (2004). “On the sampling problem for H-coloring on the hypercubic lattice”, DIMACS Series in Discrete Math. and Computer Science 63, 13-28. | MR | Zbl

[12] Borovkov K. (1991). “A New Variant of the Monte Carlo Method”, Th. Probabl. Appl. 36, 355-360. | MR | Zbl

[13] Breiman L. (1968). “Probability”, Addison-Wesley, Reading, Mass. | MR | Zbl

[14] Ceperley D. M. (1995). “Path integrals in the theory of condensed helium”, Rev. Mod. Phys. 67, 279-355.

[15] Chen Y., Diaconis P., Holmes S., and Liu J. (2005). “Sequential Monte-Carlo methods for statistical analysis of tables”, Jour. Amer. Statist. Assoc. 100, 109-120. | MR | Zbl

[16] Chen M., Shao Q., and Ibrahim J. (2000). “Monte Carlo Methods in Bayesian Computation”, Springer, New York. | MR | Zbl

[17] Chen M., and Schmeiser B. (1993). “Performance of Gibbs, hit and run and Metropolis samplers”, Jour. Comput. Graph. Statist. 2, 251-272. | MR

[18] Comets F., Popov S., Schutz G., and Vachkovskaia V. (2007). “Billiards in a general domain with random reflectors”, arXiv:math 061279941.

[19] Consta S., Wilding N. B., Frenkel D., and Alexandrowicz Z. (1999). “Recoil growth: An efficient simulation method for multi-polymer systems”, J. Chem. Phys. 110, 3220-3228.

[20] Cryan M., Dyer M., Goldberg L., and Jerrum M. (2006). “Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows”, SIAM J. Comput. 36, 247-278. | MR | Zbl

[21] Damien P., Walker S., and Wakefield J. (1999). “Gibbs sampling for Bayesian nonconjugate models using auxiliary variables”, J. Roy. Statist. Soc. B 61, 331-344. | MR | Zbl

[22] Diaconis P. (1988). “Group representations in probability and statistics”, IMS, Hayward, Mass. | MR | Zbl

[23] Diaconis P. (2003). “Analysis of a Bose-Einstein Markov chain”, Annal. Institut H. Poincaré PR 41, 409-418. | Numdam | MR | Zbl

[24] Diaconis P., and Efron B. (1985). “Testing for independendence in a two-way table: New interpretations of the chi-square statistic”, Ann. Statist. 13, 845-913. | MR | Zbl

[25] Diaconis P., and Gangolli A. (1994). “Rectangular arrays with fixed margins”, in Discrete Probability and Algorithms, D. Aldous et al., eds., Springer-Verlag, New York. | MR | Zbl

[26] Diaconis P., Graham R., and Holmes S. (1999). “Statistical problems involving permutations with restricted positions”, in M. de Gunst et al., ed., “State of the art in probability and statistics”, IMS, Benchwood, OH., pp. 195-222. | MR

[27] Diaconis P., and Holmes S. (2004). “Stein's Method: Expository Lectures and Applications”, Institute of Mathematical Statistics, Beachwood, Ohio; Chapter 1. | MR | Zbl

[28] Diaconis P., Holmes S., and Neal R. (2000). “Analysis of a non-reversible Markov chain sampler”, Annals Appl. Probab. 10, 726-752. | MR | Zbl

[29] Diaconis P., Khare K., and Saloff-Coste L. (2007). “Gibbs sampling, exponential families and orthogonal polynomials”, to appear Statistical Science. | MR

[30] Diaconis P., Khare K., and Saloff-Coste L. (2007A). “Gibbs sampling, exponential families and coupling”, preprint, Dept. of Statistics, Stanford University.

[31] Diaconis P., Khare K., and Saloff-Coste L. (2007B). “Stochastic alternating projections”, preprint, Dept. of Statistics, Stanford University.

[32] Diaconis P., and Ram A. (2000). “Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques”, Michigan Jour. Math. 48, 157-190. | MR | Zbl

[33] Diaconis P., and Sturmfels B. (1998). “Algebraic algorithms for sampling from conditional distributions”, Annals Statist. 26, 363-397. | MR | Zbl

[34] Duane S., Kennedy A. D., Pendleton B. J., and Roweth D. (1987). “Hybrid Monte Carlo”, Phys. Lett. B 195, 216-222.

[35] Dyer M., Goldberg L., and Jerrum M. (2006). “Systematic scan for sampling colorings”, Ann. Appl. Probab. 16, 185-230. | MR | Zbl

[36] Edwards R. O., and Sokal A. D. (1988). “Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo Algorithm”, Phys. Rev. D 38, 2009-2012. | MR

[37] Frenkel D., Mooij G. C. A. M., and Smit B. (1991). “Novel scheme to study structural and thermal properties of continuously deformable molecules”, J. Phys.: Condens. Matter 3, 3053-3076.

[38] Frenkel D. and Smit B. (2001). “Understanding Molecular Simulation - From Algorithms to Applications”, 2nd edition, Academic Press, San Diego. | Zbl

[39] Galvin D., and Tetali P. (2004). “Slow mixing of the Glauber dynamics for the hard core model on the Hamming cube”, Proc. Annual Symp. Disc. Algo. (SODA) 459-460.

[40] Geyer C. J. (1991). “Markov chain Monte Carlo maximum likelihood”, in E. Keramigas (ed.) “Computing Science and Statistics: The 23rd symposium on the interface”, Interface Foundation, Fairfax, pp. 156-163.

[41] Goldberg L., and Jerrum M. (2002). “The Burnside process mixes slowly”, Combinatorics, Probability, and Computing 11, 21-34. | MR | Zbl

[42] Gore V., and Jerrum M. (1999). “The Swendsen Wang process does not always mix rapidly”, J. Stat. Phys. 97, 67-86. | MR | Zbl

[43] Higdon D. (1998). “Auxiliary variable methods for Markov chain Monte Carlo with applications”, Jour. Amer. Statist. Assoc. No. 442, 585-595. | Zbl

[44] Hukushima K., and Nemoto K. (1996). “Exchange Monte Carlo method and application to spin glass simulations”, J. Phys. Soc. Japan 65, 1604-1608.

[45] Jerrum M. (1993). “Uniform sampling modulo a group of symmetries using Markov chain simulation”, DIMACS Series in Discrete Math 10, 37-47. | MR | Zbl

[46] Kiatsupaibul S., Smith R., and Zabinsky Z. (2002). “A discrete hit and run algorithm for generating samples from general discrete multivariate distributions”, preprint, Dept. of Industrial Relations and Operations Engineering, University of Michigan

[47] Kong A., Meng X., Mccullagh P., Nicolae D., and Tan Z. (2003). “A theory of statistical models for Monte-Carlo integration” (with discussion), J. Roy. Statist. Soc. B 65, 585-618. | MR | Zbl

[48] Liu J. S. (2001). “Monte Carlo Strategies in Scientific Computing”, Springer-Verlag, New York. | MR | Zbl

[49] Lovasz L. (1999). “Hit and run mixes fast”, Math. Program. 86, 443-461. | MR | Zbl

[50] Lovasz L., and Vempala S. (2003). “Hit and run is fast and fun”, preprint, Microsoft Research.

[51] Lovasz L., and Vempala S. (2006). “Hit and run from a corner”, SIAM J. Comput. 35, 985-1005. | MR | Zbl

[52] Mallows C. (1957). “Non-null ranking models, I.” Biometrika 44, 114-130. | MR | Zbl

[53] Marden J. (1995). “Analyzing and modeling rank data”, Chapman and Hall, London. | MR | Zbl

[54] Neal R. (2003). “Slice sampling”, Annals of Statist. 31, 705-767. | MR | Zbl

[55] Pak I. (2001). “What do we know about the product replacement algorithm?”, in “Groups and Computation III”, Kantor, W., and Seress, A. eds., De Gruyter, Berlin, pp. 301-347. | MR | Zbl

[56] Roberts G. and Rosenthal J. (1999). “Convergence of slice sampler Markov chains”, J. Royal Statist. Soc. B 61, 643-660. | MR | Zbl

[57] Smith R. (1984). “Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions”, Oper. Res. 32, 1296-1308. | MR | Zbl

[58] Swensen R. H., and Wang J.-S. (1987). “Nonuniversal critical dynamics in Monte Carlo simulations”, Phys. Rev. Lett. 58, 86-88.

[59] Tanner M., and Wong W. (1987). “The calculation of posterior distributions by data augmentation”, J. Amer. Statist. Assoc. 82, 528-550. | MR | Zbl

[60] Ter Braak C. J. F. (2006). “A Markov Chain Monte Carlo version of the genetic algorithm Differential Evolution: easy Bayesian computing for real parameter spaces”, Stat Comput 16, 239-249. | MR

[61] Turcin V. (1971). “On the computation of multidimensional integrals by the Monte Carlo Method”, Th. Probabl. Appl. 16, 720-724. | MR | Zbl

[62] Van Der Vaart A. (2002). “The statistical work of Lucian Le Cam”, Ann. Statist. 30, 631-682. | MR | Zbl

[63] Van Dyk D., and Meng X. (2001). “The art of data augmentation”, Jour. Comp. Graph. Statist. 10, 1-111. | MR

[64] Yang R., and Berger J. (1994). “Estimation of a covariance matrix using the reference prior”, Ann. Statist. 22, 1195-1211. | MR | Zbl