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

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