Probability Spaces for Random Algorithms

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.