4 ms·
Las Vegas = Always Correct, Probably Fast Monte Carlo = Probably Correct, Always Fast
by 1001101 10y ago
Las Vegas = Always Correct, Probably Fast
Monte Carlo = Probably Correct, Always Fast
- hyperbovine 10y agoSince when is Monte Carlo fast :-)
- snovv_crash 10y agoMore often than not, it is faster than figuring out the exact solution, if an exact solution exists. Things like having a piecewise distribution somewhere in your problem make Monte Carlo several orders of magnitude easier to implement.
- hyperbovine 10y agoThe depends a lot of the dimension of the space you're trying to integrate over, and in any case, (vanilla) Monte Carlo is trivial to implement. I was more poking fun at the very different way theorists and practitioners view classes certain algorithms. "Deterministic running time" is not a particularly strong guarantee, in practice.
- thomasahle 10y agoI think people would probably call an algorithm that is "Probably Correct, Probably Fast" Monte Carlo as well.
- funkaster 10y agoAdding speed to the classification is misleading. It might be better to state: - Las Vegas: Correct, Time unbounded - Monte Carlo: Not always correct, Time bounded edit: format
- kccqzy 10y agoAs pointed out already, a Las Vegas algorithm might have bounded but non-deterministic time.