Berry-Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing.

*(English)*Zbl 1087.60021Author develops Berry-Esseen type bounds for normal approximation, based on zero-couplings and size-bias couplings. Stein’s method, which characterizes equations to obtain bounds on the error when approximating distrubutions by a given target, is used to obtain that bound. The results are applied to bound the proximity to the normal in combinatorial central limit theorems in which the random permutation has either a uniform distribution or one that is constant over permutations with the same cycle type, with no fixed points; to counting the number of occurrences of fixed, relatively ordered subsequences, such as rising sequences, in a random permutation; and to counting the number of occurrences of patterns, local extremes, and subgraphs in finite graphs. From a characterizing equation a difference or differential equation can be set up to bound the difference between the exepctation of a test function \(h\) when evaluated on a given variable \(Y\) and then on the variable \(X\) having the target distribution. For the normal, with \(X\) having the same mean \(\mu\) and variance \(\sigma^2\) as \(Y\), the characterizing equation leads to the differential equation

\[ h((y-\mu)/\sigma) - Nh = \sigma^2 f'(y) - (y-\mu)f(y), \]

where \(Nh = Eh(Z)\) with \(Z\sim N(0,1)\), the standard normal mean of the test function \(h.\) Tow concepts of couplings of a given \(Y\) are introduced to achieve normal bounds. With \(W=(Y-\mu)/\sigma\), many authors have been successful in obtaining bounds on the distance

\[ \delta = \sup_{h\in H} | Eh(W)-Nh | \]

to the normal, over classes of nonsmooth functions \(H\), using Stein’s method. The author takes the smoothing inequality approach. In Theorem 1.1, for the case of the first type of couplings, the bound on \(\delta\) is obtained. In Section 2, the result in Theorem 1.1 is applied to random variables of the form \(Y=\sum^{n}_{i=1} a_{i, \pi(i)},\) depending on a fixed array of real numbers \(\{a_{ij}\}^{n}_{i,j=1}\) and a random permutation \(\pi\in S_n\), the symmetric group of order \(n\). In Section 2.1 the author considers \(\pi\) to have the uniform distribution on \(S_n\) and, in Section 2.2, he considers distributions constant with respect to cycle type, with no fixed points. For a case of the second size-bias coupling, the author presents Theorem 1.2, which gives a bound on \(\delta\) that depends on the size of the absolute value of difference between couplings. In Section 3, the author drives corollaries to Theorem 1.2 to obtain Berry-Esseen bounds for the number of occurrences of fixed, relatively ordered subsequences, such as rising sequences, in a radom permutation, and of color patterns, local maxima, and subgraphs in finite graphs. Several examples are given in two sections.

\[ h((y-\mu)/\sigma) - Nh = \sigma^2 f'(y) - (y-\mu)f(y), \]

where \(Nh = Eh(Z)\) with \(Z\sim N(0,1)\), the standard normal mean of the test function \(h.\) Tow concepts of couplings of a given \(Y\) are introduced to achieve normal bounds. With \(W=(Y-\mu)/\sigma\), many authors have been successful in obtaining bounds on the distance

\[ \delta = \sup_{h\in H} | Eh(W)-Nh | \]

to the normal, over classes of nonsmooth functions \(H\), using Stein’s method. The author takes the smoothing inequality approach. In Theorem 1.1, for the case of the first type of couplings, the bound on \(\delta\) is obtained. In Section 2, the result in Theorem 1.1 is applied to random variables of the form \(Y=\sum^{n}_{i=1} a_{i, \pi(i)},\) depending on a fixed array of real numbers \(\{a_{ij}\}^{n}_{i,j=1}\) and a random permutation \(\pi\in S_n\), the symmetric group of order \(n\). In Section 2.1 the author considers \(\pi\) to have the uniform distribution on \(S_n\) and, in Section 2.2, he considers distributions constant with respect to cycle type, with no fixed points. For a case of the second size-bias coupling, the author presents Theorem 1.2, which gives a bound on \(\delta\) that depends on the size of the absolute value of difference between couplings. In Section 3, the author drives corollaries to Theorem 1.2 to obtain Berry-Esseen bounds for the number of occurrences of fixed, relatively ordered subsequences, such as rising sequences, in a radom permutation, and of color patterns, local maxima, and subgraphs in finite graphs. Several examples are given in two sections.

Reviewer: Tae Il. Jeon (Taejon)

##### References:

[1] | Baldi, P. and Rinott, Y. (1989). Asymptotic normality of some graph-related statistics. J. Appl. Prob. 26 , 171–175. · Zbl 0671.60018 |

[2] | Baldi, P., Rinott, Y. and Stein, C. (1989). A normal approximation for the number of local maxima of a random function on a graph. In Probability, Statistics, and Mathematics , Academic Press, Boston, MA, pp. 59–81. · Zbl 0704.62018 |

[3] | Barbour, A. D., Janson, S., Karoński, M. and Ruciński, A. (1990). Small cliques in random graphs. Random Structures Algorithms 1 , 403–434. · Zbl 0733.05050 |

[4] | Bayer, D. and Diaconis, P. (1992). Trailing the dovetail shuffle to its lair. Ann. Appl. Prob. 2 , 294–313. JSTOR: · Zbl 0757.60003 |

[5] | Bhattacharya, R. N. and Ranga Rao, R. (1986). Normal Approximation and Asymptotic Expansions . Krieger, Melbourne, FL. · Zbl 0657.41001 |

[6] | Biggs, N. (1993). Algebraic Graph Theory . Cambridge University Press. · Zbl 0805.68094 |

[7] | Bolthausen, E. (1984). An estimate of the remainder in a combinatorial central limit theorem. Z. Wahrscheinlichkeitsth . 66 , 379–386. · Zbl 0563.60026 |

[8] | Bolthausen, E. and Götze, F. (1993). The rate of convergence for multivariate sampling statistics. Ann. Statist. 21 , 1692–1710. JSTOR: · Zbl 0798.62023 |

[9] | Brouwer, A. E., Cohen, A. M. and Neumaier, A. (1989). Distance-Regular Graphs . Springer, Berlin. · Zbl 0747.05073 |

[10] | Chen, L. H. Y. and Shao, Q.-M. (2004). Normal approximation under local dependence. Ann. Prob. 32 , 1985–2028. · Zbl 1048.60020 |

[11] | Darling, R. W. R. and Waterman, M. S. (1986). Extreme value distribution for the largest cube in a random lattice. SIAM J. Appl. Math. 46 , 118–132. · Zbl 0658.60063 |

[12] | Darling, R. W. R. and Waterman, M. S. (1985). Matching rectangles in \(d\) dimensions: algorithms and laws of large numbers. Adv. Math. 55 , 1–12. · Zbl 0586.60030 |

[13] | Glaz, J., Naus, J. and Wallenstein, S. (2001). Scan Statistics. Springer, New York. · Zbl 0983.62075 |

[14] | Goldstein, L. (2004). Normal approximation for hierarchical sequences. Ann. Appl. Prob. 14 , 1950–1969. · Zbl 1064.60056 |

[15] | Goldstein, L. and Reinert, G. (1997). Stein’s method and the zero bias transformation with application to simple random sampling. Ann. Appl. Prob. 7 , 935–952. · Zbl 0903.60019 |

[16] | Goldstein, L. and Reinert, G. (2005). Distributional transformations, orthogonal polynomials, and Stein characterizations. J. Theoret. Prob. 18 , 185–208. · Zbl 1072.62002 |

[17] | Goldstein, L. and Rinott, Y. (1996). On multivariate normal approximations by Stein’s method and size bias couplings. J. Appl. Prob. 33 , 1–17. · Zbl 0845.60023 |

[18] | Goldstein, L. and Rinott, Y. (2004). A permutation test for matching and its asymptotic distribution. Metron 61 , 375–388. |

[19] | Götze, F. (1991). On the rate of convergence in the multivariate CLT. Ann. Prob. 19 , 724–739. JSTOR: · Zbl 0729.62051 |

[20] | Ho, S. T. and Chen, L. H. Y. (1978). An \(L_p\) bound for the remainder in a combinatorial central limit theorem. Ann. Prob. 6 , 231–249. · Zbl 0375.60028 |

[21] | Huang, H. (2002). Error bounds on multivariate normal approximations for word count statistics. Adv. Appl. Prob. 34 , 559–586. · Zbl 1021.62008 |

[22] | Kolchin, V. F. and Chistyakov, V. P. (1973). On a combinatorial limit theorem. Theory Prob. Appl. 18 , 728–739. · Zbl 0314.60011 |

[23] | Naus, J. I. (1982). Approximations for distributions of scan statistics. J. Amer. Statist. Assoc. 77 , 177–183. · Zbl 0482.62010 |

[24] | 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 |

[25] | Rinott, Y. and Rotar, V. (1997). On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted \(U\)-statistics. Ann. Appl. Prob. 7 , 1080–1105. · Zbl 0890.60019 |

[26] | Stein, C. (1972). A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proc. Sixth Berkeley Symp. Math. Statist. Prob. (Berkeley, CA, 1970/1971), Vol. 2, University of California Press, pp. 583–602. · Zbl 0278.60026 |

[27] | Stein, C. (1972). Estimation of the mean of a multivariate normal distribution. Ann. Prob. 9 , 1135–1151. JSTOR: · Zbl 0476.62035 |

[28] | Stein, C. (1986). Approximate Computation of Expectations (Inst. Math. Statist. Lecture Notes Monogr. Ser. 7 ). IMS, Hayward, CA. · Zbl 0721.60016 |

[29] | Von Bahr, B. (1976). Remainder term estimate in a combinatorial limit theorem. Z. Wahrscheinlichkeitsth . 35 , 131–139. · Zbl 0366.60028 |

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.