Applications of Stein's method for concentration inequalities

By Sourav Chatterjee, Partha S. Dey. 2009

88 citations recorded by the source corpus.

Stein’s method for concentration inequalities was introduced to prove concentration of measure in problems involving complex dependencies such as random permutations and Gibbs measures. In this paper, we provide some extensions of the theory and three applications: (1) We obtain a concentration inequality for the magnetization in the Curie–Weiss model at critical temperature (where it obeys a nonstandard normalization and super-Gaussian concentration). (2) We derive exact large deviation asymptotics for the number of triangles in the Erdős–Renyi random graph G(n, p) when p ≥ 0.31. Similar results are derived also for general subgraph counts. (3) We obtain some interesting concentration inequalities for the Ising model on lattices that hold at all temperatures.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/35f4206943f3f7e3294e213dea964006604a1d4e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Estimating and understanding exponential random graph models (2011, unknown): “For exponential graph models, Chatterjee and Dey [13] prove that they work for some restricted ranges of {βi}: values where the graphs are shown to be essentially Erdős–Rényi graphs (see Theorem 4.2 below and [6]).”
Nonlinear large deviations (2014, methodology): “−f(x,y))log 1 −f(x,y) 1 −p dxdy, and T(f) = ZZZ [0,1]3 f(x,y)f(y,z)f(z,x)dxdydz. Incidentally, the variational problem (1.2) has not yet yielded explicit solutions except in special ranges of δand p[14, 16, 33, 32]. The above result was proved using Szemer´edi’s regularity lemma [35] from graph the”
Size biased couplings and the spectral gap for random regular graphs (2015, methodology): “Using Stein’s classical exchangeable pair, [16] and [17] show concentration for Hoeffding’s combinatorial statistic, in the Curie–Weiss and Ising models, and for the number of triangles in the Erdős–Rényi random graph.”
A short survey of Stein's method (2014, background): “A more complex set of examples was worked out in a later paper with Dey [25] in 2010.”
An introduction to large deviations for random graphs (2016, background): “For a few mathematical results preceding [19], see [4, 18].”
The large deviation principle for the Erd\H{o}s-R\'enyi random graph (2010, methodology): “Besides [9] and [4], we know of no other papers that attack the exact evaluation of (13) (or equivalently, (14)).”
Upper tails and independence polynomials in random graphs (2015, background): “[10, 11, 25] for more on the many questions still open in that regime).”
Fundamentals of Stein's method (2011, background): “3) may be substituted to yield different bounds; see [19].”
From Stein identities to moderate deviations (2009, unknown): “It is known that for N(0,1), Lf (w) = f ′(w) − wf (w) [see Stein (1972)] and for Poisson(λ), Lf (w) = λf (w+1)−wf (w); see Chen (1975). However, L is not unique.”