Math.Koll. am 17.01.07/Prof. Drmota

[Institut für Mathematik]

Mathematisches Kolloquium

EINLADUNG

zu einem

VORTRAG

von

Prof. Michael Drmota (Technische Universitaet Wien)

mit dem Thema:

''Random Trees and Stochastic Processes of Random Entire Functions''
Michael Drmota (joint work with Ralph Neininger and Svante Janson)

Abstract:
Random trees are a well studied object in Theoretical Computer Science since
they model several important recursive algorithms on data structures, for
example, Quicksort and its variants. The analysis is also interesting from a
mathematical point of view. It usually requires a combination of
combinatorial, analytic and stochastic methods.

In this talk we consider the profile  X_{n,k}  (the number of nodes at level
k  in a tree of size  n) of random search trees including binary search
trees and m-ary search trees. Our main result is a functional limit theorem
of the normalized profile X_{n,k}/E X_{n,k}  for  k = [\alpha \log n] in a
certain range of  \alpha.

A central feature of the proof is the use of the contraction method to prove
convergence in distribution of certain random analytic functions in a
complex domain. This is based on a general theorem on the contraction method
for random variables in an infinite dimensional Hilbert space. As part of
the proof, one has to show that the Zolotarev metric is complete for a
Hilbert space.

Zeit: Mittwoch, 17. Januar 2007, 15.45 Uhr (Kaffeejause), anschlieszend
16.15 Uhr Vortrag

Ort: Fakultät für Mathematik der Universität Wien, Nordbergstr. 15,
Seminarraum C 2.09

Harald Rindler, Christian Krattenthaler