Combinatorics, Probability and Computing

Table of Contents - 2001 - Volume 10, Issue 01  


Concentration of Measure for Products of Markov Kernels and Graph Products via Functional Inequalities

C. HOUDRÉ a1 1 and P. TETALI a2 2
a1 Southeast Applied Analysis Center, School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA (e-mail: houdre@math.gatech.edu)
a2 School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA (e-mail: tetali@math.gatech.edu)

Abstract

We present versions of concentration inequalities for products of Markov kernels and graph products. We also present discussions of a variety of consequences such as sharp upper bounds, in terms of the diameter of the state space, on the spectral gap.

(Received January 20 2000)
(Revised May 30 2000)


Footnotes

1 Research supported in part by an NSF Postdoctoral Fellowship and by NSF grant DMS-9803239.

2 Research supported in part by NSF grant CCR-9800352.