Brigitte Chauvin, Professor, University of Versailles
"Random trees and Probability"
In this mini course, three models are studied: binary search trees (BST), Pólya urns
and m-ary search trees (MST). For all of them, a same plan runs along the following outline:
Thanks to the branching property, the asymptotics of this continuous time branching
process is more accessible than in discrete time, where the branching property
does not hold.
- A discrete Markovian stochastic process is related to a random tree structure
which comes from analysis of algorithms.
The recursive nature of the problem then gives rise to discrete time martingales.
The process is embedded into continuous time, giving rise to a one
type or a multitype branching process. The associated continuous time martingales
are connected to the previous discrete time martingales.
In the three cases, BST, P\'olya urns, and MST, the limit of the (rescaled) martingale
has a non classic distribution.
We present some expected properties of these limit distribution (density, infinite
divisibility, ...) together with more exciting properties (divergent moment series,
fixed point equation, ...).
Keywords: branching process, branching property, martingale, analysis
of algorithms, Pólya urn, binary search tree.