Atypical Decay Rates for Atypical Heights in Random Recursive Trees

Xinxin Chen, Heng Ma

We establish the large deviation probabilities for the height of random recursive trees, revealing polynomial upper-tail decay and stretched-exponential lower-tail decay. Remarkabl…