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

Abstract

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).

41 pages. Published in the Electronic Journal of Probability by the International Statistical Institute/Bernoulli Society, see http://ejp.ejpecp.org/article/view/3261

References in corpus (7)

• Transportation cost-information inequalities and applications to random dynamical systems and diffusions
• Estimating and understanding exponential random graph models
• Moment inequalities for functions of independent random variables
• Concentration inequalities for sampling without replacement
• Poincaré and transportation inequalities for Gibbs measures under the Dobrushin uniqueness condition
• Convergence rate and concentration inequalities for Gibbs sampling in high dimension
• Concentration inequalities via zero bias couplings

Cited by in corpus (4)

• Modified log-Sobolev inequalities and two-level concentration
• Masked Toeplitz covariance estimation
• Risk-Aware Submodular Optimization for Multi-objective Travelling Salesperson Problem
• A note on the Hanson-Wright inequality for random vectors with dependencies