Is any randomized Algorithm a probability distribution over the set of deterministic Algorithms?

Question

If there is a finite set of Instances of size n and the set of (reasonable) deterministic algorithms is finit.

Can any randomized Algorithm be seen as a probability distribution over the set of deterministic Algorithms? And if yes, why?

Answer 1

You can think of a randomized algorithm as having access to a random variable $\mathbf{r}$, which informs its random decisions. For any fixing of $\mathbf{r}$, you get a deterministic algorithm, and in this way you can view the original randomized algorithm as a distribution over deterministic algorithms.

As an example, consider the randomized algorithm for solving MAX-3SAT. The algorithm chooses a random assignment. You can think of this assignment as specified by $\mathbf{r}$. Any particular assignment corresponds to a deterministic algorithm, and the original randomized algorithm is just the uniform distribution over these deterministic algorithms.