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^{(t(}$, and a function $U = U(X^{(t)})$, 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^{(t)} = {X_i^{(t)}} _{i \epsilon
\mathscr{V}}, t = 0, 1, \dots,$ where $\mathscr{V}$ is the vertex set of an
n-vertex regular graph, and $X_i^{(t)} = +1 \text{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_i^{(t+1)} = -X_j^{(t)}$ and
$X_k^{(t+1)} = X_k^{(t)}$ for all $k \not= i$. For a stationary antivoter
chain, we study the normal approximation of $U_n = U_n^{(t)} = \Sigma_i
X_i^{(t)}$ for large n and consider some conditions on sequences of
graphs such that $U_n$ 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.