Las Vegas, or Monte Carlo?
Posted by danielmeyer on August 4, 2008
When you need to provide a time estimate for a research task that will involve technologies your organization has never before explored, you’re going to use some heuristics, right? It seems about impossible to give an estimate that has much hope of being accurate, but you can’t just not give any answer, either, can you?
This dilemma reminds me of two different classes of probabilistic algorithms I learned about in algorithms class: Las Vegas algorithms and Monte Carlo algorithms. In sections 10.6 and 10.7 of the book Fundamentals of Algorithmics by Gilles Brassard and Paul Bratley I learned that:
- Monte Carlo algorithms always give you an answer — it just may not always be the right answer.
- Las Vegas algorithms always give you the right answer when they give you an answer — but they don’t always give you an answer*.
Do you see some similarities to the estimation dilemma? :) The similarities are really only on the surface though:
| Quality | Monte Carlo Algorithm | Task Estimation |
|---|---|---|
| Always gives an answer? | Yes | Yes |
| Answer given always correct? | No | No |
| Probability of answer being correct | Quite high | Quite low |
How about the Las Vegas algorithms vs. “I can’t give an estimate I know is wrong” task estimation?
| Quality | Las Vegas Algorithm | Task Estimation |
|---|---|---|
| Always gives an answer? | No* | No |
| Answer given always correct? | Yes | No |
| Effect of asking again after no answer | Quite likely to get correct answer | No more likely to get any answer |
*Some Las Vegas algorithms will keep at it until they get a correct answer; others just give up, but they might give you an answer if you simply ask again.
