Mathematics – Probability
Scientific paper
2005-09-21
Mathematics
Probability
23 pages
Scientific paper
Consider a random recusive tree with n vertices. We show that the number of vertices with even depth is asymptotically normal as n tends to infinty. The same is true for the number of vertices of depth divisible by m for m=3, 4 or 5; in all four cases the variance grows linearly. On the other hand, for m at least 7, the number is not asymptotically normal, and the variance grows faster than linear in n. The case m=6 is intermediate: the number is asymptotically normal but the variance is of order n log n. This is a simple and striking example of a type of phase transition that has been observed by other authors in several cases. We prove, and perhaps explain, this non-intuitive behavious using a translation to a generalized Polya urn. Similar results hold for a random binary search tree; now the number of vertices of depth divisible by m is asymptotically normal for m at most 8 but not for m at least 9, and the variance grows linearly in the first case both faster in the second. (There is no intermediate case.) In contrast, we show that for conditioned Galton-Watson trees, including random labelled trees and random binary trees, there is no such phase transition: the number is asymptotically normal for every m.
No associations
LandOfFree
Congruence properties of depths in some random trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Congruence properties of depths in some random trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Congruence properties of depths in some random trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-486492