Random recursive tree: Difference between revisions

Revision as of 16:50, 17 April 2020

Revision as of 18:40, 7 September 2020

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}}