×

Trees grown under young-age preferential attachment. (English) Zbl 1453.05022

Summary: We introduce a class of non-uniform random recursive trees grown with an attachment preference for young age. Via the Chen-Stein method of Poisson approximation, we find that the outdegree of a node is characterized in the limit by ‘perturbed’ Poisson laws, and the perturbation diminishes as the node index increases. As the perturbation is attenuated, a pure Poisson limit ultimately emerges in later phases. Moreover, we derive asymptotics for the proportion of leaves and show that the limiting fraction is less than one half. Finally, we study the insertion depth in a random tree in this class. For the insertion depth, we find the exact probability distribution, involving Stirling numbers, and consequently we find the exact and asymptotic mean and variance. Under appropriate normalization, we derive a concentration law and a limiting normal distribution. Some of these results contrast with their counterparts in the uniform attachment model, and some are similar.

MSC:

05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
90B15 Stochastic network models in operations research
60C05 Combinatorial probability
60F25 \(L^p\)-limit theorems
60F05 Central limit and other weak theorems
11B73 Bell and Stirling numbers
Full Text: DOI

References:

[1] Albert, R. andBarabási, A. (2002). Statistical mechanics of complex networks. Rev. Modern Phys.41, 47-97. · Zbl 1205.82086
[2] Barabási, A. (2016). Network Science. Cambridge University Press, Cambridge. · Zbl 1353.94001
[3] Barabási, A. andAlbert, R. (1999). Emergence of scaling in random networks. Science286, 509-512. · Zbl 1226.05223
[4] Bollobás, B., Riordan, O. andSpencer, J. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms18, 279-290. · Zbl 0985.05047
[5] Chow, Y. andTeicher, M. (1997). Probability Theory: Independence, Interchangeability, Martingales. Springer, New York. · Zbl 0891.60002
[6] Curtiss, J. (1942). A note on the theory of moment generating functions. Ann. Math. Statist.13, 430-433. · Zbl 0063.01024
[7] Drmota, M. (2009). Random Trees: An Interplay Between Combinatorics and Probability. Springer, New York. · Zbl 1170.05022
[8] Frieze, A. andKaroński, M. (2016). Introduction to Random Graphs, 2nd edn. Cambridge University Press, Cambridge. · Zbl 1328.05002
[9] Gastwirth, J. andBhattacharya, P. (1984). Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable. Operat. Res.32, 527-536. · Zbl 0544.90062
[10] Gut, A. (2013). Probability: A Graduate Course, 2nd edn. Springer, New York. · Zbl 1267.60001
[11] Hofri, M. andMahmoud, H. (2018). Algorithmics of Nonuniformity: Tools and Paradigms. CRC Press, Boca Raton.
[12] Lehmann, E. andCasella, G. (1998). Theory of Point Estimation, 2nd edn. Springer, New York. · Zbl 0916.62017
[13] Mahmoud, H. (1992). Evolution of Random Search Trees. Wiley, New York. · Zbl 0762.68033
[14] Najock, D. andHeyde, C. (1982). On the number of terminal vertices in certain random trees with an application to stemma construction in philology. J. Appl. Prob.19, 675-680. · Zbl 0487.60012
[15] Ross, N. (2011). Fundamentals of Stein’s method. Prob. Surv.8, 210-293. · Zbl 1245.60033
[16] Smythe, R. andMahmoud, H. (1995). A survey of recursive trees. Theory Prob. Math. Statist.51, 1-27. · Zbl 0933.05038
[17] Smythe, R., Mahmoud, H. andSzymański, J. (1993). On the structure of plane-oriented recursive trees and their branches. Random Structures Algorithms4, 151-176. · Zbl 0773.05040
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.