SEARCH COST FOR A NEARLY OPTIMAL PATH IN A BINARY TREE

• 成果类型: Article
• 署名作者: Pemantle, Robin
• 署名单位: University of Pennsylvania
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/08-AAP585
• 发表日期: 2009
• 页码: 1273-1291
• 关键词: branching brownian-motion; random-walk; displacement; equation

摘要

Consider a binary tree, to the vertices of which are assigned independent Bernoulli random variables with mean p <= 1/2. How many of these Bernoullis one must look at in order to find a path of length n from the root which maximizes, up to a factor of 1 - epsilon, the sum of the Bernoullis along the path? In the case p = 1/2 (the critical value for nontriviality), it is shown to take Theta(epsilon(-1)n) steps. In the case p < 1/2, the number of steps is shown to be at least n exp(const epsilon(-1/2)). This last result matches the known upper bound from [Algorithmica 22 (1998) 388-412] in a certain family of subcases.