The concentration of measure phenomenon was first discovered in the 1930's by Paul Lévy and has been investigated since then, with increasing intensity in recent decades. The probability-theoretic results have been gradually percolating throughout the mathematical community, finding applications in Banach space geometry, analysis of algorithms, statistics and machine learning.

There are several approaches to proving concentration of measure results; we shall offer a brief survey of these. The principal contribution of this thesis is a functional norm inequality, which immediately implies a concentration inequality for nonproduct measures. The inequality is proved by elementary means, yet enables one, with minimal effort, to recover and generalize the best current results for Markov chains, as well as to obtain new results for hidden Markov chains and Markov trees.

As an application of our inequalities, we give a strong law of large numbers for a broad class of non-independent processes. In particular, this allows one to analyze the convergence of inhomogeneous Markov Chain Monte Carlo algorithms. We also give some partial results on extending the Rademacher-type generalization bounds to processes with arbitrary dependence.

We end the thesis with some conjectures and open problems.

89 pages

This page maintained by reports@cs.cmu.edu