Sampling the Fermi statistics and other conditional product measures
Annales de l'I.H.P. Probabilités et statistiques, Volume 47 (2011) no. 3, p. 790-812

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.

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.

DOI : https://doi.org/10.1214/10-AIHP385
Classification:  60J10,  82C44
Keywords: metropolis algorithm, Markov chain, sampling, mixing time, product measure, conservative dynamics
@article{AIHPB_2011__47_3_790_0,
     author = {Gaudilli\`ere, A. and Reygner, J.},
     title = {Sampling the Fermi statistics and other conditional product measures},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {47},
     number = {3},
     year = {2011},
     pages = {790-812},
     doi = {10.1214/10-AIHP385},
     zbl = {1227.82064},
     mrnumber = {2841075},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2011__47_3_790_0}
}
Gaudillière, A.; Reygner, J. Sampling the Fermi statistics and other conditional product measures. Annales de l'I.H.P. Probabilités et statistiques, Volume 47 (2011) no. 3, pp. 790-812. doi : 10.1214/10-AIHP385. http://www.numdam.org/item/AIHPB_2011__47_3_790_0/

[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 1845806 | Zbl 0982.46026

[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 889476 | Zbl 0561.60080

[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 2200172 | Zbl 1087.60071

[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 2073330 | Zbl 1072.82001

[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 2429910 | Zbl 1176.60081

[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 2548501 | Zbl 1181.60142

[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 2311889 | Zbl 1153.82026

[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 2683634 | Zbl 1207.65006

[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 2117953 | Zbl 1108.60084

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

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

[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 2341319 | Zbl 1193.68138

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

[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 1490046 | Zbl 0885.60061