×

Limits of logarithmic combinatorial structures. (English) Zbl 1044.60003

Summary: Under very mild conditions, we prove that the limiting behavior of the component counts in a decomposable logarithmic combinatorial structure conforms to a single, unified pattern, which includes functional central limit theorems, P. Erdős and P. Turán laws [Acta Math. Acad. Sci. Hung. 18, 309–320 (1967; Zbl 0235.20003)], Poisson-Dirichlet limits for the large components and Poisson approximation in total variation for the total number of components. Our approach is entirely probabilistic, and the conditions can readily be verified in practice.

MSC:

60C05 Combinatorial probability
60F05 Central limit and other weak theorems

Citations:

Zbl 0235.20003
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldous, D. J. (1985). Exchangeability and related topics. Lecture Notes in Math. 17 1-198. Springer, New York. · Zbl 0562.60042
[2] Arratia, R., Barbour, A. D. and Tavaré, S. (1993). On random polynomials over a finite field. Math.Proc.Cambridge Philos.Soc.114 347-368. · Zbl 0789.60034 · doi:10.1017/S0305004100071620
[3] Arratia, R., Barbour, A. D. and Tavaré, S. (1999). On Poisson-Dirichlet limits for random decomposable combinatorial structures. Combin.Probab.Comput.8 193-208. · Zbl 0938.60019 · doi:10.1017/S0963548399003788
[4] Arratia, R., Barbour, A. D. and Tavaré, S. (2000). Logarithmic combinatorial structures. Unpublished manuscript. · Zbl 1044.60003 · doi:10.1214/aop/1019160500
[5] Arratia, R. and Tavaré, S. (1994). Independent process approximations for random combinatorial structures. Adv.Math.104 90-154. · Zbl 0802.60008 · doi:10.1006/aima.1994.1022
[6] Barbour, A. D. and Hall, P. G. (1984). On the rate ofPoisson convergence. Math.Proc.Cambridge Philos.Soc.95 473-480. · Zbl 0544.60029 · doi:10.1017/S0305004100061806
[7] Barbour, A. D. and Tavaré, S. (1994). A rate for the Erdös-Turán law. Combin.Probab.Comput. 3 167-176. · Zbl 0805.60008 · doi:10.1017/S0963548300001097
[8] De Laurentis, J. M. and Pittel, B. (1985). Random permutations and Brownian motion. Pacific J.Math.119 287-301. · Zbl 0578.60033 · doi:10.2140/pjm.1985.119.287
[9] Erd ös, P. and Turán, P. (1967). On some problems ofstatistical group theory III. Acta Math. Acad.Sci.Hungar.18 309-320. · Zbl 0235.20003 · doi:10.1007/BF02280290
[10] Ewens, W. J. (1972). The sampling theory ofselectively neutral alleles. Theoret.Population Biol. 3 87-112. · Zbl 0245.92009 · doi:10.1016/0040-5809(72)90035-4
[11] 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 · doi:10.1016/0097-3165(90)90056-3
[12] Goh, W. M. Y. and Schmutz, E. (1993). Random matrices and Brownian motion. Combin.Probab. Comput. 2 157-180. · Zbl 0793.15014 · doi:10.1017/S0963548300000572
[13] Hansen, J. C. (1989). A functional central limit theorem for random mappings. Ann.Probab. 17 317-332. · Zbl 0667.60009 · doi:10.1214/aop/1176991511
[14] Hansen, J. C. (1990). A functional central limit theorem for the Ewens Sampling Formula. J.Appl.Probab.27 28-43. JSTOR: · Zbl 0704.92011 · doi:10.2307/3214593
[15] Hansen, J. C. (1993). Factorization in GF qm x and Brownian motion. Combin.Probab. Comput. 2 285-299. · Zbl 0793.60094 · doi:10.1017/S0963548300000687
[16] Hansen, J. C. (1994). Order statistics for decomposable combinatorial structures. Random Structures Algorithms 5 517-533. · Zbl 0807.60012 · doi:10.1002/rsa.3240050404
[17] Hansen, J. C. and Schmutz, E. (1993). How random is the characteristic polynomial ofa random matrix? Math.Proc.Cambridge Philos.Soc.114 507-515. · Zbl 0793.15013 · doi:10.1017/S0305004100071796
[18] Hildebrand, A. and Tenenbaum, G. (1993). On a class of differential-difference equations arising in number theory. J.Anal.Math.61 145-179. Hwang, H.-K. (1998a). On convergence rates in the central limit theorems for combinatorial structures. European J.Combin.19 329-343. Hwang, H.-K. (1998b). A Poisson geometric convolution law for the number of components in unlabelled combinatorial structures. Combin.Probab.Comput.7 89-110. · Zbl 0797.11072 · doi:10.1007/BF02788841
[19] Hwang, H.-K. (1999). Asymptotics ofPoisson approximation to random discrete distributions: an analytic approach. Adv.Appl.Probab.31 448-491. · Zbl 0945.60001 · doi:10.1239/aap/1029955143
[20] Mutafciev, L. R. (1990). Large components and cycles in a random mapping pattern. In Random Graphs ’87 (M. Karo ński, J. Jaworski and A. Ruci ński, eds.) 189-202. Wiley, New York. · Zbl 0741.05043
[21] Nicolas, J.-L. (1984). A Gaussian law on FQ X. Colloq.Math.Soc.János Bolyai 34 1127-1162. · Zbl 0548.10034
[22] Nicolas, J.-L. (1985). Distribution statistique de l’ordre d’un élément du groupe symétrique. Acta Math.Hungar.45 69-84. · Zbl 0574.10044 · doi:10.1007/BF01955024
[23] Vershik, A. M. and Shmidt, A. A. (1977). Limit measures arising in the theory ofgroups. I. Theory Probab.Appl.22 79-85. · Zbl 0375.60007
[24] Vervaat, W. (1972). Success Epochs in Bernoulli Trials with Applications in Number Theory. Math. Centrum, Amsterdam. · Zbl 0267.60003
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.