Name
Abstract | ||
|---|---|---|
Total path length, or search cost, for a rooted tree is defined as the sum of all root-to-node distances. Let Tn be the total path length for a random recursive tree of order n. Mahmoud [10] showed that Wn := (Tn − E[Tn])/n converges almost surely and in L2 to a nondegenerate limiting random variable W. Here we give recurrence relations for the moments of Wn and of W and show that Wn converges to W in Lp for each 0 p W is not normal. We also show that the distribution of W is characterized among all distributions having zero mean and finite variance by the distributional identity***** Insert equation here *****where ℰ(x) := − x ln x − (1 minus; x) ln(1 − x) is the binary entropy function, U is a uniform (0, 1) random variable, W* and W have the same distribution, and U, W and W* are mutually independent. Finally, we derive an approximation for the distribution of W using a Pearson curve density estimator. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1017/S0963548399003855 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
random recursive trees,order n,pearson curve density estimator,rooted tree,random variable,random recursive tree,p w,n converges,wn converges,total path length,random variable w.,cumulant,recurrence relation,search cost | Discrete mathematics,Combinatorics,Random variable,Path length,Recurrence relation,Binary entropy function,Almost surely,Recursive tree,Mathematics,Independence (probability theory),Estimator | Journal |
Volume | Issue | ISSN |
8 | 4 | 0963-5483 |
Citations | PageRank | References |
18 | 1.41 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert P. Dobrow | 1 | 35 | 5.28 |
| James Allen Fill | 2 | 253 | 40.88 |