Search cost for a nearly optimal path in a binary tree

DOI10.1214/08-AAP585zbMath1176.68093arXivmath/0701741OpenAlexW3102782178MaRDI QIDQ835059

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

algorithmcomputational complexityminimal displacementoptimal pathbranching random walkmaximal 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)

Related Items (8)

Efficient approximation of branching random walk Gibbs measures ⋮ The algorithmic hardness threshold for continuous random energy models ⋮ The critical barrier for the survival of branching random walk with absorption ⋮ Asymptotics for the survival probability in a killed branching random walk ⋮ The genealogy of branching Brownian motion with absorption ⋮ Total progeny in killed branching random walk ⋮ Brunet-Derrida behavior of branching-selection particle systems on the line ⋮ Survival of branching random walks with absorption

Cites Work

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

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