Sampling the Fermi statistics and other conditional product measures

Gaudillière, A.; Reygner, J.

Annales de l'I.H.P. Probabilités et statistiques, Tome 47 (2011) no. 3, pp. 790-812.

En définissant un algorithme de type Metropolis dont le coût de chaque pas est d'ordre 1, nous construisons une chaîne de Markov dont la mesure d'équilibre est donnée par la statistique de Fermi canonique pour k particules sans interaction parmi m niveaux d'énergie. Uniformément en la température, ainsi qu'en les énergies et capacités des différents niveaux d'énergie, nous donnons une majoration explicite et de terme dominant km ln k du temps de mélange de la dynamique. Nous obtenons cette construction et cette majoration comme cas particulier d'un résultat général sur les produits (non homogènes) de mesures ultra log-concaves (comme les lois binômiales ou de Poisson) sous une contrainte globale. Ce résultat général fournit aussi une majoration indépendante du désordre pour le temps de mélange du processus d'exclusion simple sur le graphe complet en potentiel aléatoire. Il découle d'un argument de couplage élémentaire, est illustré dans une appendice de simulations et étendu aux produits (non homogènes) de mesures log-concaves.

Through a Metropolis-like algorithm with single step computational cost of order one, we build a Markov chain that relaxes to the canonical Fermi statistics for k non-interacting particles among m energy levels. Uniformly over the temperature as well as the energy values and degeneracies of the energy levels we give an explicit upper bound with leading term km ln k for the mixing time of the dynamics. We obtain such construction and upper bound as a special case of a general result on (non-homogeneous) products of ultra log-concave measures (like binomial or Poisson laws) with a global constraint. As a consequence of this general result we also obtain a disorder-independent upper bound on the mixing time of a simple exclusion process on the complete graph with site disorder. This general result is based on an elementary coupling argument, illustrated in a simulation appendix and extended to (non-homogeneous) products of log-concave measures.

Classification : 60J10, 82C44
Mots clés : metropolis algorithm, Markov chain, sampling, mixing time, product measure, conservative dynamics

[1] C. Ané, S. Blachère, D. Chafaï, P. Fougères, I. Gentil, F. Malrieu, C. Roberto and G. Scheffer. Sur les Inégalités de Sobolev Logarithmiques. Panoramas et Synthèses 10. Soc. Math. France, Paris, 2000. | MR | Zbl

[2] D. Bakry and M. Émery. Diffusions hypercontractives. In Séminaire de Probabilités, XIX, 1983/84 177-206. Lecture Notes in Math. 1123. Springer, Berlin, 1985. | Numdam | MR | Zbl

[3] A. S. Boudou, P. Caputo, P. Dai Pra and G. Posta. Spectral gap inequalities for interacting particle systems via a Bochner type inequality. J. Funct. Anal. 232 (2006) 222-258. | MR | Zbl

[4] P. Caputo. Spectral gap inequalities in product spaces with conservation laws. In Stochastic Analysis on Large Scale Interacting Systems 53-88. T. Funaki and H. Osada (Eds). Adv. Stud. Pure Math. 39. Math. Soc. Japan, Tokyo, 2004. | MR | Zbl

[5] P. Caputo. On the spectral gap of the Kac walk and other binary collision processes. ALEA Lat. Am. J. Probab. Math. Stat. 4 (2008) 205-222. | MR | Zbl

[6] P. Caputo, P. Dai Pra and G. Posta. Convex entropy decay via the Bochner-Bakry-Emery approach. Ann. Inst. H. Poincaré Probab. Statist. 45 (2009) 734-753. Available at arXiv:0712.2578. | Numdam | MR | Zbl

[7] A. Iovanella, B. Scoppola and E. Scoppola. Some spin glass ideas applied to the clique problem. J. Stat. Phys. 126 (2007) 895-915. | MR | Zbl

[8] O. Johnson. Bounds on the Poincaré constant of ultra log-concave random variables. Preprint, Univ. Bristol, 2008. Available at arXiv:0801.2112.

[9] A. Joulin and Y. Ollivier. Curvature, concentration, and error estimates for Markov chain Monte Carlo. Ann. Probab. 38 (2010) 2418-2442. Available at arXiv:0904.1312. | MR | Zbl

[10] C. Landim and J. Noronha Neto. Poincaré and logarithmic Sobolev inequality for Ginzburg-Landau processes in random environment. Probab. Theory Related Fields 131 (2005) 229-260. | MR | Zbl

[11] D. A. Levin, Y. Peres and E. L. Wilmer. Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI, 2008. | MR | Zbl

[12] T. M. Liggett. Ultra logconcave sequences and negative dependence. J. Combin. Theory Ser. A 79 (1997) 315-325. | MR | Zbl

[13] R. Montenegro and P. Tetali. Mathematical Aspects of Mixing Times in Markov Chains. Foundations and Trends in Theoretical Computer Science 1:3. M. Sudan (Ed.). Now Publishers, Boston-Delft, 2006. | MR | Zbl

[14] R. Pemantle. Towards a theory of negative dependence, J. Math. Phys. 41 (1997) 1371-1390. | MR | Zbl

[15] L. Saloff-Coste. Lectures on finite Markov chains. In Lectures on Probability Theory and Statistics, Saint-Flour 1996 301-413. Lecture Notes in Math. 1665. Springer, Berlin, 1997. | MR | Zbl