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.