Search cost for a nearly optimal path in a binary tree

Abstract

Consider a binary tree, to the vertices of which are assigned independent Bernoulli random variables with mean $p\le 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\cdot \exp (\mathrm{const}{\epsilon }^{-1/2})$. This last result matches the known upper bound from [Algorithmica 22 (1998) 388--412] in a certain family of subcases.

Published in at http://dx.doi.org/10.1214/08-AAP585 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)