Theory and applications of the multivariate contraction method

点击翻译按钮获取中文摘要

The contraction method has been developed during the last 20 years to obtain weak convergence of sequences of random variables that satisfy recurrences on the level of distributions. Motivation and applications of this methodology are coming from the probabilistic analysis of fundamental recursive algorithms and the study of asymptotic properties of random tree models. Most of these applications are for univariate (real) sequences of random variables, e.g., when the complexity is captured by one real parameter. The theory of the contraction method has partially already been developed for higher dimensions and recently as well for functional limit theorem. In the multivariate case it has mainly been used to derive correlations between univariate parameters. However, even univariate quantities often do not have a recursive description by itself: Other quantities need to be used in the description which itself fulfill recursive equations. This leads to systems of recurrences, hence multivariate recurrences. The aim of this project is a systematically study of systems of recursive equations of distributions with emphasis on applications as well. In particular we want to clarify which probability metrics are suitable to solve types of recurrences appearing in applications. We intend applications in two directions: Firstly, the analysis of digital tree models (digital search tree, trie, PATRICIA-trie) under Markov-sources. These are data structures used in praxis, for which analysis, most often, a more idealized model assumption is made compared to the Markov source model. In this project fundamental parameters of these tree models are studied by a multivariate contraction method under a Markov-source towards asymptotic normality. This generalizes the well-studied case of independent, identically distributed symbols towards a much more realistic model for many applications (e.g. for text). A second field of applications constitute Polya urn models. We intend to establish a new approach via the contraction method. The dynamic of the number of balls of a certain color in the urn cannot be expressed recursively by itself, it depends as well on the other balls within the urn. Hence a recursive description leads to a multivariate recurrence. Regarding limit laws, the case of two colors has already been classified (by other methods). Results for more than two colors are comparatively rare. An approach via the contraction method seems flexible enough to cover cases of more than two colors as well.