Congruence properties of depths in some random trees
| dc.creator | Janson, Svante | |
| dc.date | 2005-09-21 | |
| dc.date.accessioned | 2026-07-07T06:18:32Z | |
| dc.date.available | 2026-07-07T06:18:32Z | |
| dc.description | 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. | |
| dc.description | 23 pages | |
| dc.identifier | https://arxiv.org/abs/math/0509471 | |
| dc.identifier | http://arxiv.org/abs/math/0509471 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/94765 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 60C05; 05C05 | |
| dc.title | Congruence properties of depths in some random trees | |
| dc.type | text |