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/notes2003/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:GkJzKGcUMMJ: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:5CoEIVtHQJ:www.cs.ubc.ca/spider/hoos/Publ/aaai99pac.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 MonteCarlo 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
polynomialtime and is correct 3/4 of the time."
City College of New York
http://wwwcs.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
purpleanemonega
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 dataan 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
pinkfreudga
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). MonteCarlo algorithms in graph isomorphism testing.
Rapport de recherches 7910, 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 7910, 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
