17 Monte Carlo MethodsΒΆ

Randomized algorithms, roughly 2 categories

  • Las Vagas algorithms

    • always return precisely correct answer or report failed
    • consume random amount of resources: time or memory
  • Monte Carlo algorithms

    • return answers with a random amount of error
    • error amount can typically be reduced by expending more resources
    • fixed computational budget, a Monte Carlo algorithm can provide an approximate answer