Convergence of Empirical Means with Alpha-Mixing Input Sequences, and an Application to PAC Learning

Suppose {Xi} is an alpha-mixing stochastic process assuming values in a set X, and that faX → R is bounded and measurable. It is shown in this note that the sequence of empirical means (1/m) ∑ⁱ⁼¹mf(xi) converges in probability to the true expected value of the function f(.). Moreover, explicit estimates are constructed of the rate at which the empirical mean converges to the true expected value. These estimates generalize classical inequalities of Hoeffding, Bennett and Bernstein to the case of alpha-mixing inputs. In earlier work, similar results have been established when the alpha-mixing coefficient of the stochastic process converges to zero at a geometric rate. No such assumption is made in the present note. This result is then applied to the problem of PAC (probably approximately correct) learning under a fixed distribution.