Hosam Mahmoud, Inria-Rocquencourt and The George Washington University

P\'olya urn models in random trees

We survey some P\'olya urn models with a focus on their connection to random trees. Some problems in random trees will be presented, where a P\'olya urn model detects a phase transition in the covariance structure of some tree statistics, and subsequently in their joint distribution. These trees are parameterized by an integer (usually the branching factor or node capacity). As the parameter increases beyond a certain threshold value, the asymptotic covariance matrix (as the tree size goes to infinity) changes from an asymptotically linear function to a super-linear function. This reflects itself in the joint distribution; up to a certain threshold value of the parameter the joint distribution is asymptotically multivariate normal, then for higher values of the parameter it becomes asymptotically non-normal.