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

Daniel Paulin (National University of Singapore)

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

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-34

Publication Date: August 11, 2014

DOI: 10.1214/EJP.v19-3261

References

  • Applegate, David L.; Bixby, Robert E.; Chvátal, Vašek; Cook, William J. The traveling salesman problem. A computational study. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, 2006. xii+593 pp. ISBN: 978-0-691-12993-8; 0-691-12993-2 MR2286675
  • Remi Bardenet and Odalric-Ambrym Maillard, Concentration inequalities for sampling without replacement, arXiv preprint arXiv:1309.4029 (2013).
  • Boucheron, Stephane; Bousquet, Olivier; Lugosi, Gabor; Massart, Pascal. Moment inequalities for functions of independent random variables. Ann. Probab. 33 (2005), no. 2, 514--560. MR2123200
  • Boucheron, Stephane; Lugosi, Gabor; Massart, Pascal. On concentration of self-bounding functions. Electron. J. Probab. 14 (2009), no. 64, 1884--1899. MR2540852
  • Boucheron, Stephane; Lugosi, Gabor; Massart, Pascal. Concentration inequalities using the entropy method. Ann. Probab. 31 (2003), no. 3, 1583--1614. MR1989444
  • Boucheron, Stephane; Lugosi, Gabor; Massart, Pascal. Concentration inequalities. A nonasymptotic theory of independence. With a foreword by Michel Ledoux. Oxford University Press, Oxford, 2013. x+481 pp. ISBN: 978-0-19-953525-5 MR3185193
  • Chatterjee, Sourav. Concentration inequalities with exchangeable pairs. Thesis (Ph.D.)–Stanford University. ProQuest LLC, Ann Arbor, MI, 2005. 105 pp. ISBN: 978-0542-08643-4 MR2707160
  • Chatterjee, Sourav. Stein's method for concentration inequalities. Probab. Theory Related Fields 138 (2007), no. 1-2, 305--321. MR2288072
  • Chatterjee, Sourav; Diaconis, Persi. Estimating and understanding exponential random graph models. Ann. Statist. 41 (2013), no. 5, 2428--2461. MR3127871
  • Chazottes, J.-R.; Collet, P.; Kulske, C.; Redig, F. Concentration inequalities for random fields via coupling. Probab. Theory Related Fields 137 (2007), no. 1-2, 201--225. MR2278456
  • Djellout, H.; Guillin, A.; Wu, L. Transportation cost-information inequalities and applications to random dynamical systems and diffusions. Ann. Probab. 32 (2004), no. 3B, 2702--2732. MR2078555
  • Dubhashi, Devdatt P.; Panconesi, Alessandro. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, Cambridge, 2009. xvi+196 pp. ISBN: 978-0-521-88427-3 MR2547432
  • Faden, Arnold M. The existence of regular conditional probabilities: necessary and sufficient conditions. Ann. Probab. 13 (1985), no. 1, 288--298. MR0770643
  • Ghosh, Subhankar; Goldstein, Larry. Concentration of measures via size-biased couplings. Probab. Theory Related Fields 149 (2011), no. 1-2, 271--278. MR2773032
  • Goldstein, Larry; Işlak, Ümit. Concentration inequalities via zero bias couplings. Statist. Probab. Lett. 86 (2014), 17--23. MR3162712
  • Grimmett, Geoffrey R.; Stirzaker, David R. Probability and random processes. Third edition. Oxford University Press, New York, 2001. xii+596 pp. ISBN: 0-19-857223-9 MR2059709
  • Hwang, Frank K.; Richards, Dana S.; Winter, Pawel. The Steiner tree problem. Annals of Discrete Mathematics, 53. North-Holland Publishing Co., Amsterdam, 1992. xii+339 pp. ISBN: 0-444-89098-X MR1192785
  • Komiya, Hidetoshi. Elementary proof for Sion's minimax theorem. Kodai Math. J. 11 (1988), no. 1, 5--7. MR0930413
  • Kulske, Christof. Concentration inequalities for functions of Gibbs fields with application to diffraction and random Gibbs measures. Comm. Math. Phys. 239 (2003), no. 1-2, 29--51. MR1997114
  • Ledoux, Michel. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. x+181 pp. ISBN: 0-8218-2864-9 MR1849347
  • Marton, K. A measure concentration inequality for contracting Markov chains. Geom. Funct. Anal. 6 (1996), no. 3, 556--571. MR1392329
  • Marton, K. Measure concentration and strong mixing. Studia Sci. Math. Hungar. 40 (2003), no. 1-2, 95--113. MR2002993
  • Massart, Pascal. About the constants in Talagrand's concentration inequalities for empirical processes. Ann. Probab. 28 (2000), no. 2, 863--884. MR1782276
  • Ollivier, Yann. A survey of Ricci curvature for metric spaces and Markov chains. Probabilistic approach to geometry, 343--381, Adv. Stud. Pure Math., 57, Math. Soc. Japan, Tokyo, 2010. MR2648269
  • D. Paulin, Concentration inequalities for Markov chains by Marton couplings and spectral methods, arXiv preprint (2014).
  • Samson, Paul-Marie. Concentration of measure inequalities for Markov chains and $\Phi$-mixing processes. Ann. Probab. 28 (2000), no. 1, 416--461. MR1756011
  • Sion, Maurice. On general minimax theorems. Pacific J. Math. 8 1958 171--176. MR0097026
  • Steele, J. Michael. Probability theory and combinatorial optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, 69. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. viii+159 pp. ISBN: 0-89871-380-3 MR1422018
  • Talagrand, Michel. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Etudes Sci. Publ. Math. No. 81 (1995), 73--205. MR1361756
  • Neng-Yi Wang, Concentration inequalities for Gibbs sampling under the d_L^2 metric, Preprint (2014).
  • Neng-Yi Wang and Liming Wu, Convergence rate and concentration inequalities for Gibbs algorithm, To appear in Bernoulli (2014).
  • Wu, Liming. Poincare and transportation inequalities for Gibbs measures under the Dobrushin uniqueness condition. Ann. Probab. 34 (2006), no. 5, 1960--1989. MR2271488
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.