Berry-Esseen central limit theorems for Markov chains

Let X{dollar}sb{lcub}t{rcub}{dollar} be a discrete time Markov chain on a countable state space S satisfying a certain mixing condition. Let f be a bounded R{dollar}sp{lcub}d{rcub}{dollar}-valued function on S. Consider{dollar}{dollar}N(t) = sumsbsp{lcub}i=0{rcub}{lcub}t{rcub}f(Xsb{lcub}i{rcub}).{dollar}{dollar}We compute the mean and variance of N(t) in certain cases. We give two central limit theorems for N(t) with explicit error bounds, covering the cases d = 1 and d {dollar}ge{dollar} 1.; When d = 1, the bound on the difference between the distribution function of N(t) and the standard normal distribution is of order t{dollar}sp{lcub}-1/2{rcub}{dollar} with a constant depending on the size of f, the initial distribution of the chain, the rate of convergence of the chain, and the variance of N(t). An example, nearest-neighbor random walk on the discrete circle, shows this bound is sharp in some cases. When d {dollar}ge{dollar} 1, the bound is of order (log t){dollar}sp{lcub}d/2{rcub}{dollar}t{dollar}sp{lcub}-1/2{rcub}{dollar}.; The method of proof for the error bounds is Fourier analysis. The characteristic function of N(t) can be expressed in terms of a perturbation of the chain's transition kernel. Analysis of an eigenvalue of the perturbation gives sufficient control over the characteristic function of N(t) to bound the difference between the characteristic function of N(t) and the characteristic function of the standard normal distribution. A smoothing lemma translates this bound into a bound on the difference of the distribution functions.