<p>The <a href="http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm">Metropolis–Hastings algorithm</a> was published in 1953 and dates back earlier to the Manhattan project, long before Rabin. Like many of the early randomized methods given in other answers, it is a Monte Carlo algorithm.</p>

<p>Is it possible that the claim on the Wikipedia page is a garbled form of the claim that Rabin's was the first <a href="http://en.wikipedia.org/wiki/Las_Vegas_algorithm">Las Vegas algorithm</a>?</p>

CC BY-SA 3.0
2012-09-12T00:18:13.333Z
2012-09-12T00:18:13.333Z
David Eppstein
<p><a href="http://en.wikipedia.org/wiki/Buffon%27s_needle">Buffons needle algorithm</a> for estimating $\pi$, basically a <a href="http://en.wikipedia.org/wiki/Monte_carlo_method">Monte Carlo method</a>, dates to publication in 1777. note that Monte Carlo methods date to the 1940s with the US "Manhattan" atom bomb project &amp; were coinvented by Ulam, Von Neumann, and Metropolis.</p>

CC BY-SA 3.0
2012-09-11T21:33:14.403Z
Actually this is related to [a question that I asked](http://cstheory.stackexchange.com/questions/11898/who-first-proposed-using-x2y2-1-monte-carlo-algorithm-to-calculate-pi). Nobody knows exactly who devised the algorithm that many people take to be Buffon's needle nowadays.
Jérémie
CC BY-SA 3.0
2012-09-15T16:28:07.140Z
stated more exactly— there is a clearcut Buffon needle algorithm which involves dropping needles on stripes, and an apparently much different "random point vs circle" algorithm as you mention in that question which some people seem to incorrectly attribute to Buffon, with different, more modern, but uncertain origins.
vzn
CC BY-SA 3.0
2012-09-11T20:33:07.890Z
2012-09-11T20:33:07.890Z
vzn
<p>The <a href="http://en.wikipedia.org/wiki/Normal_distribution">Gaussian normal curve/distribution</a> of statistics can be "computed" by many very simple physical processes. One of the simplest is a <a href="http://en.wikipedia.org/wiki/Bean_machine">board with a pin array</a> in a triangular grid  (also known as a <a href="http://en.wikipedia.org/wiki/Francis_Galton">"Galton box"</a> dating to the 1800s) where pins are offset 1/2 square distance on alternating rows. Dropping balls repeatedly from the same position, the balls randomly displace left or right with probability 0.5. The cumulative distribution recorded at bottom positions yields the Gaussian curve/normal.</p>

CC BY-SA 3.0
2012-09-12T14:40:21.133Z
+1 just because I’m currently designing a logo for our statistics research group and the Galton Box was our first idea (but turns out to be too complex for a logo).
Konrad Rudolph
CC BY-SA 3.0
2012-09-11T20:59:58.640Z
2012-09-12T14:30:35.153Z
2012-09-12T14:30:35.153Z
vzn
<p>In my opinion, <a href="http://en.wikipedia.org/wiki/DNA">natural evolution</a> is a good and rather old probabilistic algorithm :-)</p>

