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

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.