On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted U-statistics

This paper deals with rates of convergence in the CLT for certain types of dependency. The main idea is to combine a modification of a theorem of Stein, requiring a coupling construction, with a dynamic set-up provided by a Markov structure that suggests natural coupling variables. More specifically, given a stationary Markov chain X⁽ᵗ⁽, and a function U = U(X⁽ᵗ⁾), we propose a way to study the proximity of U to a normal random variable when the state space is large. We apply the general method to the study of two problems. In the first, we consider the antivoter chain X⁽ᵗ⁾ = Xᵢ⁽ᵗ⁾ i ε V, t = 0, 1, , where V is the vertex set of an n-vertex regular graph, and Xᵢ⁽ᵗ⁾ = +1 or -1. The chain evolves from time t to $t + 1$ by choosing a random vertex i, and a random neighbor of it j, and setting Xᵢ⁽ᵗ⁺¹⁾ = -Xⱼ⁽ᵗ⁾ and Xₖ⁽ᵗ⁺¹⁾ = Xₖ⁽ᵗ⁾ for all k = i. For a stationary antivoter chain, we study the normal approximation of Uₙ = Uₙ⁽ᵗ⁾ = Σᵢ Xᵢ⁽ᵗ⁾ for large n and consider some conditions on sequences of graphs such that Uₙ is asymptotically normal, a problem posed by Aldous and Fill. The same approach may also be applied in situations where a Markov chain does not appear in the original statement of a problem but is constructed as an auxiliary device. This is illustrated by considering weighted U-statistics. In particular we are able to unify and generalize some results on normal convergence for degenerate weighted U-statistics and provide rates.