The Annals of Applied Probability · 2023 · 30 citations · 22 references
EngineeringMathematicsMarkov Decision ProcessesProbability TheoryStochastic ProcessesMarkov Chain Monte CarloMarkov ChainsMarkov ProcessesMonte Carlo MethodsMonte Carlo SimulationProbability InequalitiesConcentration InequalitiesLipschitz ConditionsLogarithmic Sobolev InequalitiesMixing Time AnalysisMixing Time CharacterizationReversible Markov ChainsStrong Covering Property
We establish universal modified log-Sobolev inequalities for reversible Markov chains on the boolean lattice {0,1}n, when the invariant law π satisfies a form of negative dependence known as the stochastic covering property. This condition is strictly weaker than the strong Rayleigh property, and is satisfied in particular by all determinantal measures, as well as the uniform distribution over the set of bases of any balanced matroid. In the special case where π is k-homogeneous, our results imply the celebrated concentration inequality for Lipschitz functions due to Pemantle and Peres (Combin. Probab. Comput. 23 (2014) 140–160). As another application, we deduce that the natural Monte-Carlo Markov chain used to sample from π has mixing time at most knloglog1π(x) when initialized in state x. To the best of our knowledge, this is the first work relating negative dependence and modified log-Sobolev inequalities.
22