×

Degrees in random self-similar bipolar networks. (English) Zbl 1342.05156

Summary: We investigate several aspects of a self-similar evolutionary process that builds a random bipolar network from building blocks that are themselves small bipolar networks. We characterize admissible outdegrees in the history of the evolution. We obtain the limit distribution of the polar degrees (when suitably scaled) characterized by its sequence of moments. We also obtain the asymptotic joint multivariate normal distribution of the number of nodes of small admissible outdegrees. Five possible substructures arise, and each has its own parameters (mean vector and covariance matrix) in the multivariate distribution. Several results are obtained by mapping bipolar networks into Pólya urns.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C80 Random graphs (graph-theoretic aspects)
90B15 Stochastic network models in operations research
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Statist. 39 , 1801-1817. · Zbl 0185.46103 · doi:10.1214/aoms/1177698013
[2] David, F. N. and Barton, D. E. (1962). Combinatorial Chance . Hafner, New York.
[3] Drmota, M., Gittenberger, B. and Panholzer, A. (2008). The degree distribution of thickened trees. In Proceedings of the Fifth Colloquium on Mathematics and Computer Science, Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 149-162. · Zbl 1355.68205
[4] Flajolet, P., Dumas, P. and Puyhaubert, V. (2006). Some exactly solvable models of urn process theory. In Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 59-118. · Zbl 1193.60011
[5] Gopaladesikan, M., Mahmoud, H. and Ward, M. D. (2014). Building random trees from blocks. Prob. Eng. Inf. Sci. 28 , 67-81. · Zbl 1287.05139 · doi:10.1017/S0269964813000338
[6] Graham, R. L., Knuth, D. E. and Patashnik, O. (1994). Concrete Mathematics , 2nd edn. Addison-Wesley, Reading, MA. · Zbl 0836.00001
[7] Janson, S. (2006). Limit theorems for triangular urn schemes. Prob. Theory Relat. Fields 134 , 417-452. · Zbl 1112.60012 · doi:10.1007/s00440-005-0442-7
[8] Kuba, M. and Mahmoud, H. (2016) Two-color balanced affine urn models with multiple drawings. II. large index and triangular urns. Submitted. Available at http://arxiv.org/abs/1509.09053. · Zbl 1366.60019
[9] Lobo, D., Vico, F. J. and Dassow, J. (2011). Graph grammars with string-regulated rewriting. Theoret. Comput. Sci. 412 , 6101-6111. · Zbl 1253.68198 · doi:10.1016/j.tcs.2011.07.004
[10] Mahmoud, H. M. (2009). Pólya Urn Models . CRC, Boca Raton, FL. · Zbl 1149.60005
[11] Matthews, P. C. and Rosenberger W. F. (1997). Variance in randomized play-the-winner clinical trials. Statist. Prob. Lett. 35 , 233-240. · Zbl 0946.62074 · doi:10.1016/S0167-7152(97)00018-7
[12] Rambo, L. R. (2010). Conversion studies, pastoral counseling, and cultural studies: engaging and embracing a new paradigm. Pastoral Psychology 59 , 433-445.
[13] Smythe, R. T. (1996). Central limit theorems for urn models. Stoch. Process. Appl. 65 , 115-137. · Zbl 0889.60013 · doi:10.1016/S0304-4149(96)00094-4
[14] Zhang, P., Chen, C. and Mahmoud, H. (2015). Explicit characterization of moments of balanced triangular Pólya urns by an elementary approach. Statist. Prob. Lett. 96 , 149-153. · Zbl 1314.60040 · doi:10.1016/j.spl.2014.09.016
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.