Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T17:52:57.982Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotics of poisson approximation to random discrete distributions: an analytic approach

Part of: Combinatorial probability Finite fields and commutative rings (number-theoretic aspects) Multiplicative number theory Combinatorics Limit theorems

Published online by Cambridge University Press:  01 July 2016

Hsien-Kuei Hwang
Hsien-Kuei Hwang*
Affiliation:
Academia Sinica
*
∗ Postal address: Institute of Statistical Science, Academia Sinica, Taipei 115, Taiwan. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A general analytic scheme for Poisson approximation to discrete distributions is studied in which the asymptotic behaviours of the generalized total variation, Fortet-Mourier (or Wasserstein), Kolmogorov and Matusita (or Hellinger) distances are explicitly characterized. Applications of this result include many number-theoretic functions and combinatorial structures. Our approach differs from most of the existing ones in the literature and is easily amended for other discrete approximations; arithmetic and combinatorial examples for Bessel approximation are also presented. A unified approach is developed for deriving uniform estimates for probability generating functions of the number of components in general decomposable combinatorial structures, with or without analytic continuation outside their circles of convergence.

Keywords

Poisson approximationEwens sampling formulaconvolution methodsingularity analysisarithmetic functionscombinatorial structuresgenerating functions

MSC classification

Primary: 60C05: Combinatorial probability 60F99: None of the above, but in this section
Secondary: 11N60: Distribution functions associated with additive and positive multiplicative functions 11T06: Polynomials 05A99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 31 , Issue 2 , June 1999 , pp. 448 - 491
Copyright
Copyright © Applied Probability Trust 1999 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Part of the work was done while the author was visiting University of the Witwatersrand, Johannesburg.

References

