Fitness levels with tail bounds for the analysis of randomized search heuristics

We remove this restriction and supplement the fitness-level method with sharp tail bounds, including lower tails. As an exemplary application, we prove that the running time of randomized local search on OneMax is sharply concentrated around nlnn−0.1159...n.