On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted \(U\)-statistics. (English) Zbl 0890.60019

Summary: 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 \({\mathbf X}^{(t)}\), and a function \(U= U({\mathbf 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 \({\mathbf X}^{(t)}= \{X^{(t)}_i\}_{i\in{\mathcal V}}\), \(t= 0,1,\dots\), where \({\mathcal V}\) is the vertex set of an \(n\)-vertex regular graph, and \(X^{(t)}_i= +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^{(t+ 1)}_i= -X^{(t)}_j\) and \(X^{(t+ 1)}_k= X^{(t)}_k\) for all \(k\neq i\). For a stationary antivoter chain, we study the normal approximation of \(U_n= U^{(t)}_n= \sum_i X^{(t)}_i\) 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.


60F05 Central limit and other weak theorems
60K35 Interacting random processes; statistical mechanics type models; percolation theory
62E20 Asymptotic distribution theory in statistics
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: DOI


[1] Aldous, D. and Fill, J. A. (1994). Reversible Markov chains and random walks on graphs. Unpublished manuscript.
[2] Barbour, A. D., Karo ński, M. and Ruci ński, A. (1989). A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B 47 125-145. · Zbl 0689.05042
[3] Bhattachary a, R. N. and Ranga Rao, R. (1986). Normal Approximation and Asy mptotic Expansion. Krieger, Melbourne, FL.
[4] Biggs, N. (1993). Algebraic Graph Theory. Cambridge Univ. Press. · Zbl 0805.68094
[5] Brouwer, A. E., Cohen, A. M. and Neumaier, A. (1989). Distance-Regular Graphs. Springer, Berlin. · Zbl 0747.05073
[6] Diaconis, P. (1977). The distribution of leading digits and uniform distribution mod 1. Ann. Probab. 5 72-81. · Zbl 0364.10025
[7] Diaconis, P. (1989). An example of Stein’s method. Technical report, Dept. Statistics, Stanford Univ. · Zbl 0688.62005
[8] Donnelly, P. and Welsh, D. (1984). The antivoter problem: random 2-colourings of graphs. In Graph Theory and Combinatorics (B. Bollobás, ed.) 133-144. Academic Press, New York. · Zbl 0579.60097
[9] G ötze, F. (1991). On the rate of convergence in the multivariate CLT. Ann. Probab. 19 724-739. · Zbl 0729.62051
[10] Griffeath, D. (1979). Additive and Cancellative Interacting Particle Sy stems. Lecture Notes in Math. 724. Springer, Berlin. · Zbl 0412.60095
[11] Hall, P. (1984). Central limit theorem for integrated square error of multivariate nonparametric density estimators. J. Multivariate Anal. 14 1-16. · Zbl 0528.62028
[12] Hoeffding, W. (1948). A class of statistics with asy mptotically normal distribution. Ann. Math. Statist. 19 293-325. · Zbl 0032.04101
[13] Horn, R. A. and Johnson, C. A. (1985). Matrix Analy sis. Cambridge Univ. Press.
[14] Janson, S. (1984). The asy mptotic distribution of incomplete U-statistics. Z. Wahrsch. Verw. Gebiete 66 495-505. · Zbl 0523.62022
[15] Joag-Dev, K. and Proschan, F. (1983). Negative association of random variables, with applications. Ann. Statist. 11 286-295. · Zbl 0508.62041
[16] Lee, A. J. (1990). U-statistics: Theory and Practice. Dekker, New York. · Zbl 0771.62001
[17] Liggett, T. M. (1985). Interacting Particle Sy stems. Springer, New York.
[18] Matloff, N. (1977). Ergodicity conditions for a dissonant voting model. Ann. Probab. 5 371-386. · Zbl 0364.60119
[19] Newman, C. M. (1984). Asy mptotic independence and limit theorems for positively and negatively dependent random variables. In Inequalities in Statistics and Probability (Y. L. Tong, ed.) 127-140. IMS, Hay ward, CA.
[20] Nowicki, K. and Wierman, J. C. (1988). Subgraph counts in random graph using incomplete U-statistics methods. Discrete Math. 72 299-310. · Zbl 0672.05072
[21] O’Neil, K. and Redner, R. A. (1993). Asy mptotic distributions of weighted U-statistics of degree 2. Ann. Probab. 21 1159-1169. · Zbl 0774.62018
[22] Rinott, Y. and Rotar, V. (1996). A multivariate CLT for local dependence with n-1/2 log n rate, and applications to multivariate graph related statistics. J. Multivariate Anal. 56 333- 350. · Zbl 0859.60019
[23] Stein, C. (1972). A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proc. Sixth Berkeley Sy mp. Math. Statist. Probab. 2 583-602. Univ. California Press, Berkeley. · Zbl 0278.60026
[24] Stein, C. (1986). Approximate Computation of Expectations. IMS, Hay ward, CA. · Zbl 0721.60016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.