×
Hwang, Hsien-Kuei

Large deviations for combinatorial distributions. I: Central limit theorems. (English) Zbl 0863.60013

Ann. Appl. Probab. 6, No. 1, 297-319 (1996).
Summary: We prove a general central limit theorem for probabilities of large deviations for sequences of random variables satisfying certain analytic conditions. This theorem has wide applications to combinatorial structures and to the distribution of additive arithmetical functions. The method of proof is an extension of Kubilius’ version of Cramér’s classical method based on analytic moment generating functions. We thus generalize Cramér’s and Kubilius’s theorems on large deviations.

Cited in 3 Reviews
Cited in 19 Documents

MSC:

60C05 Combinatorial probability
60F10 Large deviations
05A16 Asymptotic enumeration
11N05 Distribution of primes
11N37 Asymptotic results on arithmetic functions

Keywords:

large deviations; combinatorial constructions; central limit theorems; additive arithmetical functions
PDF BibTeX XML Cite
\textit{H.-K. Hwang}, Ann. Appl. Probab. 6, No. 1, 297--319 (1996; Zbl 0863.60013)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] BENDER, E. A. 1973. Central and local limit theorems applied to asy mptotic enumeration. J. Combin. Theory Ser. A 15 91 111. · Zbl 0242.05006
[2] BERGERON, F., FLAJOLET, P. and SALVY, B. 1992. Varieties of increasing trees. In CAAP ’92. Lecture Notes in Comput. Sci. 581 24 48. Springer, New York.
[3] BUCKLEW, J. A. 1990. Large Deviation Techniques in Decision, Simulation, and Estimation. Wiley, New York.
[4] CANFIELD, E. R. 1977. Central and local limit theorems for the coefficients of poly nomials of binomial ty pe. J. Combin. Theory Ser. A 23 275 290. · Zbl 0412.60032
[5] CANFIELD, E. R. 1980. Application of the Berry Esseen inequality to combinatorial estimates. J. Combin. Theory Ser. A 28 17 25. · Zbl 0429.05007
[6] CHERNOFF, H. 1952. A measure of asy mptotic efficiency for tests of a hy pothesis based on the sums of observations. Ann. Math. Statist., 23 493 507. · Zbl 0048.11804
[7] CRAMER, H. 1938. Sur un nouveau theoreme-limite de la theorie des probabilites. In \' \' \' Áctualites Scientifiques et Industrielles 736 5 23. Herman, Paris. \' · JFM 64.0529.01
[8] DELANGE, H. 1971. Sur des formules de Atle Selberg. Acta Arith. 19 105 146. · Zbl 0217.31902
[9] ESSEEN, C.-G. 1945. Fourier analysis of distribution functions. A mathematical study of the Laplace Gaussian law. Acta Math. 77 1 125. · Zbl 0060.28705
[10] FELLER, W. 1971. An Introduction to Probability Theory and Its Applications 2, 2nd ed. Wiley, New York. · Zbl 0219.60003
[11] FLAJOLET, P., FRANC \?ON, J. and VUILLEMIN, J. 1980. Sequence of operations analysis for dy namic data structures. J. Algorithms 1 111 141. · Zbl 0445.68036
[12] FLAJOLET, P. and ODLy ZKO, A. M. 1990. Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216 240. · Zbl 0712.05004
[13] FLAJOLET, P. and PRODINGER, H. 1986. Level number sequences for trees. Discrete Math. 65 149 156. · Zbl 0634.05021
[14] FLAJOLET, P. and SEDGEWICK, R. 1993. The average case analysis of algorithms, counting and generating functions. Research Report 1888, INRIA, Rocquencourt.
[15] FLAJOLET, P. and SORIA, M. 1990. Gaussian limiting distributions for the number of components in combinatorial structures. J. Combin. Theory Ser. A 53 165 182. · Zbl 0691.60035
[16] FLAJOLET, P. and SORIA, M. 1993. General combinatorial schemes, Gaussian limit distributions and exponential tails. Discrete Math. 114 159 180. · Zbl 0776.60013
[17] GAO, Z. and RICHMOND, L. B. 1992. Central and local limit theorems applied to asy mptotic enumeration. IV. Multivariate generating functions. J. Comput. Appl. Math. 41 177 186. · Zbl 0755.05004
[18] HWANG, H.-K. 1994. Theoremes limites pour les structures combinatoires et les fonctions árithmetiques. These, Ecole Poly technique. \'
[19] HWANG, H.-K. 1995. On asy mptotic expansions in the central and local limit theorems for combinatorial structures. Unpublished manuscript.
[20] HWANG, H.-K. 1995. On convergence rates in the central limit theorems for combinatorial structures. Unpublished manuscript.
[21] HWANG, H.-K. 1995. Large deviations of combinatorial distributions. II. Local limit theorems. Unpublished manuscript. \"
[22] KHINTCHINE, A. Uber einen neuen Grennzwertsatz der Wahrscheinlichkeitsrechnung. Math. Ann. 101 745 752. · JFM 55.0297.03
[23] KNOPFMACHER, A., KNOPFMACHER, J. and WARLIMONT, R. 1992. “Factorisatio numerorum” in arithmetical semigroups. Acta Arith. 61 327 336. · Zbl 0772.11038
[24] KNOPFMACHER, J. 1979. Analy tic Arithmetic of Algebraic Function Fields. Lecture Notes in Pure Appl. Math. 50. Dekker, New York. · Zbl 0411.10001
[25] KOLASSA, J. E. 1994. Series Approximation Methods in Statistics. Lecture Notes in Statist. 88. Springer, New York. · Zbl 0797.62008
[26] KUBILIUS, J. 1964. Probabilistic Methods in the Theory of Numbers. Amer. Math. Soc., Providence, RI. · Zbl 0133.30203
[27] LUKACS, E. 1960. Characteristic Functions. Griffin, London. · Zbl 0087.33605
[28] MAEJIMA, M. and VAN ASSCHE, W. 1985. Probabilistic proofs of asy mptotic formulas for some orthogonal poly nomials. Math. Proc. Cambridge Philos. Soc. 97 499 510. · Zbl 0557.33006
[29] MAHMOUD, H. M. 1992. Evolution of Random Search Trees. Wiley, New York. · Zbl 0762.68033
[30] MEIR, A. and MOON, J. W. 1978. On the altitude of nodes in random trees. Canad. J. Math. 30 997 1015. · Zbl 0394.05015
[31] MEIR, A. and MOON, J. W. 1992. On nodes of given out-degree in random trees. In Fourth Czechoslovakian Sy mposium on Combinatorics, Graphs and Complexity. Annals of Z. Discrete Mathematics J. Nesetril and M. Fiedler, eds. 51 213 222. North-Holland, Amsterdam. · Zbl 0779.05051
[32] ODLy ZKO, A. M. 1992. Explicit Tauberian estimates for functions with positive coefficients. J. Comput. Appl. Math. 41 187 197. · Zbl 0763.40006
[33] PETROV, V. V. 1975. Sums of Independent Random Variables. Springer, Berlin. Trans. lated from the Russian by A. A. Brown. · Zbl 0322.60043
[34] RICHTER, W. 1964. A more precise form of an inequality of S. N. Bernstein. For large deviations. Selected Translations of Mathematical Statistics and Probability 4 225 232. Originally published in Vestnik Leningrad. Univ. Mat. Mek. Astronom. 14 Z. 24 29 1959.
[35] SAULIS, L. and STATULEVICIUS, V. A. 1991. Limit Theorems for Large Deviations. Kluwer, Dordrecht.
[36] SORIA, M. 1990. Methode d’analyse pour les constructions combinatoires et les algo\' ŕithmes. These d’Etat, Univ. Paris-Sud.
[37] STROOCK, D. W. 1984. An Introduction to the Theory of Large Deviations. Springer, New York. · Zbl 0552.60022
[38] SZEGO, G. 1977. Orthogonal Poly nomials. 4th ed. Amer. Math. Soc., Providence, RI. \"
[39] WHITTAKER, E. T. and WATSON, G. N. 1927. A Course of Modern Analy sis: An Introduction to the General Theory of Infinite Processes and of Analy tic Functions; with an Account of the Principal Transcendental Functions, 4th ed. Cambridge Univ. Press. · JFM 53.0180.04
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.