From trees to seeds: On the inference of the seed from large trees in the uniform attachment model
Sébastien Bubecka b c d, Ronen Eldanb e, Elchanan Mosself g, Miklós Zoltán Ráczf h
- aDepartment of Operations Research and Financial Engineering , Princeton University , Sherrerd Hall , Charlton Street , Princeton , NJ 08544 , USA
- bTheory Group , Microsoft Research , One Microsoft Way , Redmond , WA 98052 , USA
- cMicrosoft USA
- dPrinceton University
- eMicrosoft , USA
- fUniversity of California at Berkeley
- gUniversity of Pennsylvania
- hDepartment of Statistics , University of California , Berkeley , CA 94720 , USA
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
We study the influence of the seed in random trees grown according to the uniform attachment model, also known as uniform random recursive trees. We show that different seeds lead to different distributions of limiting trees from a total variation point of view. To do this, we construct statistics that measure, in a certain well-defined sense, global “balancedness” properties of such trees. Our paper follows recent results on the same question for the preferential attachment model.
TL;DRIt is shown that different seeds lead to different distributions of limiting trees from a total variation point of view, and statistics are constructed that measure, in a certain well-defined sense, global "balancedness" properties of such trees. (Semantic Scholar)