  Following the seminal approach by Talagrand, the concept of Rademacher
complexity for independent sequences of random variables is extended to Markov
chains. The proposed notion of "block Rademacher complexity" (of a class of
functions) follows from renewal theory and allows to control the expected
values of suprema (over the class of functions) of empirical processes based on
Harris Markov chains as well as the excess probability. For classes of
Vapnik-Chervonenkis type, bounds on the "block Rademacher complexity" are
established. These bounds depend essentially on the sample size and the
probability tails of the regeneration times. The proposed approach is employed
to obtain convergence rates for the kernel density estimator of the stationary
measure and to derive concentration inequalities for the Metropolis-Hasting
algorithm.
