Hit and run as a unifying device

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.

[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 1631518 | Zbl 0912.65121

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

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

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

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

[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 1917562

[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 2056236 | Zbl 1074.05032

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

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

[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 2156822 | Zbl 1117.62310

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

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

[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 2231648 | Zbl 1117.62062

[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 1680334 | Zbl 0913.62028

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

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

[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 803747 | Zbl 0593.62040

[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 1380519 | Zbl 0839.05005

[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 1836562

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

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

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

[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 1786485 | Zbl 0998.60069

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

[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 2209340 | Zbl 1095.60024

[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 965465

[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 0889.65132

[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 1888180 | Zbl 1008.68085

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

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

[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 1235566 | Zbl 0814.68077

[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 1998624 | Zbl 1067.62054

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

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

[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 2203735 | Zbl 1103.52002

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

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

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

[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 1829489 | Zbl 0986.68172

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

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

[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 898357 | Zbl 0619.62029

[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 2242236

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

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

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

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