PC Seminar with Cecilia Holmgren

Date
to
Location
Ångström Laboratory, 64119
Type
Seminar
Lecturer
Cecilia Holmgren
Organiser
Matematiska institutionen
Contact person
Sascha Troscheit

Cecilia Holmgren gives this seminar. Welcome!

Abstract: Split trees were introduced by Devroye (1998) as a novel approach for unifying many important random trees of logarithmic height. They are interesting not least because of their usefulness as models of sorting algorithms in computer science; for instance the well-known Quicksort algorithm (introduced by Hoare[1960]) can be depicted as a binary search tree (which is one example of a split tree). In this talk we study so-called fringe trees in split trees and in so-called fractional split trees (a novel model which we introduce where the components in the split vector does not need to sum up to 1). A fringe tree is a node together with all its descendants. We will study sums of functions of fringe trees, which are called additive functionals. These additive functionals are quite general and can describe e.g. the number of nodes, number of leaves and the number of fringe trees of a certain size.

In the talk I will discuss some of our results on these additive functionals in split trees and fractional split trees. In particular I will discuss our results on the expected value and weak law of large numbers for these additive functionals. Our methods are mainly based on renewal theory and analysis of Fourier series, which I will briefly discuss.

Joint work with Jasper Ischebeck and Svante Janson

This is a seminar in our seminar series on Probability and Combinatorics (PC).