Las Vegas, or Monte Carlo?

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:

Task Estimation vs. a Monte Carlo Algorithm
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?

Task Estimation vs. a Las Vegas Algorithm
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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s