The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number68
Number of pages34
JournalElectronic journal of probability
Volume19
DOIs
Publication statusPublished - Oct 2014
Externally publishedYes

Fingerprint

Dive into the research topics of 'The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems'. Together they form a unique fingerprint.

Cite this