Greedy Search on the Binary Tree with Random Edge-Weights

Source abstract

There is a simple greedy algorithm for seeking large values of a function f defined on the vertices of the binary tree. Modeling f as a random function whose increments along edges are i.i.d., we show that (under a natural assumption) the values found by the greedy algorithm grow linearly in time, with rate specified in terms of a fixed-point identity for distributions.