New answers tagged


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 ...

Top 50 recent answers are included