# zbMATH — the first resource for mathematics

Berry-Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing. (English) Zbl 1087.60021
Author 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.

##### MSC:
 60F05 Central limit and other weak theorems 60C05 Combinatorial probability
##### Keywords:
Smoothing inequality; Stein’s method; permutation; graph
Full Text:
##### References:
  Baldi, P. and Rinott, Y. (1989). Asymptotic normality of some graph-related statistics. J. Appl. Prob. 26 , 171–175. · Zbl 0671.60018  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  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  Bayer, D. and Diaconis, P. (1992). Trailing the dovetail shuffle to its lair. Ann. Appl. Prob. 2 , 294–313. JSTOR: · Zbl 0757.60003  Bhattacharya, R. N. and Ranga Rao, R. (1986). Normal Approximation and Asymptotic Expansions . Krieger, Melbourne, FL. · Zbl 0657.41001  Biggs, N. (1993). Algebraic Graph Theory . Cambridge University Press. · Zbl 0805.68094  Bolthausen, E. (1984). An estimate of the remainder in a combinatorial central limit theorem. Z. Wahrscheinlichkeitsth . 66 , 379–386. · Zbl 0563.60026  Bolthausen, E. and Götze, F. (1993). The rate of convergence for multivariate sampling statistics. Ann. Statist. 21 , 1692–1710. JSTOR: · Zbl 0798.62023  Brouwer, A. E., Cohen, A. M. and Neumaier, A. (1989). Distance-Regular Graphs . Springer, Berlin. · Zbl 0747.05073  Chen, L. H. Y. and Shao, Q.-M. (2004). Normal approximation under local dependence. Ann. Prob. 32 , 1985–2028. · Zbl 1048.60020  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  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  Glaz, J., Naus, J. and Wallenstein, S. (2001). Scan Statistics. Springer, New York. · Zbl 0983.62075  Goldstein, L. (2004). Normal approximation for hierarchical sequences. Ann. Appl. Prob. 14 , 1950–1969. · Zbl 1064.60056  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  Goldstein, L. and Reinert, G. (2005). Distributional transformations, orthogonal polynomials, and Stein characterizations. J. Theoret. Prob. 18 , 185–208. · Zbl 1072.62002  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  Goldstein, L. and Rinott, Y. (2004). A permutation test for matching and its asymptotic distribution. Metron 61 , 375–388.  Götze, F. (1991). On the rate of convergence in the multivariate CLT. Ann. Prob. 19 , 724–739. JSTOR: · Zbl 0729.62051  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  Huang, H. (2002). Error bounds on multivariate normal approximations for word count statistics. Adv. Appl. Prob. 34 , 559–586. · Zbl 1021.62008  Kolchin, V. F. and Chistyakov, V. P. (1973). On a combinatorial limit theorem. Theory Prob. Appl. 18 , 728–739. · Zbl 0314.60011  Naus, J. I. (1982). Approximations for distributions of scan statistics. J. Amer. Statist. Assoc. 77 , 177–183. · Zbl 0482.62010  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  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  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  Stein, C. (1972). Estimation of the mean of a multivariate normal distribution. Ann. Prob. 9 , 1135–1151. JSTOR: · Zbl 0476.62035  Stein, C. (1986). Approximate Computation of Expectations (Inst. Math. Statist. Lecture Notes Monogr. Ser. 7 ). IMS, Hayward, CA. · Zbl 0721.60016  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.