Probability Spaces for Random Algorithms

Abstract

Standard analyses of expected runtimes for randomized algorithms typically bypass the explicit construction of an underlying probability space. In this paper, we provide a formal, yet intuitive tree-based definition of the probability space for the execution paths of such algorithms. Using this model, we derive the recurrence equation for the expected runtime.