POISSON-DIRICHLET BRANCHING RANDOM WALKS

• 成果类型: Article
• 署名作者: Addario-Berry, Louigi; Ford, Kevin
• 署名单位: McGill University; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/12-AAP840
• 发表日期: 2013
• 页码: 283-307
• 关键词: ary search-trees; minimal position; WEAK-CONVERGENCE; heights

摘要

We determine, to within 0(1), the expected minimal position at level n in certain branching random walks. The walks under consideration have displacement vector (nu 1, nu 2, ... ), where each vi is the sum of j independent Exponential(1) random variables and the different vi need not be independent. In particular, our analysis applies to the Poisson-Dirichlet branching random walk and to the Poisson-weighted infinite tree. As a corollary, we also determine the expected height of a random recursive tree to within O(1).