Google Answers Logo
View Question
 
Q: Why describe algorithms as "Las Vegas" and "Monte Carlo"? ( Answered 5 out of 5 stars,   1 Comment )
Question  
Subject: Why describe algorithms as "Las Vegas" and "Monte Carlo"?
Category: Computers > Algorithms
Asked by: purpleanemone-ga
List Price: $4.50
Posted: 19 Jul 2003 16:17 PDT
Expires: 18 Aug 2003 16:17 PDT
Question ID: 232876
In computer science, the terms "Las Vegas" and "Monte Carlo" are often
used to describe algorithms.  For definitions, see:
http://www.nist.gov/dads/HTML/monteCarlo.html
http://www.nist.gov/dads/HTML/lasVegas.html

I would like to know the origin of this distinction.  That is,
1) Who first started using these two terms?  (And when, if possible)
2) Did that person give a reason, and what was it?  

I can guess the connection between the cities and algorithm types, but I
want to have some confidence in the answer, which is why I'd like to
know who started using the term and when.
Answer  
Subject: Re: Why describe algorithms as "Las Vegas" and "Monte Carlo"?
Answered By: pinkfreud-ga on 19 Jul 2003 18:17 PDT
Rated:5 out of 5 stars
 
Hello again, purpleanemone. As soon as I saw your screen name I heard
the tune of "Barrett's Privateers" in my head.

"Monte Carlo algorithm" was a coinage that arose in the late 1940s
among mathematicians Nicholas Metropolis, Stanislaw Ulam, and John von
Neumann as they worked on the Manhattan Project:

"The Metropolis Monte Carlo was developed in present form by
Metropolis, Ulam, Neumann during their work on Manhattan project
(study of neutron diffusion). The name 'Monte Carlo' was first used in
a paper published by Metropolis and Ulam in 1949 and is attributed by
some sources to the fact that S. Ulam's uncle went each year to Monte
Carlo for gambling. Others attribute the name to S. Ulam's own
interest in poker."

University of Virginia
http://www.people.virginia.edu/~lz2n/mse524/notes-2003/MC.pdf

"The name 'Monte Carlo' was coined by Metropolis (inspired by Ulam's
interest in poker) during the Manhattan Project of World War II,
because of the similarity of statistical simulation to games of
chance, and because the capital of Monaco was a center for gambling
and similar pursuits."

Computational Science Education Project
http://csep1.phy.ornl.gov/mc/node1.html

"There are two kinds of randomized algorithms:

Monte Carlo: A Monte Carlo algorithm runs for a fixed number of steps
for each input and produces an answer that is correct with a bounded
probability.

Las Vegas: A Las Vegas algorithm always produces the correct answer,
but its runtime for each input is a random variable whose expectation
is bounded."

Cached file from the Chinese University of Hong Kong
http://216.239.53.104/search?q=cache:Gk-JzKGcUMMJ:www.cse.cuhk.edu.hk/~cslui/RANDOMIZED/random_02.ppt

The term "Las Vegas algorithm" is attributed to mathematician László
Babai:

"Stochastic local search algorithms are special cases of Las Vegas
algorithms. According to this definition, Las Vegas algorithms are
always correct, but they are not necessarily complete, i.e., even if a
given problem instance has a solution, a Las Vegas algorithm is
generally not guaranteed to find it... The term was originally coined
by Laszlo Babai in 1979."

Cached file from the University of British Columbia
http://216.239.51.104/search?q=cache:5C-oE-IVtHQJ:www.cs.ubc.ca/spider/hoos/Publ/aaai99-pac.ps

So it appears that 'Las Vegas algorithm' was coined simply as a
parallel term in contrast to the much older 'Monte Carlo algorithm'.
Las Vegas is, of course, one of the world's major gambling centers,
along with Monte Carlo. I have found no evidence that gaming styles in
these two cities have any correlation with the differences between
these types of algorithms. Certainly it cannot be said that gambling
in Las Vegas is always correct. ;-)

There is a third kind of algorithm named after a famous gambling city,
the Atlantic City algorithm:

