• 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:
  1. 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.
  2. 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.
  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.
  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.