×

zbMATH — the first resource for mathematics

Long and short paths in uniform random recursive dags. (English) Zbl 1230.60092
The authors’ main concern is the model of the uniform random recursive \(k\)-directed acyclic graph. This random directed graph is constructed as follows. There is a root vertex labeled as 0 and each succesive node labeled from 1 to \(n\) is joined to \(k\) of the previous nodes chosen uniformly at random with replacement. The authors provide results about the length of a random path starting from a certain node and leading to the root node. In particular, they show convergence in probability to a certain constant which they provide explicitly. However, the main result of the paper regards the length of the shortest path to the root that starts at vertex \(n\). In particular, they show that when divided by \(\log n\), this converges in probability to a certain constant which is determined implicitly through a certain function. Moreover, they show that the maximum shortest distance also satisfies this.

MSC:
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
05C80 Random graphs (graph-theoretic aspects)
05A15 Exact enumeration problems, generating functions
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Albert, R. and Barabasi, A., Emergence of scaling in random networks, Science 286 (1999), 509–512. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[2] Albert, R., Barabasi, A. and Jeong, H., Diameter of the World-Wide Web, Nature 401 (1999), 130–131. · doi:10.1038/43601
[3] Biggins, J. D., Chernoff’s theorem in the branching random walk, J. Appl. Probab. 14 (1977), 630–636. · Zbl 0373.60090 · doi:10.2307/3213469
[4] Biggins, J. D. and Grey, D. R., A note on the growth of random trees, Statist. Probab. Lett. 32 (1997), 339–342. · Zbl 0904.60067 · doi:10.1016/S0167-7152(96)00092-2
[5] Broutin, N. and Devroye, L., Large deviations for the weighted height of an extended class of trees, Algorithmica 46 (2006), 271–297. · Zbl 1106.68027 · doi:10.1007/s00453-006-0112-x
[6] Codenotti, B., Gemmell, P. and Simon, J., Average circuit depth and average communication complexity, in Third European Symposium on Algorithms, pp. 102–112, Springer, Berlin, 1995.
[7] Devroye, L., A note on the height of binary search trees, J. Assoc. Comput. Mach. 33 (1986), 489–498. · Zbl 0741.05062 · doi:10.1145/5925.5930
[8] Devroye, L., Branching processes in the analysis of the heights of trees, Acta Inform. 24 (1987), 277–298. · Zbl 0643.60065 · doi:10.1007/BF00265991
[9] Devroye, L., Applications of the theory of records in the study of random trees, Acta Inform. 26 (1988), 123–130. · Zbl 0656.68065 · doi:10.1007/BF02915448
[10] Devroye, L., Branching processes and their applications in the analysis of tree structures and tree algorithms, in Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms Combin. 16, pp. 49–314, Springer, Berlin, 1998. · Zbl 0924.60077
[11] Devroye, L., Universal limit laws for depths in random trees, SIAM J. Comput. 28 (1999), 409–432. · Zbl 0915.68089 · doi:10.1137/S0097539795283954
[12] Díaz, J., Serna, M. J., Spirakis, P., Toran, J. and Tsukiji, T., On the expected depth of Boolean circuits, Technical Report LSI-94-7-R, Universitat Politecnica de Catalunya, Departament de Llenguatges i Sistemes Informàtics, Barcelona, 1994.
[13] Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math. 1 (1959), 269–271. · Zbl 0092.16002 · doi:10.1007/BF01386390
[14] Dondajewski, M. and Szymański, J., On the distribution of vertex-degrees in a strata of a random recursive tree, Bull. Acad. Polon. Sci. Sér. Sci. Math. 30 (1982), 205–209. · Zbl 0485.05024
[15] Drmota, M., Janson, S. and Neininger, R., A functional limit theorem for the profile of search trees, Ann. Appl. Probab. 18 (2008), 288–333. · Zbl 1143.68019 · doi:10.1214/07-AAP457
[16] D’Souza, R. M., Krapivsky, P. L. and Moore, C., The power of choice in growing trees, Eur. Phys. J. B 59 (2007), 535–543. · Zbl 1189.05157 · doi:10.1140/epjb/e2007-00310-5
[17] Fuchs, M., Hwang, H.-K. and Neininger, R., Profiles of random trees: Limit theorems for random recursive trees and binary search trees, Algorithmica 46 (2006), 367–407. · Zbl 1106.68083 · doi:10.1007/s00453-006-0109-5
[18] Fuk, D. K. and Nagaev, S. V., Probability inequalities for sums of independent random variables, Teor. Veroyatnost. i Primenen. 16 (1971), 660–675 (Russian). English transl.: Theory Probab. Appl. 16 (1971), 643–660. · Zbl 0259.60024
[19] Gastwirth, J. L., A probability model of a pyramid scheme, Amer. Statist. 31 (1977), 79–82. · Zbl 0366.62128
[20] Glick, N., Breaking records and breaking boards, Amer. Math. Monthly 85 (1978), 2–26. · Zbl 0395.62040 · doi:10.2307/2978044
[21] Hwang, H.-K., Profiles of random trees: plane-oriented recursive trees (Extended Abstract), in 2005 International Conference on Analysis of Algorithms, pp. 193–200, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2005. · Zbl 1104.68086
[22] Hwang, H.-K., Profiles of random trees: plane-oriented recursive trees, Random Structures Algorithms 30 (2007), 380–413. · Zbl 1115.05083 · doi:10.1002/rsa.20139
[23] Mahmoud, H. M., Limiting distributions for path lengths in recursive trees, Probab. Engrg. Inform. Sci. 5 (1991), 53–59. · Zbl 1134.68361 · doi:10.1017/S0269964800001881
[24] Mahmoud, H. M., Distances in random plane-oriented recursive trees, J. Comput. Appl. Math. 41 (1992), 237–245. · Zbl 0768.05029 · doi:10.1016/0377-0427(92)90252-S
[25] Mahmoud, H. M., Evolution of Random Search Trees, Wiley, New York, 1992. · Zbl 0762.68033
[26] Mahmoud, H. M. and Smythe, R. T., On the distribution of leaves in rooted subtrees of recursive trees, Ann. Appl. Probab. 1 (1991), 406–418. · Zbl 0738.05034 · doi:10.1214/aoap/1177005874
[27] Meir, A. and Moon, J. W., On the altitude of nodes in random trees, Canad. J. Math. 30 (1978), 997–1015. · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[28] Na, H. S. and Rapoport, A., Distribution of nodes of a tree by degree, Math. Biosci. 6 (1970), 313–329. · Zbl 0193.53501 · doi:10.1016/0025-5564(70)90071-4
[29] Petrov, V. V., Limit Theorems of Probability Theory: Sequences of Independent Random Variables, Oxford University Press, Oxford, 1995. · Zbl 0826.60001
[30] Pittel, B., Note on the heights of random recursive trees and random m-ary search trees, Random Structures Algorithms 5 (1994), 337–347. · Zbl 0790.05077 · doi:10.1002/rsa.3240050207
[31] Prim, R. C., Shortest connection networks and some generalizations, Bell System Tech. J. 36 (1957), 1389–1401. · doi:10.1002/j.1538-7305.1957.tb01515.x
[32] Pyke, R., Spacings, J. Roy. Statist. Soc. Ser. B 27 (1965), 395–445.
[33] Rényi, A., Théorie des éléments saillants d’une suite d’observations, in Colloquium on Combinatorial Methods in Probability Theory, pp. 104–115, Mathematisk Institut, Aarhus Universitet, Aarhus, 1962.
[34] Rosenthal, H. P., On the subspaces of L p (p>2) spanned by sequences of independent random variables, Israel J. Math. 8 (1970), 273–303. · Zbl 0213.19303 · doi:10.1007/BF02771562
[35] Smythe, R. T. and Mahmoud, H. M., A survey of recursive trees, Teor. Ĭmovīr. Mat. Stat. 51 (1994), 1–29 (Ukrainian). English transl.: Theory Probab. Math. Statist. 51 (1995), 1–27 (1996).
[36] Sulzbach, H., A functional limit law for the profile of plane-oriented recursive trees, in Fifth Colloquium on Mathematics and Computer Science, pp. 339–350, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008. · Zbl 1355.05229
[37] Szymański, J., On a nonuniform random recursive tree, in Random Graphs ’85 (Poznań , 1985 ), North-Holland Math. Stud. 144, pp. 297–306, North-Holland, Amsterdam, 1987.
[38] Szymański, J., On the maximum degree and height of a random recursive tree, in Random Graphs ’87 (Poznań , 1987 ), pp. 313–324, Wiley, Chichester, 1990. · Zbl 0747.05083
[39] Timofeev, E. A., Random minimal trees, Teor. Veroyatnost. i Primenen. 29 (1984), 134–141 (Russian). English transl.: Theory Probab. Appl. 29 (1985), 134–141.
[40] Tsukiji, T. and Xhafa, F., On the depth of randomly generated circuits, in Algorithm–ESA ’96 , Lecture Notes in Comput. Sci. 1136, pp. 208–220, Springer, Berlin, 1996. · Zbl 0939.68044
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.