zbMATH — the first resource for mathematics

The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems. (English) Zbl 1330.60039
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.

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