28

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, 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, 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?

Abuzer Yakaryilmaz
  • 3,707
  • 1
  • 20
  • 38
  • 26
    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 Sep 11 '12 at 20:18
  • 3
    Rabin's algorithm was published in 1976, long after "modern" computer science was well-established. – Jeffε Sep 11 '12 at 21:53
  • 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 Sep 13 '12 at 16:05
  • @NieldeBeaudrap: What in my mind was some mathematically well-defined algorithms. (But, personally, I like arnab's answer very much :)) – Abuzer Yakaryilmaz Sep 15 '12 at 15:13

10 Answers10

34

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.

Jeffrey Shallit
  • 6,986
  • 33
  • 38
28

Buffons needle algorithm for estimating $\pi$, basically a 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.

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 8
    Actually this is related to a question that I asked. Nobody knows exactly who devised the algorithm that many people take to be Buffon's needle nowadays. – Jérémie Sep 11 '12 at 21:33
  • 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 Sep 15 '12 at 16:28
19

The Metropolis–Hastings 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?

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
11

The Gaussian normal curve/distribution of statistics can be "computed" by many very simple physical processes. One of the simplest is a board with a pin array in a triangular grid (also known as a "Galton box" 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.

Bill the Lizard
  • 123
  • 1
  • 2
  • 10
vzn
  • 11,014
  • 2
  • 31
  • 64
  • +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 Sep 12 '12 at 14:40
11

In my opinion, natural evolution is a good and rather old probabilistic algorithm :-)

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 1
    +1 although the description of the process as probabilistic us much more recent. ;-) – Konrad Rudolph Sep 12 '12 at 14:41
  • 7
    "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 Sep 13 '12 at 15:33
  • MDB is dead on! evolution is a genetic algorithm 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 Sep 13 '12 at 15:44
  • 2
    @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 Sep 13 '12 at 15:56
  • @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 Sep 13 '12 at 16:06
  • @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 Sep 13 '12 at 16:08
  • @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 Sep 13 '12 at 16:14
  • 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 in asserting that all algorithms must be programmed by humans. many animals have algorithmic-like behavior patterns.... – vzn Sep 13 '12 at 22:15
  • 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. its clear the modern conception of algorithms is undergoing a near kuhnian-shift to find them almost ubiquitous in nature. dare I mention wolfram? – vzn Sep 15 '12 at 16:11
  • 4
    @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 Sep 15 '12 at 18:08
7

There is a paper about randomized algorithms in 'primitive' cultures.

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.

adrianN
  • 877
  • 10
  • 13
1

one of Einsteins 1905 "miracle" papers was on brownian motion, a classic physical example of a 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.

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 4
    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 Sep 13 '12 at 15:53
-4

another answer in the vein of JS's number theory direction. one of the earliest analog-digital computers constructed is the 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. 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 (~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

[2] Babbage engine


Lehmer mod n & factoring machine

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 1
    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 Sep 15 '12 at 17:23
  • 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, "types of problems Lehmer was attempting to solve" by Dr mike williams, head curator of the computer history museum of CA – vzn Sep 15 '12 at 17:41
  • 1
    the machine(s) can certainly be used to implement probabilistic algorithms — So? As opposed to other machines that can't? – Jeffε Sep 15 '12 at 18:45
  • 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. – Jeffε Sep 15 '12 at 18:48
  • 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 Sep 16 '12 at 02:43
  • 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 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 Sep 16 '12 at 14:53
  • @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 Sep 17 '12 at 12:13
  • 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 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 Sep 17 '12 at 16:39
  • @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 Sep 17 '12 at 16:59
  • 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 who is leading on a wild goose chase. – vzn Sep 17 '12 at 17:31
  • 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. the later wheel computers were apparently based on the earlier stencil methods. – vzn Sep 20 '12 at 18:15
  • here is lehmers description of [one of?] his algorithms that he says is "sometimes very effective in the factoring of large numbers" – vzn Sep 20 '12 at 18:23
  • followup descr 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 Sep 20 '12 at 18:36
-6

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

  • consider the 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 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 (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, a "modern" randomized quasi-game for suicide.

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 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 Sep 13 '12 at 15:39
  • 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 Sep 13 '12 at 15:49
  • 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 Sep 13 '12 at 15:51
  • 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 Sep 13 '12 at 15:58
  • 1
    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 Sep 13 '12 at 16:03
  • hint: algorithms have evolved. think Homo sapiens vs Homo sapiens neanderthalensis vs Homo neanderthalensis – vzn Sep 13 '12 at 16:14
  • 1
    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 Sep 13 '12 at 16:17
  • ah, so, [tag:soft-question] and [tag:ho.history-overview] are admittedly not your thing! – vzn Sep 13 '12 at 16:20
  • 1
    "soft question" doesn't mean a question with infinitely flexible boundaries; "historical overview" is not the same as historical revisionism. – Niel de Beaudrap Sep 13 '12 at 16:25
  • 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 Sep 13 '12 at 16:30
  • 2
    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 Sep 13 '12 at 16:36
  • 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 Sep 13 '12 at 16:44
  • 1
    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 Sep 13 '12 at 16:48
  • 1
    It seems to me that decimation is a good example of a randomized technique, albeit a grisly one – Suresh Venkat Sep 13 '12 at 17:39
-7

JS mentions number theory. Fermat is credited with the 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.]

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 2
    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 Sep 13 '12 at 15:35
  • 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 along with pascal, laying the groundwork in a series of letters in the mid 1600s. – vzn Sep 15 '12 at 05:12
  • 2
    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 Sep 15 '12 at 11:13
  • 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 Sep 15 '12 at 14:32
  • 3
    @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. This was not done until Euler factored it more than 60 years after Fermat's death. – Peter Shor Sep 15 '12 at 15:43
  • @peter ah but so then maybe at least Euler understood it? =) – vzn Sep 15 '12 at 15:51
  • 2
    @vzn: [citation needed] – Jeffε Sep 15 '12 at 18:43
  • 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 Sep 16 '12 at 02:35