HOROWITZ SEMINAR

PROBABILITY, ERGODIC THEORY and DYNAMICAL SYSTEMS

On Sunday June 18th in room 210, Schreiber Bldg., at 14:30

Leonid Kontorovich (Carnegie Mellon Univ.)

Concentration of measure for Markov chains.

abstract

The concentration of measure phenomenon has been actively analyzed in recent years using a variety of tools: isoperimetric inequalities, information-theoretic techniques, log-Sobolev inequalities. We take McDiarmid's method of bounded differences as a starting point and proceed to obtain a general concentration inequality for nonproduct measures. As an application, we (with Kavita Ramanan) give a bound for inhomogeneous Markov processes that is both sharper and requires weaker assumptions than the best known bounds.