A MEASURE CONCENTRATION INEQUALITY FOR CONTRACTING MARKOV-CHAINS

The concentration of measure phenomenon in product spaces means the fo llowing: if a subset A of the n'th power of a probability space X does not have too small a probability then very large probability is conce ntrated in a small neighborhood of A. The neighborhood is in many case s understood in the sense of Hamming distance, and then measure concen tration is known to occur for product probability measures, and also f or the distribution of some processes with very fast and uniform decay of memory. Recently Talagrand introduced another notion of neighborho od of sets for which he proved a similar measure concentration inequal ity which in many cases allows more efficient applications than the on e for a Hamming neighborhood. So far this inequality has only been pro ved for product distributions. The aim of this paper is to give a new proof of Talagrand's inequality, which admits an extension to contract ing Markov chains. Tile proof is based on a new asymmetric nation of d istance between probability measures, and bounding this distance by in formational divergence. As an application, we analyze the bin packing problem for Markov chains.