"Two common classes of probabilistic algorithms are Monte Carlo and
Las Vegas methods. Monte Carlo algorithms are always fast, but only
probably correct. On the other hand, Las Vegas algorithms (Babai,
1979) are always correct, but only probably fast. A third class of
algorithms, bounded probabilistic polynomial time (BPP) algorithms
(Boppana and Hirschfeld, 1989), are probably correct and probably
fast."

North Carolina State University
http://www4.ncsu.edu/~kaltofen/ssg/Erich/Theses/turner.pdf

"We note that RP algorithms and BPP algorithms are sometimes
respectively referred to as Monte-Carlo and Atlantic City algorithms."

Cached file from Texas A&M University
http://216.239.51.104/search?q=cache:t5yogkh_qHEJ:www.math.tamu.edu/~rojas/dzh.ps.gz

"An Atlantic City algorithm for primality testing is one which runs in
polynomial-time and is correct 3/4 of the time."

City College of New York
http://www-cs.engr.ccny.cuny.edu/~csmma/cs5726/probset

I have not been able to find the origins of the term "Atlantic City
algorithm" for a BPP algorithm. It appears to be the most recent of
these three terms.

Search terms used:

"monte carlo algorithm(s)"
"las vegas algorithm(s)"
"atlantic city algorithm(s)"
"stanislaw ulam"
"laszlo babai"

I hope this information is useful. If anything is unclear, or if a
link does not function, please request clarification; I'll be glad to
offer further assistance before you rate my answer.

Best wishes,
pinkfreud

Request for Answer Clarification by purpleanemone-ga on 27 Jul 2003 10:11 PDT
Wow!  I was amazed at how quickly you answered.  (And really amused
that you were also the same person who answerd the "Barrett's
Privateers"--really, I don't send that many questions to google
answers!  :) )

I do have a clarification question -- can you find the passage where
László Babai introduces the term?   Or an electronic copy of the
relevant paper?

"I have found no evidence that gaming styles in
these two cities have any correlation with the differences between
these types of algorithms. Certainly it cannot be said that gambling
in Las Vegas is always correct. ;-)"

The hypothesis (reasoning backward from the data--an always suspect
technique) proposed by a friend of mine was that you went to Monte
Carlo for a fixed time, and left with whatever money you had at that
time.  On the other hand, you went to Las Vegas, and played until you
were broke.  (So you knew the answer when you left, but not how long
you stayed.)

Clarification of Answer by pinkfreud-ga on 27 Jul 2003 12:14 PDT
I have not been able to locate an online text of the paper in which
Dr. Babai introduced the term "Las Vegas algorithm." I have, I
believe, found the name of the paper and its origin of publication:

"The complexity class R contains all problems solvable in Las Vegas
polynomial time. The term Las Vegas was coined by L. Babai (1979).
Clearly, as Gene Cooperman has pointed out to me, a BPP method can be
converted to a Monte Carlo method by returning garbage when the random
walk consumes too much time. It is unknown if BPP = R, or if R = P,
the class of problems solvable deterministically in polynomial time.
Many theorists ....

Babai, L. (1979). Monte-Carlo algorithms in graph isomorphism testing.
Rapport de recherches 79-10, Univ. de Montr'eal, D'ep. de
math'ematiques et de statistique."

http://citeseer.nj.nec.com/context/54398/0

"L. Babai: Monte Carlo algorithms in graph isomorphism testing,
Université de Montréal Tech. Rep. DMS 79-10, 1979 (pp. 42)"

http://www.cs.uchicago.edu/files/bibliographies/laci.html

Here are links to Dr. Babai's homepages, business and personal:

http://www.cs.uchicago.edu/people/laci

http://people.cs.uchicago.edu/~laci/

I've sent an email to Dr. Babai asking his assistance in finding the
paper in question. If I receive useful information in response, I'll
post it here for you.

~pinkfreud
purpleanemone-ga rated this answer:5 out of 5 stars and gave an additional tip of: $5.00
Very fast answer.

Comments  
Subject: Re: Why describe algorithms as "Las Vegas" and "Monte Carlo"?
From: pinkfreud-ga on 29 Jul 2003 06:59 PDT
 
Many thanks for the five-star rating and the nice tip!

I haven't heard back from Dr. Babai yet, but if I receive anything
useful from him, I'll let you know.

~pinkfreud

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy