Theory and applications of the multivariate contraction method

收缩法是近20年来发展起来的一种方法，用于研究在分布水平上满足递推关系的随机变量序列的弱收敛性。这种方法的动机和应用来自于基本递归算法的概率分析和随机树模型的渐近性质的研究。这些应用中的大多数是用于随机变量的单变量（真实的）序列，例如，当复杂度被一个真实的参数捕获时。收缩法的理论已经部分地发展为更高的维度，最近也为泛函极限定理。在多变量的情况下，它主要用于推导单变量参数之间的相关性。然而，即使是单变量量本身也往往没有递归描述：其他量需要在描述中使用，这些描述本身满足递归方程。这导致递归系统，因此是多元递归系统。本计画的目的是系统地研究递回分布方程组，并强调其应用。特别是，我们要澄清的概率度量是合适的解决类型的递归出现在应用程序中。我们打算在两个方向上应用：第一，分析马尔可夫源下的数字树模型（数字搜索树，trie，PATRICIA-trie）。这些是在实践中使用的数据结构，对于这些数据结构的分析，与马尔可夫源模型相比，通常会进行更理想化的模型假设。在这个项目中，这些树模型的基本参数研究的多元收缩方法下的马尔可夫源渐近正态。这概括了独立的，相同分布的符号的良好研究的情况下，对许多应用程序（例如，文本）更现实的模型。第二个应用领域是Polya骨灰盒模型。 我们打算通过收缩法建立一种新的方法。瓮中某种颜色的球的数量的动态不能由其本身递归地表示，它也取决于瓮中的其他球。因此，递归描述导致多元递归。关于极限定律，两种颜色的情况已经被分类（通过其他方法）。两种以上颜色的结果比较罕见。通过收缩方法的方法似乎足够灵活，以涵盖超过两种颜色的情况。

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.