The convex distance inequality for dependent random variables, with applications to the stochastic travelling salesman and other problems. (English) Zbl 1330.60039

Paulin, Daniel

Electron. J. Probab. 19, Paper No. 68, 34 p. (2014).

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.

Reviewer: Fraser Daly (Edinburgh)

MSC:

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

Keywords:

concentration inequalities; Stein’s method; exchangeable pairs; reversible Markov chains; stochastic travelling salesman problem; Steiner tree; sampling without replacement; Dobrushin condition; exponential random graph