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.
@article{JSFS_2007__148_4_5_0, author = {Andersen, Hans C. and Diaconis, Persi}, title = {Hit and run as a unifying device}, journal = {Journal de la soci\'et\'e fran\c caise de statistique}, pages = {5--28}, publisher = {Soci\'et\'e fran\c caise de statistique}, volume = {148}, number = {4}, year = {2007}, language = {en}, url = {http://www.numdam.org/item/JSFS_2007__148_4_5_0/} }
Andersen, Hans C.; Diaconis, Persi. Hit and run as a unifying device. Journal de la société française de statistique, Tome 148 (2007) no. 4, pp. 5-28. http://www.numdam.org/item/JSFS_2007__148_4_5_0/
[1] “Reversible Markov chains and random walks on graphs”, monograph in preparation, drafts available online.
, and (2007).[2] “Molecular dynamics simulations at constant pressure and/or temperature”, J. Chem. Phys. 72, 2384-2393 (1980).
(1980).[3] “Convergence properties of hit and run samplers”, Comm. Statist-Stochastic Models 14, 767-800. | MR 1631518 | Zbl 0912.65121
, , and (1998).[4] “Hit and run algorithms for generating multivariate distributions”, Math. Oper. Res. 18, 255-266. | MR 1250117 | Zbl 0771.60052
, , and (1993).[5] “Trivial intersection of -fields and Gibbs sampling”, to appear Annals of Probability. | MR 2478681 | Zbl 1159.60007
, , and (2007).[6] “Spatial statistics and Bayesian computation” (with discussion), J. Roy. Statist. Soc. B 16, 395-407. | MR 1210422 | Zbl 0800.62572
, and (1993).[7] “Non-existence of everywhere proper conditional distributions”, Ann. Math. Statist. 34, 223-225. | MR 148097 | Zbl 0122.13202
, and (1963).[8] “Exact sampling, regeneration and minorization conditions”, preprint, Dept. of Statistics, Harvard University.
, and (2007).[9] “Constraints redundancy and feasible region boundedness by random feasible point generator (RGPG)”, Third European Congress on Operations Research - EURO III, Amsterdam.
, and (1979).[10] “Torpid mixing of some MCMC algorithms in statistical physics”, Proc. 40th IEEE Symp. on Foundations of Computer Science (FOCS) 218-229. | MR 1917562
, , , , , , and (1999).[11] “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
, , , and (2004).[12] “A New Variant of the Monte Carlo Method”, Th. Probabl. Appl. 36, 355-360. | MR 1119508 | Zbl 0776.65067
(1991).[13] “Probability”, Addison-Wesley, Reading, Mass. | MR 229267 | Zbl 0174.48801
(1968).[14] “Path integrals in the theory of condensed helium”, Rev. Mod. Phys. 67, 279-355.
(1995).[15] “Sequential Monte-Carlo methods for statistical analysis of tables”, Jour. Amer. Statist. Assoc. 100, 109-120. | MR 2156822 | Zbl 1117.62310
, , , and (2005).[16] “Monte Carlo Methods in Bayesian Computation”, Springer, New York. | MR 1742311 | Zbl 0949.65005
, , and (2000).[17] “Performance of Gibbs, hit and run and Metropolis samplers”, Jour. Comput. Graph. Statist. 2, 251-272. | MR 1272394
, and (1993).[18] “Billiards in a general domain with random reflectors”, arXiv:math 061279941.
, , , and (2007).[19] “Recoil growth: An efficient simulation method for multi-polymer systems”, J. Chem. Phys. 110, 3220-3228.
, , , and (1999).[20] “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
, , , and (2006).[21] “Gibbs sampling for Bayesian nonconjugate models using auxiliary variables”, J. Roy. Statist. Soc. B 61, 331-344. | MR 1680334 | Zbl 0913.62028
, , and (1999).[22] “Group representations in probability and statistics”, IMS, Hayward, Mass. | MR 964069 | Zbl 0695.60012
(1988).[23] “Analysis of a Bose-Einstein Markov chain”, Annal. Institut H. Poincaré PR 41, 409-418. | Numdam | MR 2139027 | Zbl 1130.60012
(2003).[24] “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
, and (1985).[25] “Rectangular arrays with fixed margins”, in Discrete Probability and Algorithms, D. Aldous et al., eds., Springer-Verlag, New York. | MR 1380519 | Zbl 0839.05005
, and (1994).[26] “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
, , and (1999).[27] “Stein's Method: Expository Lectures and Applications”, Institute of Mathematical Statistics, Beachwood, Ohio; Chapter 1. | MR 2118599 | Zbl 1079.62024
, and (2004).[28] “Analysis of a non-reversible Markov chain sampler”, Annals Appl. Probab. 10, 726-752. | MR 1789978 | Zbl 1083.60516
, , and (2000).[29] “Gibbs sampling, exponential families and orthogonal polynomials”, to appear Statistical Science. | MR 2446500
, , and (2007).[30] “Gibbs sampling, exponential families and coupling”, preprint, Dept. of Statistics, Stanford University.
, , and (2007A).[31] “Stochastic alternating projections”, preprint, Dept. of Statistics, Stanford University.
, , and (2007B).[32] “Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques”, Michigan Jour. Math. 48, 157-190. | MR 1786485 | Zbl 0998.60069
, and (2000).[33] “Algebraic algorithms for sampling from conditional distributions”, Annals Statist. 26, 363-397. | MR 1608156 | Zbl 0952.62088
, and (1998).[34] “Hybrid Monte Carlo”, Phys. Lett. B 195, 216-222.
, , , and (1987).[35] “Systematic scan for sampling colorings”, Ann. Appl. Probab. 16, 185-230. | MR 2209340 | Zbl 1095.60024
, , and (2006).[36] “Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo Algorithm”, Phys. Rev. D 38, 2009-2012. | MR 965465
, and (1988).[37] “Novel scheme to study structural and thermal properties of continuously deformable molecules”, J. Phys.: Condens. Matter 3, 3053-3076.
, , and (1991).[38] “Understanding Molecular Simulation - From Algorithms to Applications”, 2nd edition, Academic Press, San Diego. | Zbl 0889.65132
and (2001).[39] “Slow mixing of the Glauber dynamics for the hard core model on the Hamming cube”, Proc. Annual Symp. Disc. Algo. (SODA) 459-460.
, and (2004).[40] “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.
(1991).[41] “The Burnside process mixes slowly”, Combinatorics, Probability, and Computing 11, 21-34. | MR 1888180 | Zbl 1008.68085
, and (2002).[42] “The Swendsen Wang process does not always mix rapidly”, J. Stat. Phys. 97, 67-86. | MR 1733467 | Zbl 1006.82015
, and (1999).[43] “Auxiliary variable methods for Markov chain Monte Carlo with applications”, Jour. Amer. Statist. Assoc. No. 442, 585-595. | Zbl 0953.62103
(1998).[44] “Exchange Monte Carlo method and application to spin glass simulations”, J. Phys. Soc. Japan 65, 1604-1608.
, and (1996).[45] “Uniform sampling modulo a group of symmetries using Markov chain simulation”, DIMACS Series in Discrete Math 10, 37-47. | MR 1235566 | Zbl 0814.68077
(1993).[46] “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
, , and (2002).[47] “A theory of statistical models for Monte-Carlo integration” (with discussion), J. Roy. Statist. Soc. B 65, 585-618. | MR 1998624 | Zbl 1067.62054
, , , , and (2003).[48] “Monte Carlo Strategies in Scientific Computing”, Springer-Verlag, New York. | MR 1842342 | Zbl 0991.65001
(2001).[49] “Hit and run mixes fast”, Math. Program. 86, 443-461. | MR 1733749 | Zbl 0946.90116
(1999).[50] “Hit and run is fast and fun”, preprint, Microsoft Research.
, and (2003).[51] “Hit and run from a corner”, SIAM J. Comput. 35, 985-1005. | MR 2203735 | Zbl 1103.52002
, and (2006).[52] “Non-null ranking models, I.” Biometrika 44, 114-130. | MR 87267 | Zbl 0087.34001
(1957).[53] “Analyzing and modeling rank data”, Chapman and Hall, London. | MR 1346107 | Zbl 0853.62006
(1995).[54] “Slice sampling”, Annals of Statist. 31, 705-767. | MR 1994729 | Zbl 1051.65007
(2003).[55] “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
(2001).[56] “Convergence of slice sampler Markov chains”, J. Royal Statist. Soc. B 61, 643-660. | MR 1707866 | Zbl 0929.62098
and (1999).[57] “Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions”, Oper. Res. 32, 1296-1308. | MR 775260 | Zbl 0552.65004
(1984).[58] “Nonuniversal critical dynamics in Monte Carlo simulations”, Phys. Rev. Lett. 58, 86-88.
, and (1987).[59] “The calculation of posterior distributions by data augmentation”, J. Amer. Statist. Assoc. 82, 528-550. | MR 898357 | Zbl 0619.62029
, and (1987).[60] “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
(2006).[61] “On the computation of multidimensional integrals by the Monte Carlo Method”, Th. Probabl. Appl. 16, 720-724. | MR 292259 | Zbl 0257.65030
(1971).[62] “The statistical work of Lucian Le Cam”, Ann. Statist. 30, 631-682. | MR 1922537 | Zbl 1103.62301
(2002).[63] “The art of data augmentation”, Jour. Comp. Graph. Statist. 10, 1-111. | MR 1936358
, and (2001).[64] “Estimation of a covariance matrix using the reference prior”, Ann. Statist. 22, 1195-1211. | MR 1311972 | Zbl 0819.62013
, and (1994).