A rigorous proof of a fundamental theorem in the drift analysis of evolutionary algorithms

A fundamental theorem in the drift analysis of EAs was initially presented in Jun He and Xin Yao´s paper(Artificial Intelligence 127(1) (2001) 57-85). However, the theorem remained defective in spite of its successful applications in some specific cases. This paper points out those defects, then suggests some modifications on the theorem and introduces a new and rigorous proof. This work is expected to contribute to the solid foundation of runtime analysis of Evolutionary Algorithms.