Search cost for a nearly optimal path in a binary tree

DOI10.1214/08-AAP585MaRDI QIDQ835059zbMATH OpenOpenAlexFDO

Authors Robin Pemantle

Publication date 27 August 2009

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0701741

zbMATH Keywords

computational complexityalgorithmbranching random walkoptimal pathmaximal displacementminimal displacement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: Consider a binary tree, to the vertices of which are assigned independent Bernoulli random variables with mean $pleq1/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(epsilo{n}^{-1}n)$ steps. In the case $p<1/2$, the number of steps is shown to be at least $ncdotexp(operatornameconstepsilo{n}^{-1/2})$. This last result matches the known upper bound from [Algorithmica 22 (1998) 388--412] in a certain family of subcases.

Recommendations

• Searches on a Binary Tree with Random Edge-Weights
• scientific article; zbMATH DE number 1334602
• The estimated cost of a search tree on binary words
• Search for the maximum of a random walk
• Greedy Search on the Binary Tree with Random Edge-Weights

Cites work

• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 503438 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Metropolis-type optimization algorithm on the infinite tree
• Branching Brownian motion with absorption
• Chernoff's theorem in the branching random walk
• Further probabilistic analysis of the Fisher-Kolmogorov-Petrovskii-Piscounov equation: one sided travelling-waves
• Greedy Search on the Binary Tree with Random Edge-Weights
• Maximal displacement of branching brownian motion
• Minimal displacement of branching random walk
• Postulates for subadditive processes
• Searching for an optimal path in a tree with random costs
• Subadditive ergodic theory
• Supercritical Branching Brownian Motion and K-P-P Equation In the Critical Speed-Area
• Survival probabilities for branching Brownian motion with absorption
• The first birth problem for an age-dependent branching process

Cited in

(11)

• Brunet-Derrida behavior of branching-selection particle systems on the line
• Cost-error relationships in A* tree-searching
• Asymptotics for the survival probability in a killed branching random walk
• The genealogy of branching Brownian motion with absorption
• The critical barrier for the survival of branching random walk with absorption
• Total progeny in killed branching random walk
• Survival of branching random walks with absorption
• Efficient approximation of branching random walk Gibbs measures
• The node visit cost of brother trees
• The cost of offline binary search tree algorithms and the complexity of the request sequence
• The algorithmic hardness threshold for continuous random energy models

This page was built for publication: Search cost for a nearly optimal path in a binary tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q835059)