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

DOI10.1214/EJP.V19-3261MaRDI QIDQ743493zbMATH OpenFDO

Authors Daniel Paulin

Publication date 24 September 2014

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.2014

zbMATH Keywords

concentration inequalitiesDobrushin conditionexchangeable pairsexponential random graphreversible Markov chainssampling without replacementStein's methodSteiner treestochastic travelling salesman problem

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

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

Review text

Let \(X=(X_1,\dots,X_n)\) be a vector of random variables taking values in a Polish space \(\Lambda=\Lambda_1\times\dots\times\Lambda_n\). Suppose that these random variables are weakly dependent, in the sense that they satisfy the Dobrushin condition. The author begins by proving concentration inequalities for \(g(X)\) for functions \(g:\Lambda\mapsto\mathbb{R}^+\) which satisfy a self-boundedness condition. For such weakly dependent random variables \(X\), a version of Talagrand's convex distance inequality is also established. The proofs of these results use Stein's method of exchangeable pairs. A detailed discussion is given for applications to the stochastic travelling salesman problem, Steiner trees, the Curie-Weiss model, and exponential random graph models.

Recommendations

• Concentration inequalities for functions of independent variables
• A sharp deviation inequality for the stochastic traveling salesman problem
• Measure concentration and strong mixing
• scientific article; zbMATH DE number 747044
• Measure concentration for Euclidean distance in the case of dependent random variables.

Cited in

(6)

• A sharp deviation inequality for the stochastic traveling salesman problem
• Measure concentration for Euclidean distance in the case of dependent random variables.
• Concentration inequalities on the multislice and for sampling without replacement
• Kantorovich duality for general transport costs and applications
• Modified log-Sobolev inequalities and two-level concentration
• Concentration inequalities for some negatively dependent binary random variables

This page was built for publication: The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q743493)