权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Theory and applications of the multivariate contraction method

多元收缩法的理论与应用

基本信息

批准号：
230688343
负责人：
Professor Dr. Ralph Neininger
金额：
--
依托单位：
Fachbereich 12 - Informatik und Mathematik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2012
资助国家：
德国
起止时间：
2011-12-31 至 2016-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/230688343?language=en
关键词：
Theory applications 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.

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