Probability and statistics seminar: Central limit theorems for additive functionals and fringe trees in tries

  • Date: –11:15
  • Location: Ångströmlaboratoriet, Lägerhyddsvägen 1 64119
  • Lecturer: Svante Janson
  • Organiser: Matematiska institutionen
  • Contact person: Xing Shi Cai
  • Seminarium

Abstract: We prove central limit theorems for additive functionals of tries, undersuitable conditions.  Several methods are used and combined; these include: Poissonization (introducing more independence); approximation with a sum of independent terms (coming from disjoint subtrees); dePoissonization using a conditional limit theorem; moment asymptotics by renewal theory.

 

As examples, we consider some properties of fringe trees.