Statistics Seminar, "Inversions in Split Trees", Xing Shi Cai, Department of Mathematics, Uppsala University
Kontakt: dragi [at] maths [dot] lth [dot] se
Spara händelsen till din kalender
We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees, which include binary search trees, we show that X_n converges to the unique solution of a distributional equation.