A sharp minimum on the mean number of steps taken in adaptive walks

It was recently conjectured by H.A. Orr [2003. A minimum on the mean number of steps taken in adaptive walks. J. Theor. Biol. 220, 241-247] that from a random initial point on a random fitness landscape of alphabetic sequences with one-mutation adjacency, chosen from a larger class of landscapes, no adaptive algorithm can arrive at a local optimum in fewer than on average e-1 steps. Here, using an example in which the mean number of steps to a local optimum equals (A-1)/A, where A is the number of distinct “letters” in the “alphabet” from which sequences are constructed, it is shown that as originally stated, the conjecture does not hold. It is also demonstrated that (A-1)/A is a sharp minimum on the mean number of steps taken in adaptive walks on fitness landscapes of alphabetic sequences with one-mutation adjacency. As the example that achieves the new lower bound has properties that are not often considered as potential attributes for fitness landscapes-non-identically distributed fitnesses and negative fitness correlations for adjacent points-a weaker set of conditions characteristic of more commonly studied fitness landscapes is proposed under which the lower bound on the mean length of adaptive walks is conjectured to equal e-1.