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−ɛ, the sum of the Bernoullis along the path? In the case p=1/2 (the critical value for nontriviality), it is shown to take Θ(ɛ−1n) steps. In the case p<1/2, the number of steps is shown to be at least n⋅exp(const ɛ−1/2). This last result matches the known upper bound from [Algorithmica 22 (1998) 388–412] in a certain family of subcases.
@article{1248700617,
author = {Pemantle, Robin},
title = {Search cost for a nearly optimal path in a binary tree},
journal = {Ann. Appl. Probab.},
volume = {19},
number = {1},
year = {2009},
pages = { 1273-1291},
language = {en},
url = {http://dml.mathdoc.fr/item/1248700617}
}
Pemantle, Robin. Search cost for a nearly optimal path in a binary tree. Ann. Appl. Probab., Tome 19 (2009) no. 1, pp. 1273-1291. http://gdmltest.u-ga.fr/item/1248700617/