Aldous, D. (1989). Probability approximations via the Poisson clumping heuristic. Springer, New York.Google Scholar
Aldous, D. J. and Pitman, J. (1994). Brownian bridge asymptotics for random mappings. Random Structures Algorithms 5, 487–512.CrossRefGoogle Scholar
Andrews, G. E. (1976). The theory of partitions. In Encyclopedia of Mathematics and its Applications, Vol. 2, ed. Rota, G.-C.. Addison-Wesley, London.Google Scholar
Arratia, R. and Tavaré, S. (1992). Limit theorems for combinatorial structures via discrete process approximations. Random Structures Algorithms 3, 321–345.Google Scholar
Arratia, R. and Tavaré, S. (1994). Independent process approximations for random combinatorial structures. Adv. Math. 104, 90–154.Google Scholar
Arratia, R., Goldstein, L. and Gordon, L. (1990). Poisson approximation and the {Chen–Stein} method. Statist. Sci. 5, 403–434.Google Scholar
Arratia, R., Barbour, A. D. and Tavaré, S. (1992). Poisson process approximations for the Ewens sampling formula. Ann. Appl. Prob. 2, 519–535.Google Scholar
Arratia, R., Barbour, A. D. and Tavaré, S. (1993). On random polynomials over finite fields. Math. Proc. Camb. Phil. Soc. 114, 347–368.Google Scholar
Arratia, R., Stark, D. and Tavaré, S. (1995). Total variation asymptotics for Poisson process approximations of logarithmic combinatorial assemblies. Ann. Prob. 23, 1347–1388.Google Scholar
Balazard, M. (1987). Sur la répartition des valeurs de certaines fonctions arithmétiques additives. Thèse, Université de Limoges.Google Scholar
Balazard, M., Delange, H. and Nicolas, J.-L. (1988). Sur le nombre de facteurs premiers des entiers. C. R. Acad. Sci. Paris, Sér. I Math. 306, 511–514.Google Scholar
Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson approximation. Clarendon, Oxford.Google Scholar
Bender, E. A. (1973). Central and local limit theorems applied to asymptotic enumeration. J. Combin. Theory, Ser. A 15, 91–111.Google Scholar
Bender, E. A. and Richmond, L. B. (1983). Central and local limit theorems applied to asymptotic enumeration. II. Multivariate generating functions. J. Combin. Theory, Ser. A 34, 255–265.CrossRefGoogle Scholar
Bender, E. A., Richmond, L. B. and Williamson, S. G. (1983). Central and local limit theorems applied to asymptotic enumeration. III. Matrix recursions J. Combin. Theory, Ser. A 35, 263–278.Google Scholar
Bergeron, F., Flajolet, P. and Salvy, B. (1992). Varieties of increasing trees. In Proc. CAAP '92 (Lecture Notes in Comput. Sci. 581). Springer, New York, pp. 24–48.Google Scholar
Billingsley, P. (1974). The probability theory of additive arithmetic functions. Ann. Prob. 2, 749–791.Google Scholar
Borovkov, K. and Pfeifer, D. (1995). On record indices and record times. J. Statist. Plann. Inference 45, 65–79.Google Scholar
Brown, T. C. (1984). Poisson approximation and the definition of Poisson process. Amer. Math. Monthly 91, 116–123.CrossRefGoogle Scholar
Canfield, E. R. (1977). Central and local limit theorems for the coefficients of polynomials of binomial type. J. Combin. Theory, Ser. A 23, 275–290.CrossRefGoogle Scholar
Chihara, T. S. (1978). An introduction to orthogonal polynomials. Gordon and Breach, New York.Google Scholar
Deheuvels, P. and Pfeifer, D. (1986). A semigroup approach to Poisson approximation. Ann. Prob. 14, 663–676.Google Scholar
Deheuvels, P. and Pfeifer, D. (1988). On a relationship between Uspensky's theorem and Poisson approximation. Ann. Inst. Statist. Math. 40, 671–681.CrossRefGoogle Scholar
Deheuvels, P., Karr, A., Pfeifer, D. and Serfling, R. (1988). Poisson approximations in selected metrics by coupling and semigroup methods with applications. J. Statist. Plann. Inference 20, 1–22.Google Scholar
Delange, H. (1956). Sur la distribution des entiers ayant certaines propriétés. Ann. Sci. École Norm. Sup. 73, 15–74.Google Scholar
DeLaurentis, J.-M. and Pittel, B. G. (1985). Random permutations and Brownian motion. Pacific J. Math. 119, 287–301.Google Scholar
Donnelly, P. and Grimmett, G. (1993). On the asymptotic distribution of large prime factors. J. Lond. Math. Soc. 47, 395–404.Google Scholar
Donnelly, P. J., Ewens, W. J. and Padmadisastra, S. (1991). Functionals of random mappings: exact and asymptotic results. Adv. Appl. Prob. 23, 437–455.CrossRefGoogle Scholar
Donnelly, P., Kurtz, T. G. and Tavaré, S. (1991). On the functional central limit theorem for the Ewens sampling formula. Ann. Appl. Prob. 1, 539–545.CrossRefGoogle Scholar
Elliott, P. D. T. A. (1980). Probabilistic number theory, volume II, Central limit theorems. Springer, New York.Google Scholar
Erd Hos, P. and {Turán}, P.} (1965). On some problems of a statistical group theory. Z. Wahrscheinlichskeitsth. 4, 175–186.Google Scholar
Ewens, W. J. (1972). The sampling theory of selectively neutral alleles. Theoret. Pop. Biol. 3, 87–112.Google Scholar
Falk, M. and Reiss, R.-D. (1992). Poisson approximation of empirical processes. Statist. Prob. Lett. 14, 39–48.Google Scholar
Flajolet, P. and Odlyzko, A. M. (1990). Random mapping statistics, EUROCRYPT '89 (Lecture Notes in Comput. Sci. 434). Springer, New York, pp. 329–354.Google Scholar
Flajolet, P. and Odlyzko, A. M. (1990). Singularity analysis of generating functions. SIAM J. Discrete Math. 3, 216–240.Google Scholar
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.Google Scholar
Flajolet, P. and Soria, M. (1993). General combinatorial schemes: {Gaussian} limit distributions and exponential tails. Discrete Math. 114, 159–180.Google Scholar
Foata, D. (1974). La série génératrice exponentielle dans les problèmes d'énumération. Les Presses de l'Université de Montréal, Montréal.Google Scholar
Franken, P. (1964). Approximation des Verteilungen von Summen unabhängiger nichtnegativer ganzzahler Zufallsgrössen durch Poissonsche verteilungen. Math. Nachrich. 23, 303–340.Google Scholar
Gao, Z. and Richmond, L. B. (1992). Central and local limit theorems applied to asymptotic enumeration IV: multivariate generating functions. J. Comput. Appl. Math. 41, 177–186.Google Scholar
Goh, W. M. Y. and Schmutz, E. (1991). A central limit theorem on GLn(Fq). Random Structures Algorithms 2, 47–53.Google Scholar
Goh, W. M. Y. and Schmutz, E. (1993). Random matrices and Brownian motion. Combin. Prob. Comput. 2, 157–180.Google Scholar
Goulden, I. P. and Jackson, D. M. (1983). Combinatorial enumeration. John Wiley, New York.Google Scholar
Greene, D. H. and Knuth, D. E. (1990). Mathematics for the analysis of algorithms, 3rd edn. Birkhäuser, Boston.Google Scholar
{Halász, G.} (1971). On the distribution of additive and the mean values of multiplicative functions. Stud. Scient. Math. Hungar. 6, 211–233.Google Scholar
{Halász, G.} (1975). On the distribution of additive arithmetic functions. Acta Arith. 27, 143–152.Google Scholar
Hansen, J. C. (1989). A functional central limit theorem for random mappings. Ann. Prob. 17, 317–332. Correction: (1991), 19, 1393–1396.Google Scholar
Hansen, J. C. (1990). A functional central limit theorem for the Ewens sampling formula. J. Appl. Prob. 27, 28–43.CrossRefGoogle Scholar
Hansen, J. C. (1993). Factorization in {F_q[X]} and Brownian motion. Combin. Prob. Comput. 2, 285–299.Google Scholar
Hansen, J. C. (1994). Order statistics for decomposable combinatorial structures. Random Structures Algorithms 5, 517–533.Google Scholar
Harper, L. H. (1967). Stirling behaviour is asymptotically normal. Ann. Math. Statist. 38, 410–414.Google Scholar
Hensley, D. (1987). The distribution of the number of factors in a factorization. J. Number Theory 26, 179–191.Google Scholar
Hwang, H.-K. (1994). {Théorèmes limites pour les structures combinatoires et les fonctions {arithmétiques}}. Thèse, École polytechnique.Google Scholar
Hwang, H.-K. (1996). Large deviations for combinatorial distributions, I. central limit theorems. Ann. Appl. Prob. 6, 297–319.Google Scholar
Hwang, H.-K. (1997). Asymptotic estimates of elementary probability distributions. Stud. Appl. Math. 99, 393–417.Google Scholar
Hwang, H.-K. (1998). A Poisson,*,geometric law for the number of components in unlabelled combinatorial structures. Random Structures Algorithms 7, 89–110.Google Scholar
Hwang, H.-K. (1998). On convergence rates in the central limit theorems for combinatorial structures. European J. Combin. 19, 329–343.Google Scholar
Janson, S. (1994). Coupling and Poisson approximation. Acta Appl. Math. 34, 7–15.Google Scholar
Johnson, N. L., Kotz, S. and Kemp, A. W. (1992). Univariate discrete distributions, 2nd edn. John Wiley, New York.Google Scholar
Joyce, P. and {Tavaré}, S. (1992). A convergence theorem for symmetric functionals of random partitions. J. Appl. Prob. 29, 280–290.Google Scholar
Kerstan, J. (1964). Verallgemeinerung eines Satzes von Prochorow und Le Cam. Z. Wahrscheinlichskeitsth. 2, 173–179.Google Scholar
Knopfmacher, A., Knopfmacher, J. and Warlimont, R. (1992). “Factorisatio numerorum” in arithmetical semigroups. Acta Arith. 61, 327–336.Google Scholar
Knopfmacher, A. and Warlimont, R. (1996). Counting permutations and polynomials with a restricted factorization pattern. Austral. J. Combin. 13, 151–162.Google Scholar
Knopfmacher, J. (1979). Analytic arithmetic of algebraic function fields (Lecture Notes in Pure and Appl. Math. 50). Marcel Dekker, New York.Google Scholar
Kolchin, V. F. (1986). Random mappings. Optimization Software, New York.Google Scholar
Kung, J. (1981). The cycle structure of a linear transformation over a finite field. Lin. Alg. Appl. 36, 141–155.Google Scholar
Le Cam, L. (1960). An approximation theorem for the Poisson binomial distribution. Pacific J. Math. 10, 1181–1197.CrossRefGoogle Scholar
Nevzorov, V. B. (1987). Records. Theory Prob. Appl. 32, 201–228.Google Scholar
Nicolas, J.-L. (1985). Distribution statistique de l'ordre d'un élément du groupe symétrique. Acta Math. Hungar. 45, 69–84.Google Scholar
Pavlov, A. I. (1985). On the limit distribution of the number of cycles and the logarithm of the order of a class of permutations. Sb Math. (Translation of Matematicheskii Sbornik) 45, 69–84.Google Scholar
Pitman, J. (1997). Probabilistic bounds on the coefficients with only real zeros. J. Combin. Theory, Ser. A 77, 279–303.Google Scholar
Pfeifer, D. (1991). Some remarks on Nevzorov's record model. Adv. Appl. Prob. 23, 823–834.CrossRefGoogle Scholar
Prohorov, Y. V. (1953). Asymptotic behavior of the binomial distribution. Uspekhi Matematicheskikh Nauk 8, 135–142. Also in Selected Translations in Mathematical Statistics and Probability, Vol. 1, 87–95.Google Scholar
Reiss, R.-D. (1989). Approximate distributions of order statistics, with applications to nonparametric statistics. Springer, New York.Google Scholar
Romanowska, M. (1977). A short note on the upper bound for the distance in total variation between the binomial and Poisson distribution. Statist. Neerlandica 31, 127–130.Google Scholar
Roos, B. (1995). A semigroup approach to Poisson approximation with respect to the point metric. Statist. Prob. Lett. 24, 305–314.Google Scholar
Selberg, A. (1954). Note on a paper by L. G. Sathe. J. Indian Math. Soc. 18, 83–87.Google Scholar
Serfling, R. J. (1978). Some elementary results on Poisson approximation in a sequence of Bernoulli trials. SIAM Review 20, 567–579.Google Scholar
Shorgin, S. Y. (1977). Approximation of a generalized Binomial distribution. Theory Prob. Appl. 22, 846–850.Google Scholar
Smythe, R. T. and Mahmoud, H. M. (1995). A survey of recursive trees. Theory Prob. Math. Statist. 51, 1–27.Google Scholar
Soria, M. (1990). Méthode d'analyse pour les constructions combinatoires et les algorithmes. Thèse d'État, Université de Paris-Sud.Google Scholar
Steele, J. M. (1994). Le Cam's inequality and Poisson approximations. Amer. Math. Monthly 101, 48–54.Google Scholar
Stong, R. (1988). Some asymptotic results on finite vector spaces. Adv. Appl. Math. 9, 167–199.Google Scholar
{Szabó, Z. I. (1986). Hilbert's fourth problem. I. Adv. Math. 59, 185–301.Google Scholar
{Szegö, G., (1977). Orthogonal polynomials. Vol. XXIII. of American Mathematical Society Colloquium Publications, 4th edn. AMS, Providence, RI.Google Scholar
Székely, L. A. (1985). Holiday numbers: sequences resembling to the Stirling numbers of the second kind. Acta Math. Hungar. 48, 459–467.Google Scholar
Székely, L. A. (1987). The analytic behavior of the holiday numbers. Acta Math. Hungar. 51, 365–369.Google Scholar
Tenenbaum, G. (1990). Introduction à la théorie analytique et probabiliste des nombres. Institut Élie Cartan, Université de Nancy I, Nancy, France. English version by C. B. Thomas, Cambridge University Press, 1995.Google Scholar
Uspensky, J. V. (1931). On Ch. Jordan's series for probability. Ann. Math. 32, 306–312.Google Scholar
Vervaat, W. (1969). Upper bound for the distance in total variation between the binomial and the Poisson distribution. Statist. Neerlandica 23, 79–86.Google Scholar
Whittaker, E. T. and Watson, G. N. (1927). A course of modern analysis, 4th edn. CUP, Cambridge.Google Scholar
Wilf, H. S. (1983). Three problems in combinatorial asymptotics. J. Combin. Theory, Ser. A 35, 199–207.CrossRefGoogle Scholar
Witte, H.-J. (1990). A unification of some approaches to Poisson approximation. J. Appl. Prob. 27, 611–621.Google Scholar
Wong, R. (1989). Asymptotic approximations of integrals. Academic Press, Boston.Google Scholar
Wright, E. M. (1935). The asymptotic expansion of the generalized Bessel functions. Proc. Lond. Math. Soc. 38, 257–270.Google Scholar
Zolotarev, V. M. (1983). Probability metrics. Theory Prob. Appl. 28, 278–302.Google Scholar