5 ms·

It's not just an Americanization. "Las Vegas" and "Monte Carlo" are technical terms with specific, different meanings. A Monte Carlo algorithm runs in a determ

It's not just an Americanization. "Las Vegas" and "Monte Carlo" are technical terms with specific, different meanings. A Monte Carlo algorithm runs in a deterministic amount of time, and computes a probabilistic (approximate) result. For example: Monte Carlo numerical integration, or Miller-Rabin primality testing. A Las Vegas algorithm takes a non-deterministic amount of time, but is guaranteed to return a correct result. For example: quicksort with a random choice of pivot.

tgb 10y ago
I don't see why quick sort with a random pivot takes a non deterministic amount of time.
- rdtsc 10y ago
  > I don't see why quick sort with a random pivot takes a non deterministic amount of time. Because it might sort faster or slower depending on how the pivot gets picked. But you'd get the sorted list in the end. A Monte Carlo solution might run for 5 seconds but you might get a partially sorted list only.
  - tgb 10y ago
    Ah I see thanks. I was thinking the claim was that it might take an unbounded amount of time.
rawnlq 10y ago
There's a popular interview question that has a las vegas algorithm as a solution. It's a more illustrative example since it takes an unbounded amount of time. Let's say you want to simulate a 1/3-biased coin with a fair coin. One solution is to flip the fair coin twice, then output heads if you get HH, output tails if you get TH or HT, otherwise retry (if TT). Then this process is guaranteed to always output heads with 1/3 probability and tails with 2/3 probability if it ever ends. The runtime complexity is unbounded since you can keep getting TT forever but the expected runtime is constant.
- curuinor 10y ago
  Similary to St. Petersburg paradox (https://en.wikipedia.org/wiki/St._Petersburg_paradox https://en.wikipedia.org/wiki/St._Petersburg_paradox). The expectation is a stranger and more dangerous beast than would be easily expected.

tgb 10y ago

I don't see why quick sort with a random pivot takes a non deterministic amount of time.

rdtsc 10y ago
> I don't see why quick sort with a random pivot takes a non deterministic amount of time. Because it might sort faster or slower depending on how the pivot gets picked. But you'd get the sorted list in the end. A Monte Carlo solution might run for 5 seconds but you might get a partially sorted list only.
- tgb 10y ago
  Ah I see thanks. I was thinking the claim was that it might take an unbounded amount of time.

rawnlq 10y ago

There's a popular interview question that has a las vegas algorithm as a solution. It's a more illustrative example since it takes an unbounded amount of time. Let's say you want to simulate a 1/3-biased coin with a fair coin. One solution is to flip the fair coin twice, then output heads if you get HH, output tails if you get TH or HT, otherwise retry (if TT). Then this process is guaranteed to always output heads with 1/3 probability and tails with 2/3 probability if it ever ends. The runtime complexity is unbounded since you can keep getting TT forever but the expected runtime is constant.

curuinor 10y ago
Similary to St. Petersburg paradox (https://en.wikipedia.org/wiki/St._Petersburg_paradox https://en.wikipedia.org/wiki/St._Petersburg_paradox). The expectation is a stranger and more dangerous beast than would be easily expected.