Séminaire du 18 octobre 2010, 10h30: Henning Sulzbach, Universität Frankfurt.
On the contraction method in function spaces and the partial
match problem
The techniques of the contraction method for random recursive
structures that have mainly been used in the area of probabilistic
analysis of algorithms are generalized to random quantities taking
values in the space of continuous or cadlag functions on the unit
interval with uniform topology. We use probability metrics of the
Zolotarev type introduced in the late 1970s and provide sufficient
conditions under which convergence in these metrics implies weak
convergence.
After a short introduction to the contraction method we illustrate
these ideas with the complexity of the partial match query in a random
two-dimensional quad-tree. We can give new asymptotic results the
finite dimensional distributions and on the process level.
Virginie Collette
Last modified: Mon Sep 20 14:24:06 CEST 2010