CC BY-SA 3.0
2012-09-12T14:41:40.113Z
+1 although the *description* of the process as probabilistic us much more recent. ;-)
Konrad Rudolph
CC BY-SA 3.0
2012-09-13T15:33:12.557Z
"Algorithm" suggests that there is a problem it is trying to solve; but it isn't. It isn't even "trying" to make animals which are better at surviving; creating animals which are adapted to its environment is just a byproduct (one which is not always achieved, as extinction and mass-extinction events make evident). In this respect, evolution is no more an algorithm than gravity is; it's just this thing which sort of happens.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T15:44:13.400Z
MDB is dead on! evolution is a [genetic algorithm](http://cstheory.stackexchange.com/questions/427/what-are-some-real-world-applications-for-genetic-algorithms) that selects for _evolutionary fitness_ and science is still catching up with all the implications of this.... ie its an active area of research. it hasnt been pointed out much or widely appreciated, but the phenomenal success of GAs in CS is actually strong mathematical/scientific evidence of the reality of biological evolution theory. however, concede it is definitely different than other "algorithms" in some key ways.
vzn
CC BY-SA 3.0
2012-09-13T15:56:09.343Z
@vzn: a "genetic algorithm", first of all, selects for a fitness function which we impose for a specific purpose. *We* use evolution as a tool to do something in that case. But that doesn't mean that biological evolution is an algorithm to do anything. Using the gravity analogy again, is there a meaningful sense in which all waterfalls are algorithms, just because we sometimes use waterfalls to generate electricity?
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T16:06:42.137Z
@NieldeBeaudrap: *"Algorithm" suggests that there is a problem it is trying to solve* ... IMO natural evolution is trying to solve the (hard) problem of "species survival" in the natural environment. One can say that even a (mechanical) Turing Machine doing his computation, isn't trying to solve a problem following an "algorithm", but it is simply following world's rules :-)
Marzio De Biasi
CC BY-SA 3.0
2012-09-13T16:08:49.910Z
@MarzioDeBiasi: however, we typically reserve 'algorithm' for something which is **(a)** planned, that is adopted intentionally; not to mention **(b)** something which provably terminates with success under certain conditions. The consensus is that (a) is false, while for (b) the only time at which the process stops *is precisely* when it fails (which as $t \to \infty$ it will do, with certainty). I'm taking issue with the notion that it is trying to do anything at all having any end-point; and given that it doesn't even always succeed in muddling on as best it can, it seems poor teminology.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T16:14:55.880Z
@MarzioDeBiasi: as for Turing Machines: the essential distinction is that we use the Turing machine as a tool. We impose intention on it. When we speak of "an algorithm to to X", it means that it is something which we may choose in order to accomplish X, and within certain constraints also of our choosing. If Turing machines were strange little animals whose tapes fluttered in the wind, I wouldn't consider them algorithms either. Choosing a particular one of them to solve 2-SAT would be reasonable to describe as an algorithm, however.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T22:15:56.373Z
NdB, am not expecting any satisfactory resolution to your numerous qualms but will throw this out there. all life is just a intermediate process of the computation of DNA. DNA copies and modifies itself in a finite process. DNA copying is therefore an algorithm. evolution supplies random mutations to this copying algorithm, some of which _increase its efficiency and efficacy_. you seem to suffer from the [anthropocentric fallacy](http://en.wikipedia.org/wiki/Anthropocentrism) in asserting that all algorithms must be programmed by humans. many animals have algorithmic-like behavior patterns....
vzn
CC BY-SA 3.0
2012-09-15T16:11:39.877Z
furthermore, many _cellular processes_ not merely associated with DNA have extremely algorithmic-like properties. think also _viruses_ which implement _probabilistic algorithms_ for _infection/transmission_. and consider the massive yet still-embryonic field of [DNA computing](http://en.wikipedia.org/wiki/DNA_computing). its clear the modern conception of algorithms is undergoing a near [kuhnian-shift](http://en.wikipedia.org/wiki/Paradigm_shift) to find them almost ubiquitous in nature. dare I mention [wolfram](http://en.wikipedia.org/wiki/A_New_Kind_of_Science)?
vzn
CC BY-SA 3.0
2012-09-15T18:08:44.023Z
@vzn: I merely assert that "an algorithm" should entail well-defined parameters of probability of success, not to mention that *there should be an agent which carries it out*. The only 'agent' which could be said to carry out "evolution" would be an entire ecosystem. What should we say that the ecosystem is "trying" to achieve? I would as readily say that you are *anthropomorphising* nature. I only demand that "applying an algorithm" entail some amount of goal-oriented intentionality, applied by humans or no. In what sense can a process without a goal represent an "algorithm"?
Niel de Beaudrap
CC BY-SA 3.0
2012-09-11T23:55:36.357Z
2012-09-12T00:16:00.950Z
2012-09-12T00:16:00.950Z
Marzio De Biasi
<p>There is a paper about <a href="https://cs.uwaterloo.ca/~shallit/Papers/ch.pdf" rel="noreferrer">randomized algorithms in 'primitive' cultures</a>.</p>

<p>Using oracles (e.g. chicken bones, stones) to decide on where to hunt can be seen as a randomized algorithm. One can argue that randomizing the hunting grounds prevents game adaption and overhunting. </p>

CC BY-SA 3.0
2012-12-09T11:59:30.403Z
2012-12-09T11:59:30.403Z
adrianN
<p>one of Einsteins 1905 "miracle" papers was on <a href="http://en.wikipedia.org/wiki/Brownian_motion#Einstein.27s_Theory" rel="nofollow">brownian motion</a>, a classic physical example of a <a href="http://en.wikipedia.org/wiki/Random_walk" rel="nofollow">random walk</a> and yields a formula (ie, basically an algorithm, if the physical process is the "computer") for estimating/calculating particle (molecule) diameter given other known physical constants and the observation/measurement of the (random) particle displacement over time. this paper also served as early theoretical/experimental/foundational evidence for the atomic theory of matter.</p>

CC BY-SA 3.0
2012-09-13T15:53:19.877Z
Again as with evolution: though the motion may be random, and may be modelled by a random walk, what algorithm does this represent? While some algorithms use random walks, this does not mean that all random walks represent algorithms (any more than any string of words in English represents prose just because all English prose consists of words in English).
Niel de Beaudrap
CC BY-SA 3.0
2012-09-11T20:46:06.657Z
2012-09-11T20:46:06.657Z
vzn
<p>another answer in the vein of JS's number theory direction. one of the earliest analog-digital computers constructed is the <a href="http://en.wikipedia.org/wiki/Lehmer_sieve" rel="nofollow noreferrer">Lehmer sieve</a> dating to ~1932, predating electronic computers by about a decade. it basically computes remainder of division <em>mod</em> $n_i$ for a finite number of $n_i$ and applies the <a href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem" rel="nofollow noreferrer">chinese remainder thm</a>. for larger numbers it computes probabilistic answers to number theory questions including factoring. although the terminology at the time may not have referred to "probabilistic algorithms" it was possibly used in this way in some cases. (in this way it also has some similarity to the Fermat probabilistic prime test.)</p>

<p>the machine also bears some similarity to the <a href="http://en.wikipedia.org/wiki/Babbage_engine" rel="nofollow noreferrer">Babbage differential engine</a> (~1830s). its not entirely inconceivable that Babbage or Lovelace may have envisioned something similar to probabilistic algorithms. the machine(s) can certainly be <em>used</em> to implement probabilistic algorithms, borrowing modern theory and superimposing it on the past.</p>

<p>[1] <a href="http://ed-thelen.org/comp-hist/Lehmer-Factoring-Machines.html" rel="nofollow noreferrer">Lehmer factoring machine</a></p>

<p>[2] <a href="http://en.wikipedia.org/wiki/Babbage_engine" rel="nofollow noreferrer">Babbage engine</a></p>

<p><img src="https://i.sstatic.net/5yK4D.jpg" width="200" height="230"><br>
Lehmer <em>mod n</em> &amp; factoring machine</p>

CC BY-SA 3.0
2012-09-15T17:23:22.207Z
Can you describe the sense in which it computed probabilistic answers for large numbers? A quick search doesn't I can't seem to find any references to that online.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-15T17:41:40.303Z
my understanding, it was used [among other purposes] to find smaller factors of large test numbers similar to sieve of eratosthenes. if the large number passed, it is "probably not composite" or "possibly prime" or a "prime candidate". unfortunately the internet is not very good with historical references & origins [even wikipedia], books are better. more details at bottom of [this page](http://ed-thelen.org/comp-hist/Mike-Williams-Lehmer.html), "types of problems Lehmer was _attempting_ to solve" by Dr mike williams, head curator of the computer history museum of CA
vzn
CC BY-SA 3.0
2012-09-15T18:45:36.110Z
_the machine(s) can certainly be used to implement probabilistic algorithms_ — So?  As opposed to other machines that can't?
Jeffε
CC BY-SA 3.0
2012-09-15T18:48:06.640Z
_although the terminology at the time may not have referred to "probabilistic algorithms" it was possibly used in this way in some cases_ — [citation needed] If you have **evidence** that "possibly prime" is a formal statement about probability, and not simply a heuristic description, please cite it.  Otherwise, please stop speculating.
Jeffε
CC BY-SA 3.0
2012-09-16T02:43:33.033Z
dont have the full contents of Lehmers papers available (not even sure what all he published), but the pocklington randomized ref is supported by _a single line_ of one of his papers. what is the criteria? it seems all that is required that Lehmer run the machine on some number greater than $n_1 * n_2 * n_3 * n_x$ for the largest $x$ on the machine, and make some kind of reasonable observation about the result, _not necessarily written down_.... seems plausible to me....
vzn
CC BY-SA 3.0
2012-09-16T14:53:27.887Z
in other words see some of these suggestions as _research leads_. vote em down if you know how to rule it out. =) further suggestion, the [pocklington-lehmer primality test](http://en.wikipedia.org/wiki/Pocklington_primality_test) ie they seemed to mesh their work to some degree. can we be sure the machine was never used to implement the test? the test may returns "inconclusive" in which case, just like the Fermat test & others, some conclusion on probability can be drawn.... did they ever study that conclusion? dont know for sure! can it be ruled out based on everything known/published?
vzn
CC BY-SA 3.0
2012-09-17T12:13:37.130Z
@vzn: Answers on Stackexchange fora are not meant to be research leads, but **answers**.  Precisely because it is impossible to rule out possibilities because the historical record might accidentally omit them, the burden is on the person making the positive/affirmative claim. Your "research leads" are as likely to be speculative wild-goose chases where the OP asks for historical (i.e. recorded) overview.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-17T16:39:51.810Z
NdB, original poster did not specify acceptance criteria as you claim. the exact history relating to the question has prob not been _fully_ researched by anyone incl yourself, and until it is done, its basically an "open question" & airtight rigor as with math thms is not feasible/possible. as for how TCS.se fits into the stackexchange network, try reading [this](http://meta.cs.stackexchange.com/a/103/699) by official stackexchange community coordinator on the TCS.se character/structure wrt other SE sites, spec. warning against extreme specialization/narrowness/inflexibility/exclusionism etc
vzn
CC BY-SA 3.0
2012-09-17T16:59:25.303Z
@vzn: If you allow that there could always be missing data, the exact history will *never* be "fully researched" by *anyone*. It isn't *necessary* to say on a StackExchange site that one is looking for answers, because that is what StackExchange is for; what makes it meaningful as a soft question is not that any speculative projection will do, but that it isn't actually about a problem in computer science. It's about *history* in this case. For every other topic, responses to problems such as "Maybe! Have you tried approach X, Y, Z?" are comment material at best.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-17T17:31:04.937Z
NdB, admittedly need some assistance from the "collective intelligence" of the site & other _experts_ to flesh out details & rule out all possibilities. have posted _numerous tangible historical refs_ & imho your comments eventually amt to "I want a _better_ reference" repeated _ad infinitum ad nauseam_. and speaking of _specifics_ on _historical record_, feel it is [_you_](http://cstheory.stackexchange.com/users/248/niel-de-beaudrap?tab=tags) who is leading on a wild goose chase.
vzn
CC BY-SA 3.0
2012-09-20T18:15:13.803Z
fyi @Niel descr by lehmers son that sounds a lot like the pocklington algorithm: "Since every quadratic residue R of a number N is also a quadratic residue of every possible factor of N, it follows that the problem of factoring a number N is hereby reduced to the discovery of an adequate number of quadratic residues R of N and the superposition of the corresponding stencils to reveal those few primes having these residues R." [Lehmer bio](http://www-history.mcs.st-andrews.ac.uk/Biographies/Lehmer_Derrick_N.html). the later wheel computers were apparently based on the earlier stencil methods.
vzn
CC BY-SA 3.0
2012-09-20T18:23:35.040Z
here is [lehmers description](http://projecteuclid.org/euclid.bams/1183419373) of [one of?] his algorithms that he says is _"**sometimes** very effective in the factoring of large numbers_"
vzn
CC BY-SA 3.0
2012-09-20T18:36:45.687Z
[followup descr](http://projecteuclid.org/euclid.bams/1183491949) by lehmer. so lehmer clearly had methods that _sometimes succeeded_ factoring large numbers, and otherwise were indeterminate if they failed. but isnt this a **probabilistic algorithm** using weak criteria? he maybe didnt know or was able to estimate the probability of failure, but he did seem to have a _rudimentary theory of, and implement_ **probabilistic algorithm(s)**. (1st ref is from 1903(!) talk, published 1907, 2nd is 1927)
vzn
CC BY-SA 3.0
2012-09-15T15:22:51.960Z
2012-09-15T15:37:35.117Z
2012-09-15T15:37:35.117Z
vzn
<p>here are some cases of the early and even ancient/prehistory beginnings of concepts related to randomized algorithms.</p>

<ul>
<li><p>consider the <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow"><strong>Sieve of Eratosthenes,</strong></a> approx 2 millenia old. somewhat implicit in the algorithm would be the idea of "stopping early" in marking off the prime intervals, before all intervals up to $n/2$ have been marked off. it is clear that the "later" longer intervals are less likely to mark off a given number under consideration. in other words, its a rough visualization of the basic number theory fact that "most composite numbers have small factors" and that testing a bunch of small factors is enough to rule out many composite numbers. this concept would probably be understood by the Greeks.</p></li>
<li><p><strong>games of chance</strong> and <strong>gambling</strong> are very ancient. from modern theory, games have strong similarities if not direct connections to algorithms. gambling/gaming <a href="http://en.wikipedia.org/wiki/dice" rel="nofollow"><strong>dice</strong></a> are known to be at least <em>five millenia</em> old.</p></li>
<li><p>the Greeks &amp; Romans also had the concept of <strong>drawing straws</strong> where the person drawing the shortest straw lost. similar to dice, its in a sense the simplest possible algorithm to make a single random choice.</p></li>
<li><p>full disclosure, there is a tinge of bloody history and connection. in other answer MDB mentions <strong>evolution</strong>. part of evolution is <strong>natural selection</strong> which also has parallels to <strong>human warfare</strong> — apparently an intrinsic part of the evolution of human cities/societies. in a sense a war is a crude semirandom algorithm for "something" which sociologists &amp; historians still argue over exact causes. theft/looting? allocating resources? territory? political power? slaves? (etc.) the Romans also had a grisly practice called <a href="http://en.wikipedia.org/wiki/Decimation_%28Roman_army%29" rel="nofollow"><strong>decimation</strong></a> (the modern word actually derives in etymology from the ancient one!) in which, as punishment for mutiny or cowardice, every 10th soldier selected at random was executed by remaining soldiers. it might seem a forgotten and atavistic practice, but it seems to have some parallel to modern <a href="http://en.wikipedia.org/wiki/Russian_roulette" rel="nofollow"><strong>russian roulette</strong></a>, a "modern" randomized quasi-game for suicide.</p></li>
</ul>

CC BY-SA 3.0
2012-09-13T15:39:39.933Z
It's not clear whether the first is an example where the ancients understood that randomness could play a role: did they make the connection between "most composite numbers" and "any randomly chosen number, with high probability", and did they actually recognize the assertion about 'most' composite numbers to begin with? (Priorities in mathematics have changed a lot since 300 BCE, we should avoid trying to read our values into how they thought of their work.) And it's not clear to me that the latter three are 'algorithms' at all (see my comment on Marzio's response).
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T15:49:13.717Z
admittedly the concept of "algorithm" has some subtle nuances but it seems to be similar to the Church-Turing thesis where one can take an expansive view. in other words if anyone accepts the C-T thesis (which is the majority of CS practitioners), they are basically taking the broad view of algorithms, which yes, is a lens, yet nevertheless has implications on interpreting the history of CS "pre modern era". and of course we cant have any strong certitude about long lost history in the sands of time, only suggestion.
vzn
CC BY-SA 3.0
2012-09-13T15:51:10.003Z
The Church-Turing thesis is about algorithms to compute functions and relations. It's not clear to me that a dice game represents an algorithm any more than me punching random keys on a pocket calculator represents an algorithm.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T15:58:42.553Z
fyi the greeks did have a term for composite numbers, apparently they called them "rectangular" because they could be laid out in a $m$ by $n$ rectangular grid.
vzn
CC BY-SA 3.0
2012-09-13T16:03:21.257Z
That's not what I'm asking about; I'm asking about whether they reasoned about the relative frequency of composite numbers in the way that you describe.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T16:14:24.347Z
hint: _algorithms_ have _evolved_. think _Homo sapiens_ vs _Homo sapiens neanderthalensis_ vs _Homo neanderthalensis_
vzn
CC BY-SA 3.0
2012-09-13T16:17:44.490Z
I'm afraid I'm not interested in vague generalities, and it seems quite obvious that we disagree fundamentally in what an "algorithm" is. I'm interested in more than just "phenomena". Otherwise, we may as well cite all quantum mechanical events after the Big Bang as examples of "randomized algorithms", which makes the whole subject trivial.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T16:20:36.740Z
ah, so, [tag:soft-question] and [tag:ho.history-overview] are admittedly not your thing!
vzn
CC BY-SA 3.0
2012-09-13T16:25:03.610Z
"soft question" doesn't mean a question with infinitely flexible boundaries; "historical overview" is not the same as historical revisionism.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T16:30:50.480Z
think its actually the above observation about the sieve of eratosthenes that is near-trivial, & that euclid or eratosthenes or some other brilliant greek like diophantus probably understood it intuitively but did not necessarily write it down, or perhaps it was written down but lost. and, civilized people can respectfully disagree. or in games, call a draw.
vzn
CC BY-SA 3.0
2012-09-13T16:36:28.140Z
Your 'hint' to me about evolution, nor your casting me as wasting time on a question I don't like, nor your evasion of my earlier question, were respectful. And in fact, your speculating that the Greeks probably knew about what you're talking about but didn't bother to write about it is exactly one of the things which "historical revisionism" can refer to. (Maybe Archimedes invented decimal notation, but didn't bother to make any record; after all, the Sand Reckoner is quite close to place notation, and the Greeks did use a base-10-like system. But should we take the idea seriously? No.)
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T16:44:43.413Z
its clear that there are many basic beginnings of TCS concepts in greek number theory, some of them with near-astonishing sophistication by modern standards, including things like primality, algorithms, euclids GCD algorithm etc (with recursion! possibly one of the earliest cases!) but few in the TCS field seem to recognize/realize/appreciate that at times. maybe its rarely taught in CS classes. there are however good math history classes in college.
vzn
CC BY-SA 3.0
2012-09-13T16:48:50.203Z
I agree that it's concievable, and that it isn't even very far-fetched -- aside, of course, from the fact that we don't seem to have any record of the Greeks talking about probability per se. But if there's an actual record of it, you should be able to actually point it out. Otherwise, it's speculation, not history.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-13T17:39:20.693Z
It seems to me that decimation is a good example of a randomized technique, albeit a grisly one
Suresh Venkat
CC BY-SA 3.0
2012-09-13T15:12:39.550Z
2012-09-13T15:25:45.193Z
2012-09-13T15:25:45.193Z
vzn
<p>JS mentions number theory. Fermat is credited with the <a href="http://en.wikipedia.org/wiki/Fermat_primality_test" rel="nofollow">Fermat primality test</a>, a probabilistic algorithm which dates to the 1600s and serves as a precursor to more modern primality tests such as Solovay-Strassen and Miller-Rabin. [it would take a historian specializing in math &amp; number theory to try to pinpoint exactly what Fermat knew about it versus modern knowledge which is much more complete about the structure of its pseudoprimes (false positives) etc.]</p>

CC BY-SA 3.0
2012-09-13T15:35:55.540Z
Can you cite Fermat as having used his test as a way of filtering out randomly selected integers as non-primes (as opposed to just an interesting property that primes have)? Or perhaps cite an early author who suggests doing so?
Niel de Beaudrap
CC BY-SA 3.0
2012-09-15T05:12:21.193Z
as stated the exact details are better left to a professional historian. however note [addendum; should have mentioned this] the simple historical fact that [fermat is credited as the _founding coinventor_ of probability theory](http://en.wikipedia.org/wiki/Probability) along with pascal, laying the groundwork in a series of letters in the mid 1600s.
vzn
CC BY-SA 3.0
2012-09-15T11:13:14.780Z
it's not really appropriate to propose answers based on what you believe someone else might be able to show. Again, that is speculation.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-15T14:32:32.630Z
NdB, am only making a plausible case & letting the group decide. read carefully-- didnt mention my personal "belief" at all. the votes will reflect the quality or trust in the answer and its not really nec or appropriate to be a self-appointed arbiter of answer quality. historical analysis is not cut and dried like math theorems nor can it be prematurely declared definitive. another direct consideration is that Fermat rarely wrote out his actual real knowledge in letters and historians are quite consistent in giving him credit for some discoveries he did not state directly, only indirectly.
vzn
CC BY-SA 3.0
2012-09-15T15:43:39.967Z
@vzn: If Fermat had realized that Fermat's Little Theorem was a good primality test, he would have calculated that the 5th Fermat number was [not prime](http://en.wikipedia.org/wiki/Fermat_number).  This was not done until Euler factored it more than 60 years after Fermat's death.
Peter Shor 
CC BY-SA 3.0
2012-09-15T15:51:03.763Z
@peter ah but so then maybe at least _Euler_ understood it? =)
vzn
CC BY-SA 3.0
2012-09-15T18:43:58.187Z
@vzn: [citation needed]
Jeffε
CC BY-SA 3.0
2012-09-16T02:35:36.860Z
ok guys, it looks to me that, as the original question indicates, a wiki entry was wildly inaccurate about origins of randomized algorithms (off by at least ~2centuries) & maybe nobody has really seriously looked into the real history of _randomized_ algorithms in particular, that appears to be the case. doubt there is a very good ref on the subj at all. so you can keep dinging the answers as not supported by a particular authority/ref calling them "randomized algorithms", but that seems unfair to penalize them merely on that criteria! they are supported by known history...
vzn
CC BY-SA 3.0
2012-09-13T14:56:42.853Z
2012-09-13T14:56:42.853Z
vzn
<p>This is discussed a bit in my paper with H. C. Williams, "Factoring Integers before Computers"</p>

<p>In a 1917 paper, H. C. Pocklington discussed an algorithm for finding sqrt(a), modulo p, which depended on choosing elements at random to get a nonresidue of a certain form.  In it, he said, "We have to do this [find the nonresidue] by trial, using the Law of Quadratic Reciprocity, which is a defect in the method.  But as for each value of u half the values of t are suitable, there should be no difficulty in finding one."</p>

<p>So this is one of the first explicit mentions of a randomized algorithm.</p>

CC BY-SA 3.0
2012-09-12T17:02:57.487Z
This is a really nice reference. Has Pocklington's Algorithm since been derandomized?

Tangentially, I love your work - both in and out of CS - in particular your algorithm for Bachet's conjecture (the paper was hard to find a copy of though!) but also your civil liberties work. Have you watched Errol Morris's "Mr. Death?"
Ross Snider
CC BY-SA 3.0
2012-09-13T15:43:12.367Z
interesting. it's reminiscent of randomized primality testing
Sasho Nikolov
CC BY-SA 3.0
2012-09-13T15:43:42.283Z
And a Las Vegas algorithm too! Nice reference.
David Eppstein
CC BY-SA 3.0
2012-09-14T13:53:32.090Z
Very nice reference.
Jérémie
CC BY-SA 3.0
2012-09-20T18:07:58.420Z
speaking of factoring before computers, does anyone know what [Lehmer](http://en.wikipedia.org/wiki/Derrick_Norman_Lehmer) knew about the pocklington algorithm, or any other randomized algorithms, or whether Lehmer actually ever implemented it on his [sieve factoring computer](http://en.wikipedia.org/wiki/Lehmer_sieve)? the two apparently have some connection with the [Pocklington-Lehmer primality test](http://en.wikipedia.org/wiki/Pocklington_primality_test) acc to wikipedia
vzn
CC BY-SA 3.0
2012-09-12T16:51:42.673Z
2012-09-12T16:51:42.673Z
Jeffrey Shallit
<p>Edit: I choice the answer with highest score by December 06, 2012.</p>

<p>This is a soft question.</p>

<p>The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms? </p>

<p>In <a href="http://en.wikipedia.org/wiki/Randomized_algorithm#History" rel="noreferrer">this wiki entry</a>, Rabin's algorithm for the closest pair problem in computational geometry was given as the first randomized algorithm (year???). Lipton introduced Rabin's algorithm as the start of the modern era of random algorithms <a href="http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/" rel="noreferrer">here</a>, but not as the first one. I also know many algorithms for probabilistic finite automata (a very simple computational model) discovered during 1960s.</p>

<p>Do you know any probabilistic/randomized algorithms (or method) even before 1960s? </p>

<p>or</p>

<p>Which finding can be seen as the first probabilistic/randomized algorithm?</p>

CC BY-SA 3.0
2012-09-11T20:18:21.080Z
The age-old idea of tasting a spoonful of boiling soup to check if it tastes right is essentially random sampling, a probabilistic algorithm with provable guarantees.
arnab
CC BY-SA 3.0
2012-09-11T21:53:10.450Z
Rabin's algorithm was published in 1976, long after "modern" computer science was well-established.
Jeffε
CC BY-SA 3.0
2012-09-13T16:05:36.073Z
Could you perhaps clarify if there are any criteria which you would like to impose on "algorithms", in order to clarify whether you think e.g. that natural phenomena which predate humanity by billions of years represent "algorithms", as suggested by some of the responses below?
Niel de Beaudrap
CC BY-SA 3.0
2012-09-15T15:13:14.390Z
@NieldeBeaudrap: What in my mind was some mathematically well-defined algorithms. (But, personally, I like **arnab**'s answer very much :))
Abuzer Yakaryilmaz
<ds.algorithms><reference-request><big-list><randomized-algorithms><ho.history-overview>
Probabilistic (randomized) algorithms before "modern" computer science appeared
Abuzer Yakaryilmaz
# Probabilistic (randomized) algorithms before "modern" computer science appeared

(Asked by: username_0 on 2012-09-11)

Edit: I choice the answer with highest score by December 06, 2012.

This is a soft question.

The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?

In [this wiki entry](http://en.wikipedia.org/wiki/Randomized_algorithm#History), Rabin's algorithm for the closest pair problem in computational geometry was given as the first randomized algorithm (year???). Lipton introduced Rabin's algorithm as the start of the modern era of random algorithms [here](http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/), but not as the first one. I also know many algorithms for probabilistic finite automata (a very simple computational model) discovered during 1960s.

Do you know any probabilistic/randomized algorithms (or method) even before 1960s?

or

Which finding can be seen as the first probabilistic/randomized algorithm?

**Tags:** ds.algorithms, reference-request, big-list, randomized-algorithms, ho.history-overview
> **Comments:**
> **username_1**: The age-old idea of tasting a spoonful of boiling soup to check if it tastes right is essentially random sampling, a probabilistic algorithm with provable guarantees.  
> **username_2**: Rabin's algorithm was published in 1976, long after "modern" computer science was well-established.  
> **username_3**: Could you perhaps clarify if there are any criteria which you would like to impose on "algorithms", in order to clarify whether you think e.g. that natural phenomena which predate humanity by billions of years represent "algorithms", as suggested by some of the responses below?  
> **username_0**: @NieldeBeaudrap: What in my mind was some mathematically well-defined algorithms. (But, personally, I like **arnab**'s answer very much :))  

---

## 10 answers

### Answer by username_12 on 2012-09-12. Score: 34 | Accepted answer

This is discussed a bit in my paper with H. C. Williams, "Factoring Integers before Computers"

In a 1917 paper, H. C. Pocklington discussed an algorithm for finding sqrt(a), modulo p, which depended on choosing elements at random to get a nonresidue of a certain form. In it, he said, "We have to do this [find the nonresidue] by trial, using the Law of Quadratic Reciprocity, which is a defect in the method. But as for each value of u half the values of t are suitable, there should be no difficulty in finding one."

So this is one of the first explicit mentions of a randomized algorithm.

> **Comments:**
> **username_13**: This is a really nice reference. Has Pocklington's Algorithm since been derandomized?  Tangentially, I love your work - both in and out of CS - in particular your algorithm for Bachet's conjecture (the paper was hard to find a copy of though!) but also your civil liberties work. Have you watched Errol Morris's "Mr. Death?"  
> **username_14**: interesting. it's reminiscent of randomized primality testing  
> **username_4**: And a Las Vegas algorithm too! Nice reference.  
> **username_6**: Very nice reference.  
> **username_5**: speaking of factoring before computers, does anyone know what [Lehmer](http://en.wikipedia.org/wiki/Derrick_Norman_Lehmer) knew about the pocklington algorithm, or any other randomized algorithms, or whether Lehmer actually ever implemented it on his [sieve factoring computer](http://en.wikipedia.org/wiki/Lehmer_sieve)? the two apparently have some connection with the [Pocklington-Lehmer primality test](http://en.wikipedia.org/wiki/Pocklington_primality_test) acc to wikipedia  

---

### Answer by username_5 on 2012-09-11. Score: 28

[Buffons needle algorithm](http://en.wikipedia.org/wiki/Buffon%27s_needle) for estimating $\pi$, basically a [Monte Carlo method](http://en.wikipedia.org/wiki/Monte_carlo_method), dates to publication in 1777. note that Monte Carlo methods date to the 1940s with the US "Manhattan" atom bomb project & were coinvented by Ulam, Von Neumann, and Metropolis.

> **Comments:**
> **username_6**: Actually this is related to [a question that I asked](http://cstheory.stackexchange.com/questions/11898/who-first-proposed-using-x2y2-1-monte-carlo-algorithm-to-calculate-pi). Nobody knows exactly who devised the algorithm that many people take to be Buffon's needle nowadays.  
> **username_5**: stated more exactly— there is a clearcut Buffon needle algorithm which involves dropping needles on stripes, and an apparently much different "random point vs circle" algorithm as you mention in that question which some people seem to incorrectly attribute to Buffon, with different, more modern, but uncertain origins.  

---

### Answer by username_4 on 2012-09-12. Score: 19

The [Metropolis–Hastings algorithm](http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm) was published in 1953 and dates back earlier to the Manhattan project, long before Rabin. Like many of the early randomized methods given in other answers, it is a Monte Carlo algorithm.

Is it possible that the claim on the Wikipedia page is a garbled form of the claim that Rabin's was the first [Las Vegas algorithm](http://en.wikipedia.org/wiki/Las_Vegas_algorithm)?


---

### Answer by username_5 on 2012-09-11. Score: 11

The [Gaussian normal curve/distribution](http://en.wikipedia.org/wiki/Normal_distribution) of statistics can be "computed" by many very simple physical processes. One of the simplest is a [board with a pin array](http://en.wikipedia.org/wiki/Bean_machine) in a triangular grid (also known as a ["Galton box"](http://en.wikipedia.org/wiki/Francis_Galton) dating to the 1800s) where pins are offset 1/2 square distance on alternating rows. Dropping balls repeatedly from the same position, the balls randomly displace left or right with probability 0.5. The cumulative distribution recorded at bottom positions yields the Gaussian curve/normal.

> **Comments:**
> **username_7**: +1 just because I’m currently designing a logo for our statistics research group and the Galton Box was our first idea (but turns out to be too complex for a logo).  

---

### Answer by username_8 on 2012-09-11. Score: 11

In my opinion, [natural evolution](http://en.wikipedia.org/wiki/DNA) is a good and rather old probabilistic algorithm :-)

> **Comments:**
> **username_7**: +1 although the *description* of the process as probabilistic us much more recent. ;-)  
> **username_3**: "Algorithm" suggests that there is a problem it is trying to solve; but it isn't. It isn't even "trying" to make animals which are better at surviving; creating animals which are adapted to its environment is just a byproduct (one which is not always achieved, as extinction and mass-extinction events make evident). In this respect, evolution is no more an algorithm than gravity is; it's just this thing which sort of happens.  
> **username_5**: MDB is dead on! evolution is a [genetic algorithm](http://cstheory.stackexchange.com/questions/427/what-are-some-real-world-applications-for-genetic-algorithms) that selects for _evolutionary fitness_ and science is still catching up with all the implications of this.... ie its an active area of research. it hasnt been pointed out much or widely appreciated, but the phenomenal success of GAs in CS is actually strong mathematical/scientific evidence of the reality of biological evolution theory. however, concede it is definitely different than other "algorithms" in some key ways.  
> **username_3**: @vzn: a "genetic algorithm", first of all, selects for a fitness function which we impose for a specific purpose. *We* use evolution as a tool to do something in that case. But that doesn't mean that biological evolution is an algorithm to do anything. Using the gravity analogy again, is there a meaningful sense in which all waterfalls are algorithms, just because we sometimes use waterfalls to generate electricity?  
> **username_8**: @NieldeBeaudrap: *"Algorithm" suggests that there is a problem it is trying to solve* ... IMO natural evolution is trying to solve the (hard) problem of "species survival" in the natural environment. One can say that even a (mechanical) Turing Machine doing his computation, isn't trying to solve a problem following an "algorithm", but it is simply following world's rules :-)  
> **username_3**: @MarzioDeBiasi: however, we typically reserve 'algorithm' for something which is **(a)** planned, that is adopted intentionally; not to mention **(b)** something which provably terminates with success under certain conditions. The consensus is that (a) is false, while for (b) the only time at which the process stops *is precisely* when it fails (which as $t \to \infty$ it will do, with certainty). I'm taking issue with the notion that it is trying to do anything at all having any end-point; and given that it doesn't even always succeed in muddling on as best it can, it seems poor teminology.  
> **username_3**: @MarzioDeBiasi: as for Turing Machines: the essential distinction is that we use the Turing machine as a tool. We impose intention on it. When we speak of "an algorithm to to X", it means that it is something which we may choose in order to accomplish X, and within certain constraints also of our choosing. If Turing machines were strange little animals whose tapes fluttered in the wind, I wouldn't consider them algorithms either. Choosing a particular one of them to solve 2-SAT would be reasonable to describe as an algorithm, however.  
> **username_5**: NdB, am not expecting any satisfactory resolution to your numerous qualms but will throw this out there. all life is just a intermediate process of the computation of DNA. DNA copies and modifies itself in a finite process. DNA copying is therefore an algorithm. evolution supplies random mutations to this copying algorithm, some of which _increase its efficiency and efficacy_. you seem to suffer from the [anthropocentric fallacy](http://en.wikipedia.org/wiki/Anthropocentrism) in asserting that all algorithms must be programmed by humans. many animals have algorithmic-like behavior patterns....  
> **username_5**: furthermore, many _cellular processes_ not merely associated with DNA have extremely algorithmic-like properties. think also _viruses_ which implement _probabilistic algorithms_ for _infection/transmission_. and consider the massive yet still-embryonic field of [DNA computing](http://en.wikipedia.org/wiki/DNA_computing). its clear the modern conception of algorithms is undergoing a near [kuhnian-shift](http://en.wikipedia.org/wiki/Paradigm_shift) to find them almost ubiquitous in nature. dare I mention [wolfram](http://en.wikipedia.org/wiki/A_New_Kind_of_Science)?  
> **username_3**: @vzn: I merely assert that "an algorithm" should entail well-defined parameters of probability of success, not to mention that *there should be an agent which carries it out*. The only 'agent' which could be said to carry out "evolution" would be an entire ecosystem. What should we say that the ecosystem is "trying" to achieve? I would as readily say that you are *anthropomorphising* nature. I only demand that "applying an algorithm" entail some amount of goal-oriented intentionality, applied by humans or no. In what sense can a process without a goal represent an "algorithm"?  

---

### Answer by username_9 on 2012-12-09. Score: 7

There is a paper about [randomized algorithms in 'primitive' cultures](https://cs.uwaterloo.ca/~shallit/Papers/ch.pdf).

Using oracles (e.g. chicken bones, stones) to decide on where to hunt can be seen as a randomized algorithm. One can argue that randomizing the hunting grounds prevents game adaption and overhunting.


---

### Answer by username_5 on 2012-09-11. Score: 1

one of Einsteins 1905 "miracle" papers was on [brownian motion](http://en.wikipedia.org/wiki/Brownian_motion#Einstein.27s_Theory), a classic physical example of a [random walk](http://en.wikipedia.org/wiki/Random_walk) and yields a formula (ie, basically an algorithm, if the physical process is the "computer") for estimating/calculating particle (molecule) diameter given other known physical constants and the observation/measurement of the (random) particle displacement over time. this paper also served as early theoretical/experimental/foundational evidence for the atomic theory of matter.

> **Comments:**
> **username_3**: Again as with evolution: though the motion may be random, and may be modelled by a random walk, what algorithm does this represent? While some algorithms use random walks, this does not mean that all random walks represent algorithms (any more than any string of words in English represents prose just because all English prose consists of words in English).  

---

### Answer by username_5 on 2012-09-15. Score: -4

another answer in the vein of JS's number theory direction. one of the earliest analog-digital computers constructed is the [Lehmer sieve](http://en.wikipedia.org/wiki/Lehmer_sieve) dating to ~1932, predating electronic computers by about a decade. it basically computes remainder of division *mod* $n\_i$ for a finite number of $n\_i$ and applies the [chinese remainder thm](http://en.wikipedia.org/wiki/Chinese_remainder_theorem). for larger numbers it computes probabilistic answers to number theory questions including factoring. although the terminology at the time may not have referred to "probabilistic algorithms" it was possibly used in this way in some cases. (in this way it also has some similarity to the Fermat probabilistic prime test.)

the machine also bears some similarity to the [Babbage differential engine](http://en.wikipedia.org/wiki/Babbage_engine) (~1830s). its not entirely inconceivable that Babbage or Lovelace may have envisioned something similar to probabilistic algorithms. the machine(s) can certainly be *used* to implement probabilistic algorithms, borrowing modern theory and superimposing it on the past.

[1] [Lehmer factoring machine](http://ed-thelen.org/comp-hist/Lehmer-Factoring-Machines.html)

[2] [Babbage engine](http://en.wikipedia.org/wiki/Babbage_engine)

![](https://i.sstatic.net/5yK4D.jpg)  
Lehmer *mod n* & factoring machine

> **Comments:**
> **username_3**: Can you describe the sense in which it computed probabilistic answers for large numbers? A quick search doesn't I can't seem to find any references to that online.  
> **username_5**: my understanding, it was used [among other purposes] to find smaller factors of large test numbers similar to sieve of eratosthenes. if the large number passed, it is "probably not composite" or "possibly prime" or a "prime candidate". unfortunately the internet is not very good with historical references & origins [even wikipedia], books are better. more details at bottom of [this page](http://ed-thelen.org/comp-hist/Mike-Williams-Lehmer.html), "types of problems Lehmer was _attempting_ to solve" by Dr mike williams, head curator of the computer history museum of CA  
> **username_2**: _the machine(s) can certainly be used to implement probabilistic algorithms_ — So?  As opposed to other machines that can't?  
> **username_2**: _although the terminology at the time may not have referred to "probabilistic algorithms" it was possibly used in this way in some cases_ — [citation needed] If you have **evidence** that "possibly prime" is a formal statement about probability, and not simply a heuristic description, please cite it.  Otherwise, please stop speculating.  
> **username_5**: dont have the full contents of Lehmers papers available (not even sure what all he published), but the pocklington randomized ref is supported by _a single line_ of one of his papers. what is the criteria? it seems all that is required that Lehmer run the machine on some number greater than $n_1 * n_2 * n_3 * n_x$ for the largest $x$ on the machine, and make some kind of reasonable observation about the result, _not necessarily written down_.... seems plausible to me....  
> **username_5**: in other words see some of these suggestions as _research leads_. vote em down if you know how to rule it out. =) further suggestion, the [pocklington-lehmer primality test](http://en.wikipedia.org/wiki/Pocklington_primality_test) ie they seemed to mesh their work to some degree. can we be sure the machine was never used to implement the test? the test may returns "inconclusive" in which case, just like the Fermat test & others, some conclusion on probability can be drawn.... did they ever study that conclusion? dont know for sure! can it be ruled out based on everything known/published?  
> **username_3**: @vzn: Answers on Stackexchange fora are not meant to be research leads, but **answers**.  Precisely because it is impossible to rule out possibilities because the historical record might accidentally omit them, the burden is on the person making the positive/affirmative claim. Your "research leads" are as likely to be speculative wild-goose chases where the OP asks for historical (i.e. recorded) overview.  
> **username_5**: NdB, original poster did not specify acceptance criteria as you claim. the exact history relating to the question has prob not been _fully_ researched by anyone incl yourself, and until it is done, its basically an "open question" & airtight rigor as with math thms is not feasible/possible. as for how TCS.se fits into the stackexchange network, try reading [this](http://meta.cs.stackexchange.com/a/103/699) by official stackexchange community coordinator on the TCS.se character/structure wrt other SE sites, spec. warning against extreme specialization/narrowness/inflexibility/exclusionism etc  
> **username_3**: @vzn: If you allow that there could always be missing data, the exact history will *never* be "fully researched" by *anyone*. It isn't *necessary* to say on a StackExchange site that one is looking for answers, because that is what StackExchange is for; what makes it meaningful as a soft question is not that any speculative projection will do, but that it isn't actually about a problem in computer science. It's about *history* in this case. For every other topic, responses to problems such as "Maybe! Have you tried approach X, Y, Z?" are comment material at best.  
> **username_5**: NdB, admittedly need some assistance from the "collective intelligence" of the site & other _experts_ to flesh out details & rule out all possibilities. have posted _numerous tangible historical refs_ & imho your comments eventually amt to "I want a _better_ reference" repeated _ad infinitum ad nauseam_. and speaking of _specifics_ on _historical record_, feel it is [_you_](http://cstheory.stackexchange.com/users/248/niel-de-beaudrap?tab=tags) who is leading on a wild goose chase.  
> **username_5**: fyi @Niel descr by lehmers son that sounds a lot like the pocklington algorithm: "Since every quadratic residue R of a number N is also a quadratic residue of every possible factor of N, it follows that the problem of factoring a number N is hereby reduced to the discovery of an adequate number of quadratic residues R of N and the superposition of the corresponding stencils to reveal those few primes having these residues R." [Lehmer bio](http://www-history.mcs.st-andrews.ac.uk/Biographies/Lehmer_Derrick_N.html). the later wheel computers were apparently based on the earlier stencil methods.  
> **username_5**: here is [lehmers description](http://projecteuclid.org/euclid.bams/1183419373) of [one of?] his algorithms that he says is _"**sometimes** very effective in the factoring of large numbers_"  
> **username_5**: [followup descr](http://projecteuclid.org/euclid.bams/1183491949) by lehmer. so lehmer clearly had methods that _sometimes succeeded_ factoring large numbers, and otherwise were indeterminate if they failed. but isnt this a **probabilistic algorithm** using weak criteria? he maybe didnt know or was able to estimate the probability of failure, but he did seem to have a _rudimentary theory of, and implement_ **probabilistic algorithm(s)**. (1st ref is from 1903(!) talk, published 1907, 2nd is 1927)  

---

### Answer by username_5 on 2012-09-13. Score: -6

here are some cases of the early and even ancient/prehistory beginnings of concepts related to randomized algorithms.

* consider the [**Sieve of Eratosthenes,**](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) approx 2 millenia old. somewhat implicit in the algorithm would be the idea of "stopping early" in marking off the prime intervals, before all intervals up to $n/2$ have been marked off. it is clear that the "later" longer intervals are less likely to mark off a given number under consideration. in other words, its a rough visualization of the basic number theory fact that "most composite numbers have small factors" and that testing a bunch of small factors is enough to rule out many composite numbers. this concept would probably be understood by the Greeks.
* **games of chance** and **gambling** are very ancient. from modern theory, games have strong similarities if not direct connections to algorithms. gambling/gaming [**dice**](http://en.wikipedia.org/wiki/dice) are known to be at least *five millenia* old.
* the Greeks & Romans also had the concept of **drawing straws** where the person drawing the shortest straw lost. similar to dice, its in a sense the simplest possible algorithm to make a single random choice.
* full disclosure, there is a tinge of bloody history and connection. in other answer MDB mentions **evolution**. part of evolution is **natural selection** which also has parallels to **human warfare** — apparently an intrinsic part of the evolution of human cities/societies. in a sense a war is a crude semirandom algorithm for "something" which sociologists & historians still argue over exact causes. theft/looting? allocating resources? territory? political power? slaves? (etc.) the Romans also had a grisly practice called [**decimation**](http://en.wikipedia.org/wiki/Decimation_%28Roman_army%29) (the modern word actually derives in etymology from the ancient one!) in which, as punishment for mutiny or cowardice, every 10th soldier selected at random was executed by remaining soldiers. it might seem a forgotten and atavistic practice, but it seems to have some parallel to modern [**russian roulette**](http://en.wikipedia.org/wiki/Russian_roulette), a "modern" randomized quasi-game for suicide.

> **Comments:**
> **username_3**: It's not clear whether the first is an example where the ancients understood that randomness could play a role: did they make the connection between "most composite numbers" and "any randomly chosen number, with high probability", and did they actually recognize the assertion about 'most' composite numbers to begin with? (Priorities in mathematics have changed a lot since 300 BCE, we should avoid trying to read our values into how they thought of their work.) And it's not clear to me that the latter three are 'algorithms' at all (see my comment on Marzio's response).  
> **username_5**: admittedly the concept of "algorithm" has some subtle nuances but it seems to be similar to the Church-Turing thesis where one can take an expansive view. in other words if anyone accepts the C-T thesis (which is the majority of CS practitioners), they are basically taking the broad view of algorithms, which yes, is a lens, yet nevertheless has implications on interpreting the history of CS "pre modern era". and of course we cant have any strong certitude about long lost history in the sands of time, only suggestion.  
> **username_3**: The Church-Turing thesis is about algorithms to compute functions and relations. It's not clear to me that a dice game represents an algorithm any more than me punching random keys on a pocket calculator represents an algorithm.  
> **username_5**: fyi the greeks did have a term for composite numbers, apparently they called them "rectangular" because they could be laid out in a $m$ by $n$ rectangular grid.  
> **username_3**: That's not what I'm asking about; I'm asking about whether they reasoned about the relative frequency of composite numbers in the way that you describe.  
> **username_5**: hint: _algorithms_ have _evolved_. think _Homo sapiens_ vs _Homo sapiens neanderthalensis_ vs _Homo neanderthalensis_  
> **username_3**: I'm afraid I'm not interested in vague generalities, and it seems quite obvious that we disagree fundamentally in what an "algorithm" is. I'm interested in more than just "phenomena". Otherwise, we may as well cite all quantum mechanical events after the Big Bang as examples of "randomized algorithms", which makes the whole subject trivial.  
> **username_5**: ah, so, [tag:soft-question] and [tag:ho.history-overview] are admittedly not your thing!  
> **username_3**: "soft question" doesn't mean a question with infinitely flexible boundaries; "historical overview" is not the same as historical revisionism.  
> **username_5**: think its actually the above observation about the sieve of eratosthenes that is near-trivial, & that euclid or eratosthenes or some other brilliant greek like diophantus probably understood it intuitively but did not necessarily write it down, or perhaps it was written down but lost. and, civilized people can respectfully disagree. or in games, call a draw.  
> **username_3**: Your 'hint' to me about evolution, nor your casting me as wasting time on a question I don't like, nor your evasion of my earlier question, were respectful. And in fact, your speculating that the Greeks probably knew about what you're talking about but didn't bother to write about it is exactly one of the things which "historical revisionism" can refer to. (Maybe Archimedes invented decimal notation, but didn't bother to make any record; after all, the Sand Reckoner is quite close to place notation, and the Greeks did use a base-10-like system. But should we take the idea seriously? No.)  
> **username_5**: its clear that there are many basic beginnings of TCS concepts in greek number theory, some of them with near-astonishing sophistication by modern standards, including things like primality, algorithms, euclids GCD algorithm etc (with recursion! possibly one of the earliest cases!) but few in the TCS field seem to recognize/realize/appreciate that at times. maybe its rarely taught in CS classes. there are however good math history classes in college.  
> **username_3**: I agree that it's concievable, and that it isn't even very far-fetched -- aside, of course, from the fact that we don't seem to have any record of the Greeks talking about probability per se. But if there's an actual record of it, you should be able to actually point it out. Otherwise, it's speculation, not history.  
> **username_10**: It seems to me that decimation is a good example of a randomized technique, albeit a grisly one  

---

### Answer by username_5 on 2012-09-13. Score: -7

JS mentions number theory. Fermat is credited with the [Fermat primality test](http://en.wikipedia.org/wiki/Fermat_primality_test), a probabilistic algorithm which dates to the 1600s and serves as a precursor to more modern primality tests such as Solovay-Strassen and Miller-Rabin. [it would take a historian specializing in math & number theory to try to pinpoint exactly what Fermat knew about it versus modern knowledge which is much more complete about the structure of its pseudoprimes (false positives) etc.]

> **Comments:**
> **username_3**: Can you cite Fermat as having used his test as a way of filtering out randomly selected integers as non-primes (as opposed to just an interesting property that primes have)? Or perhaps cite an early author who suggests doing so?  
> **username_5**: as stated the exact details are better left to a professional historian. however note [addendum; should have mentioned this] the simple historical fact that [fermat is credited as the _founding coinventor_ of probability theory](http://en.wikipedia.org/wiki/Probability) along with pascal, laying the groundwork in a series of letters in the mid 1600s.  
> **username_3**: it's not really appropriate to propose answers based on what you believe someone else might be able to show. Again, that is speculation.  
> **username_5**: NdB, am only making a plausible case & letting the group decide. read carefully-- didnt mention my personal "belief" at all. the votes will reflect the quality or trust in the answer and its not really nec or appropriate to be a self-appointed arbiter of answer quality. historical analysis is not cut and dried like math theorems nor can it be prematurely declared definitive. another direct consideration is that Fermat rarely wrote out his actual real knowledge in letters and historians are quite consistent in giving him credit for some discoveries he did not state directly, only indirectly.  
> **username_11**: @vzn: If Fermat had realized that Fermat's Little Theorem was a good primality test, he would have calculated that the 5th Fermat number was [not prime](http://en.wikipedia.org/wiki/Fermat_number).  This was not done until Euler factored it more than 60 years after Fermat's death.  
> **username_5**: @peter ah but so then maybe at least _Euler_ understood it? =)  
> **username_2**: @vzn: [citation needed]  
> **username_5**: ok guys, it looks to me that, as the original question indicates, a wiki entry was wildly inaccurate about origins of randomized algorithms (off by at least ~2centuries) & maybe nobody has really seriously looked into the real history of _randomized_ algorithms in particular, that appears to be the case. doubt there is a very good ref on the subj at all. so you can keep dinging the answers as not supported by a particular authority/ref calling them "randomized algorithms", but that seems unfair to penalize them merely on that criteria! they are supported by known history...  

---

