Abstract / Description of output
We prove concentration inequalities for general functions of weakly dependent random variables satisfying the Dobrushin condition. In particular, we show Talagrand's convex distance inequality for this type of dependence. We apply our bounds to a version of the stochastic salesman problem, the Steiner tree problem, the total magnetisation of the Curie-Weiss model with external field, and exponential random graph models. Our proof uses the exchangeable pair method for proving concentration inequalities introduced by Chatterjee (2005). Another key ingredient of the proof is a subclass of (a,b)-self-bounding functions, introduced by Boucheron, Lugosi and Massart (2009).
Original language | English |
---|---|
Article number | 68 |
Number of pages | 34 |
Journal | Electronic journal of probability |
Volume | 19 |
DOIs | |
Publication status | Published - Oct 2014 |
Externally published | Yes |