We give a proof for the Additive Drift Theorem, originally published (in a more restricted version) by He and Yao [1]}, [2]}. We start by reproving the original theorem (which requires a bounded search space) but in a simpler, more elegant and educational manner. We then greatly extend this result by generalizing it to processes with a bounded step width. Finally, we lift also this restriction.
