We observe that the technique of Markov contraction can be used to establish measure concentration for a broad class of non-contracting chains. In particular, geometric ergodicity provides a simple and versatile framework. This leads to a short, elementary proof of a general concentration inequality for Markov and hidden Markov chains (HMM), which supercedes some of the known results and easily extends to other processes such as Markov trees. As applications, we give a Dvoretzky-Kiefer-Wolfowitz-type inequality and a uniform Chernoff bound. All of our bounds are dimension-free and hold for countably infinite state spaces.
In parallel to the work on concentration of measure results for Markov chains @cite_10 @cite_1 @cite_34 @cite_7 @cite_2 @cite_3 , grew a body of independent results on Chernoff-type bounds for these processes. The papers @cite_21 @cite_25 @cite_29 @cite_15 @cite_4 played a founding role, and various extensions and refinements followed @cite_11 @cite_16 . In a remarkable recent development @cite_8 , optimal Chernoff-Hoeffding bounds are obtained based on the mixing time at a constant threshold. Concentration of Lipschitz functions of mixing sequences, with applications to the Kolmogorov-Smirnov statistic, were considered in @cite_32 . The paper @cite_14 examines the concentration of empirical distributions for non-independent sequences satisfying Poincar 'e or log-Sobolev inequalities.
@cite_14 @cite_4 @cite_7 @cite_8 @cite_29 @cite_21 @cite_1 @cite_32 @cite_3 @cite_16 @cite_2 @cite_15 @cite_34 @cite_10 @cite_25 @cite_11
2165651967 1985380836 2009754940 2101363765 2139964991 1980322272 2950313068 1972615020 2124036135 1998123258 2001351653 2028204099 2133755908 2027143166 2004255137
The concentration of empirical measures is studied for dependent data, whose joint distribution satisfies Poincar ' e -type or logarithmic Sobolev inequalities. The general concentration results are then applied to spectral empirical distribution functions associated with high-dimensional random matrices. This paper develops bounds on the distribution function of the empirical mean for irreducible finite-state Markov chains. One approach, explored by D. Gillman, reduces this problem to bounding the largest eigenvalue of a perturbation of the transition matrix for the Markov chain. By using estimates on eigenvalues given in Kato's book ''Perturbation Theory for Linear Operators'', we simplify the proof of D. Gillman and extend it to non-reversible finite-state Markov chains and continuous time. We also set out another method, directly applicable to some general ergodic Markov kernels having a spectral gap. The martingale method is used to establish concentration inequalities for a class of dependent random sequences on a countable state space, with the constants in the inequalities expressed in terms of certain mixing coecien ts. Along the way, bounds are obtained on mar- tingale dierences associated with the random sequences, which may be of independent interest. As applications of the main result, concentra- tion inequalities are also derived for inhomogeneous Markov chains and hidden Markov chains, and an extremal property associated with their martingale dierence bounds is established. This work complements and generalizes certain concentration inequalities obtained by Marton and Samson, while also providing a dieren t proof of some known results. We prove the first Chernoff-Hoeffding bounds for general nonreversible finite-state Markov chains based on the standard L_1 (variation distance) mixing-time of the chain. Specifically, consider an ergodic Markov chain M and a weight function f: [n] -> [0,1] on the state space [n] of M with mean mu = E_ v = delta mu t ], is at most exp(-Omega(delta^2 mu t T)) for 0 1. In fact, the bounds hold even if the weight functions f_i's for i in [t] are distinct, provided that all of them have the same mean mu. We also obtain a simplified proof for the Chernoff-Hoeffding bounds based on the spectral expansion lambda of M, which is the square root of the second largest eigenvalue (in absolute value) of M tilde M , where tilde M is the time-reversal Markov chain of M. We show that the probability Pr [ |X - mu t| >= delta mu t ] is at most exp(-Omega(delta^2 (1-lambda) mu t)) for 0 1. Both of our results extend to continuous-time Markov chains, and to the case where the walk starts from an arbitrary distribution x, at a price of a multiplicative factor depending on the distribution x in the concentration bounds. We consider a finite random walk on a weighted graph G; we show that the fraction of time spent in a set of vertices A converges to the stationary probability @math with error probability exponentially small in the length of the random walk and the square of the size of the deviation from @math . The exponential bound is in terms of the expansion of G and improves previous results of [D. Aldous, Probab. Engrg. Inform. Sci., 1 (1987), pp. 33--46], [L. Lovasz and M. Simonovits, Random Structures Algorithms , 4 (1993), pp. 359--412], [M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic simulation of logspace, in Proc. 19th ACM Symp. on Theory of Computing, 1987]. We show that taking the sample average from one trajectory gives a more efficient estimate of @math than the standard method of generating independent sample points from several trajectories. Using this more efficient sampling method, we improve the algorithms of Jerrum and Sinclair for approximating the number of perfect matchings in a dense graph and for approximating the partition function of a ferromagnetic Ising system, and we give an efficient algorithm to estimate the entropy of a random walk on an unweighted graph. Using the renewal approach we prove exponential inequalities for additive functionals and empirical processes of ergodic Markov chains, thus obtaining counterparts of inequalities for sums of independent random variables. The inequalities do not require functions of the chain to be bounded and moreover all the involved constants are given by explicit formulas whenever the usual drift condition holds, which may be of interest in practical applications e.g. to MCMC algorithms. We prove concentration inequalities for some classes of Markov chains and (F-mixing processes, with constants independent of the size of the sample, that extend the inequalities for product measures of Talagrand. The method is based on information inequalities put forward by Marton in case of contracting Markov chains. Using a simple duality argument on entropy, our results also include the family of logarithmic Sobolev inequalities for convex functions. Applications to bounds on supremum of dependent empirical processes complete this work. We prove tail estimates for variables of the form ∑if(Xi), where (Xi)i is a sequence of states drawn from a reversible Markov chain, or, equivalently, from a random walk on an undirected graph. The estimates are in terms of the range of the function f, its variance, and the spectrum of the graph. The purpose of our estimates is to determine the number of chain walk samples which are required for approximating the expectation of a distribution on vertices of a graph, especially an expander. The estimates must therefore provide information for fixed number of samples (as in Gillman's [4]) rather than just asymptotic information. Our proofs are more elementary than other proofs in the literature, and our results are sharper. We obtain Bernstein-and Bennett-type inequalities, as well as an inequality for sub-Gaussian variables. There is a simple inequality by Pinsker between variational distance and informational divergence of probability measures defined on arbitrary probability spaces. We shall consider probability measures on sequences taken from countable alphabets, and derive, from Pinsker's inequality, bounds on the d-distance by informational divergence. Such bounds can be used to prove the concentration of measure phenomenon for some nonproduct distributions. We obtain moment and Gaussian bounds for general coordinate-wise Lipschitz functions evaluated along the sample path of a Markov chain. We treat Markov chains on general (possibly unbounded) state spaces via a coupling method. If the first moment of the coupling time exists, then we obtain a variance inequality. If a moment of order @math @math of the coupling time exists, then depending on the behavior of the stationary distribution, we obtain higher moment bounds. This immediately implies polynomial concentration inequalities. In the case that a moment of order @math is finite, uniformly in the starting point of the coupling, we obtain a Gaussian bound. We illustrate the general results with house of cards processes, in which both uniform and non-uniform behavior of moments of the coupling time can occur. We present a tail inequality for suprema of empirical processes generated by variables with finite @math norms and apply it to some geometrically ergodic Markov chains to derive similar estimates for empirical processes of such chains, generated by bounded functions. We also obtain a bounded difference inequality for symmetric statistics of such Markov chains. Bounds are given for an irreducible Markov chain on the probability that the time average of a functional on the state space exceeds its stationary expectation, without assuming reversibility. The bounds are in terms of the singular values of the discrete generator. We build optimal exponential bounds for the probabilities of large deviations of sums k=1 ^nf(X_k) where (X_k) is a finite reversible Markov chain and f is an arbitrary bounded function. These bounds depend only on the stationary mean E_ f, the end-points of the support of f, the sample size n and the second largest eigenvalue of the transition matrix.