Concentration inequalities for polynomials of contracting ising models

Reza Gheissari; Eyal Lubetzky; Yuval Peres

doi:10.1214/18-ECP173

Concentration inequalities for polynomials of contracting ising models

Reza Gheissari, Eyal Lubetzky, Yuval Peres

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We study the concentration of a degree-d polynomial of the N spins of a general Ising model, in the regime where single-site Glauber dynamics is contracting. For d = 1, Gaussian concentration was shown by Marton (1996) and Samson (2000) as a special case of concentration for convex Lipschitz functions, and extended to a variety of related settings by e.g., Chazottes et al. (2007) and Kontorovich and Ramanan (2008). For d = 2, exponential concentration was shown by Marton (2003) on lattices. We treat a general fixed degree d with O(1) coefficients, and show that the polynomial has variance O(N^d) and, after rescaling it by N^−d/2, its tail probabilities decay as exp(−c r^2/d) for deviations of r ≥ C log N.

Original language	English (US)
Article number	76
Journal	Electronic Communications in Probability
Volume	23
DOIs	https://doi.org/10.1214/18-ECP173
State	Published - 2018

Keywords

Concentration of measure
Contraction
Independence testing
Ising model

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty

Access to Document

10.1214/18-ECP173

Cite this

@article{7cf93502bd954f85a46ef1f044ce852a,

title = "Concentration inequalities for polynomials of contracting ising models",

abstract = "We study the concentration of a degree-d polynomial of the N spins of a general Ising model, in the regime where single-site Glauber dynamics is contracting. For d = 1, Gaussian concentration was shown by Marton (1996) and Samson (2000) as a special case of concentration for convex Lipschitz functions, and extended to a variety of related settings by e.g., Chazottes et al. (2007) and Kontorovich and Ramanan (2008). For d = 2, exponential concentration was shown by Marton (2003) on lattices. We treat a general fixed degree d with O(1) coefficients, and show that the polynomial has variance O(Nd) and, after rescaling it by N−d/2, its tail probabilities decay as exp(−c r2/d) for deviations of r ≥ C log N.",

keywords = "Concentration of measure, Contraction, Independence testing, Ising model",

author = "Reza Gheissari and Eyal Lubetzky and Yuval Peres",

note = "Funding Information: The authors thank the anonymous referee for helpful suggestions. R.G. and E.L. thank Microsoft Research for its hospitality. E.L. was supported in part by NSF grant DMS-1513403. Publisher Copyright: {\textcopyright} 2018, University of Washington. All rights reserved.",

year = "2018",

doi = "10.1214/18-ECP173",

language = "English (US)",

volume = "23",

journal = "Electronic Communications in Probability",

issn = "1083-589X",

publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Concentration inequalities for polynomials of contracting ising models

AU - Gheissari, Reza

AU - Lubetzky, Eyal

AU - Peres, Yuval

N1 - Funding Information: The authors thank the anonymous referee for helpful suggestions. R.G. and E.L. thank Microsoft Research for its hospitality. E.L. was supported in part by NSF grant DMS-1513403. Publisher Copyright: © 2018, University of Washington. All rights reserved.

PY - 2018

Y1 - 2018

N2 - We study the concentration of a degree-d polynomial of the N spins of a general Ising model, in the regime where single-site Glauber dynamics is contracting. For d = 1, Gaussian concentration was shown by Marton (1996) and Samson (2000) as a special case of concentration for convex Lipschitz functions, and extended to a variety of related settings by e.g., Chazottes et al. (2007) and Kontorovich and Ramanan (2008). For d = 2, exponential concentration was shown by Marton (2003) on lattices. We treat a general fixed degree d with O(1) coefficients, and show that the polynomial has variance O(Nd) and, after rescaling it by N−d/2, its tail probabilities decay as exp(−c r2/d) for deviations of r ≥ C log N.

AB - We study the concentration of a degree-d polynomial of the N spins of a general Ising model, in the regime where single-site Glauber dynamics is contracting. For d = 1, Gaussian concentration was shown by Marton (1996) and Samson (2000) as a special case of concentration for convex Lipschitz functions, and extended to a variety of related settings by e.g., Chazottes et al. (2007) and Kontorovich and Ramanan (2008). For d = 2, exponential concentration was shown by Marton (2003) on lattices. We treat a general fixed degree d with O(1) coefficients, and show that the polynomial has variance O(Nd) and, after rescaling it by N−d/2, its tail probabilities decay as exp(−c r2/d) for deviations of r ≥ C log N.

KW - Concentration of measure

KW - Contraction

KW - Independence testing

KW - Ising model

UR - http://www.scopus.com/inward/record.url?scp=85055744897&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85055744897&partnerID=8YFLogxK

U2 - 10.1214/18-ECP173

DO - 10.1214/18-ECP173

M3 - Article

AN - SCOPUS:85055744897

SN - 1083-589X

VL - 23

JO - Electronic Communications in Probability

JF - Electronic Communications in Probability

M1 - 76

ER -

Concentration inequalities for polynomials of contracting ising models

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this