ABSTRACT
The theme in this paper is a composition of random graphs and Pólya urns. The random graphs are generated through a small structure called the seed. Via Pólya urns, we study the asymptotic degree structure in a random $m$-ary hooking network and identify strong laws. We further upgrade the result to second-order asymptotics in the form of multivariate Gaussian limit laws. We give a few concrete examples and explore some properties with a full representation of the Gaussian limit in each case. The asymptotic covariance matrix associated with the Pólya urn is obtained by a new method that originated in this paper and is reported in [25].
► BibTeX data
► References
[1] Athreya, K. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. The Annals of Mathematical Statistics 39, 1801–1817. https://doi.org/10.1214/aoms/1177698013.
https://doi.org/10.1214/aoms/1177698013
[2] Bagchi, A. and Pal, A. (1985). Asymptotic normality in the generalized Pólya-Eggenberger urn model with applications to computer data structures. SIAM Journal on Algebraic and Discrete Methods 6, 394–405. https://doi.org/10.1137/0606041.
https://doi.org/10.1137/0606041
[3] Bahrani, M. and Lumbroso, J. (2019). Split-decomposition trees with prime nodes: Enumeration and random generation of cactus graphs. 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 143–157. https://doi.org/10.1137/1.9781611975062.13.
https://doi.org/10.1137/1.9781611975062.13
[4] Bhutani, K., Kalpathy, R. and Mahmoud, H. (2021). Average measures in polymer graphs. International Journal of Computer Mathematics: Computer Systems Theory 6:1, 37–53. https://doi.org/10.1080/23799927.2020.1860134.
https://doi.org/10.1080/23799927.2020.1860134
[5] Bhutani, K., Kalpathy, R. and Mahmoud, H. (2022). Random networks grown by fusing edges via urns. Network Science, 1–14. https://doi.org/10.1017/nws.2022.30.
https://doi.org/10.1017/nws.2022.30
[6] Bhutani, K., Kalpathy, R. and Mahmoud, H. (2023). Random multi-hooking networks. Probability in the Engineering and Informational Sciences, 1–15. https://doi.org/10.1017/s0269964822000523.
https://doi.org/10.1017/s0269964822000523
[7] Bhutani, K., Kalpathy, R., Mahmoud, H. and Ofonedu, A. (2023+). Some empirical and theoretical attributes of random multi-hooking networks (under review).
[8] Brown, G. and Shubert, B. (1984). On random binary trees. Mathematics of Operations Research 9, 43–65. https://doi.org/10.1287/moor.9.1.43.
https://doi.org/10.1287/moor.9.1.43
[9] Chen, C. and Mahmoud, H. (2016). Degrees in random self-similar bipolar networks. Journal of Applied Probability 53, 434–447. https://doi.org/10.1017/jpr.2016.11.
https://doi.org/10.1017/jpr.2016.11
[10] Desmarais, C. and Holmgren, C. (2019). Degree distributions of generalized hooking networks. 2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 103–110. https://doi.org/10.1137/1.9781611975505.11.
https://doi.org/10.1137/1.9781611975505.11
[11] Desmarais, C. and Holmgren, C. (2020). Normal limit laws for vertex degrees in randomly grown hooking networks and bipolar networks. The Electronic Journal of Combinatorics 27(2), P2.45. https://doi.org/10.37236/9139.
https://doi.org/10.37236/9139
[12] Desmarais, C. and Mahmoud, H. (2021). Depths in hooking networks. Probability in the Engineering and Informational Sciences, 1–9. https://doi.org/10.1017/s0269964821000164.
https://doi.org/10.1017/s0269964821000164
[13] Drmota, M., Gittenberger, B. and Panholzer, A. (2008). The degree distribution of thickened trees. DMTCS Proceedings, Fifth Colloquium on Mathematics and Computer Science AI, 149–162. https://doi.org/10.46298/dmtcs.3561.
https://doi.org/10.46298/dmtcs.3561
[14] Freedman, D. (1965). Bernard Friedman's urn. The Annals of Mathematical Statistics 36, 956–970. https://doi.org/10.1214/aoms/1177700068.
https://doi.org/10.1214/aoms/1177700068
[15] Gopaladesikan, M., Mahmoud, H. and Ward, M. (2014). Building random trees from blocks. Probability in the Engineering and Informational Sciences 28, 67–81. https://doi.org/10.1017/s0269964813000338.
https://doi.org/10.1017/s0269964813000338
[16] Holmgren, C., Janson, S. and Sileikis, M. (2017). Multivariate normal limit laws for the numbers of fringe subtrees in $m$-ary search trees and preferential attachment trees. The Electronic Journal of Combinatorics 24, p2.51. https://doi.org/10.37236/6374.
https://doi.org/10.37236/6374
[17] Horn, R. and Johnson, C. (1985). Matrix Analysis. Cambridge University Press, Cambridge, UK.
[18] Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Processes and Their Applications 110, 177–245. https://doi.org/10.1016/j.spa.2003.12.002.
https://doi.org/10.1016/j.spa.2003.12.002
[19] Janson, S. (2020). Mean and variance of balanced Pólya urns. Advances in Applied Probability 52 , 1224–1248. https://doi.org/10.1017/apr.2020.38.
https://doi.org/10.1017/apr.2020.38
[20] Kalpathy, R. and Mahmoud, H. (2016). Degree profile of $m$-ary search trees: A vehicle for data structure compression. Probability in the Engineering and Informational Sciences 30, 133–123. https://doi.org/10.1017/s0269964815000303.
https://doi.org/10.1017/s0269964815000303
[21] Knuth, D. (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd Ed. Addison-Wesley, Boston, Massachusetts.
[22] Mahmoud, H. (2008). Pólya Urn Models. Chapman-Hall, Orlando, Florida.
[23] Mahmoud, H. (2019). Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment. Advances in Applied Mathematics 111, 101930. https://doi.org/10.1016/j.aam.2019.07.006.
https://doi.org/10.1016/j.aam.2019.07.006
[24] Mahmoud, H. (2019). A spectrum of series-parallel graphs with multiple edge evolution. Probability in the Engineering and Informational Sciences 33, 487–499. https://doi.org/10.1017/s0269964818000505.
https://doi.org/10.1017/s0269964818000505
[25] Mahmoud, H. (2021). Covariances in Pólya urn schemes. Probability in the Engineering and Informational Sciences 37, 60–71. https://doi.org/10.1017/s0269964821000450.
https://doi.org/10.1017/s0269964821000450
[26] Pouyanne, N. (2008). An algebraic approach to Pólya processes. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 44, 293–323. https://doi.org/10.1214/07-aihp130.
https://doi.org/10.1214/07-aihp130
[27] Resnick, S. and Samorodnitsky, G. (2016). Asymptotic normality of degree counts in a preferential attachment model. Advances in Applied Probability 48, 283–299. https://doi.org/10.1017/apr.2016.56.
https://doi.org/10.1017/apr.2016.56
[28] Smythe, R. (1996). Central limit theorems for urn models. Stochastic Processes and Their Applications 65, 115–137. https://doi.org/10.1016/s0304-4149(96)00094-4.
https://doi.org/10.1016/s0304-4149(96)00094-4
[29] van der Hofstad, R. (2016). Random Graphs and Complex Networks, Vol. 1. Cambridge University Press, Cambridge, UK.
Cited by
Could not fetch Crossref cited-by data during last attempt 2024-12-05 01:33:15: Could not fetch cited-by data for 10.32408/compositionality-5-6 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2024-12-05 01:33:15).
This Paper is published in Compositionality under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.