Random recursive tree: Difference between revisions

Revision as of 16:50, 17 April 2020

Latest revision as of 03:53, 30 April 2025

(3 intermediate revisions by 3 users not shown)

Line 8:

==Properties==

With high probability, the longest path from the root to the leaf of an <math>n</math>-vertex random recursive tree has length <math>e\log n</math>.{{r|p}}

The maximum number of children of any vertex, i.e., degree, in the tree is, with high probability, <math>(1\pm o(1))\loglog_2 n</math>.{{r|gs}}

The [[expected value|expected]] distance of the <math>k</math>th vertex from the root is the <math>k</math>th [[harmonic number]], from which it follows by [[linearity of expectation]] that the sum of all root-to-vertex path lengths is, with high probability, <math>(1\pm o(1))n\log n</math>.{{r|df}}

The expected number of leaves of the tree is <math>n/2</math> with [[variance]] <math>n/12</math>, so with high probability the number of leaves is <math>(1\pm o(1))n/2</math>.{{r|z}}

Line 28:

| title = Total path length for random recursive trees

| volume = 8

| year = 1999}}</ref>| s2cid = 40574756

}}</ref>

<ref name=gs>{{citation

Line 40 ⟶ 41:

| title = Limit distribution for the maximum degree of a random recursive tree

| volume = 142

| year = 2002}}</ref>| doi-access = free

| bibcode = 2002JCoAM.142...61G

}}</ref>

<ref name=p>{{citation

Line 63 ⟶ 66:

| volume = 29

| year = 2015| doi-access = free

| url = https://projecteuclid.org/journals/brazilian-journal-of-probability-and-statistics/volume-29/issue-4/On-the-number-of-leaves-in-a-random-recursive-tree/10.1214/14-BJPS252.pdf

}}</ref>