4 ms·
I’m still unclear on whether probabilistic algorithms are “algorithms” in the strict sense - in that definition an algorithm should have deterministic behavior,
by olliej 8y ago
I’m still unclear on whether probabilistic algorithms are “algorithms” in the strict sense - in that definition an algorithm should have deterministic behavior, which a probabilistic method does not have. But let’s say your “random” is a deterministic prng- does that then make the PA a deterministic algorithm?
Basically the distinction can be best illustrated with bozo/bogo sort. The definition many people use is:
1. Randomly shuffle the input
2. See if it is sorted, if not go to 1.
The problem, as explained to me by an algorithms lecturer a long time ago, is that the algorithm is not guaranteed to finish, and more over the same input may or may not result in it finishing on different runs.
Per that lecturer a “correct” bozo sort is
1. Generate a list of every permutation of the input
2. Iterate the list until you find a sorted entry and return that.
It has computable best case, worst case, and average case (all terrible). It is guaranteed that the same input will always produce the same output (terminate vs not terminate).
Obviously you could optimize this if you had an algorithm that could shuffle an input such that you were guaranteed that if you shuffled it’s own output you were guaranteed to produce every ordering of the original input. Then you would get closer to: shuffle; check; repeat. But still note that there is no random involved :)
- hyperion2010 8y agoI think that the intuition here has to do with the dimensionality of the problem, in the sense that we have proved that in 3 dimensions a random walk will never return to it's starting point, bit in two dimensions it will. Mapping all probabilistic algorithms into demensional random walk space is probably extremely difficult though.
- dcow 8y ago> in the sense that we have proved that in 3 dimensions a random walk will never return to it’s (sic.) starting point We have? I believe the probability is ~34%. http://mathworld.wolfram.com/PolyasRandomWalkConstants.html http://mathworld.wolfram.com/PolyasRandomWalkConstants.html
- hyperion2010 8y agoSorry, I had it reversed in my head. For 1 and 2 dimensions they will return to the starting point with probability 1. For 3 dimensions it simply that it is not probability 1. Obviously a weaker result.
- rcfox 8y agoDo you have a better source than "an anonymous lecturer once said..."? I've never heard such a strict definition of algorithm before. Randomized algorithms are often used to avoid falling into worst-case scenarios and improve run-time, like with quicksort, or to avoid settling in local minima like with simulated annealing.
- olliej 8y agoOk per wikipedia (https://en.wikipedia.org/wiki/Algorithm https://en.wikipedia.org/wiki/Algorithm) "Starting from an initial state and initial input (perhaps empty),[4] the instructions describe a computation that, when executed, proceeds through a finite[5] number of well-defined successive states, eventually producing "output"[6] and terminating at a final ending state" The "finite" bit I guess is the key thing, that I think was what my lecturer would have been getting at - the canonical bozo sort is not - you could just run for ever, as you might not /ever/ produce a correctly sorted version of the input. That article also points to "randomized algorithms", taking some random input (you could image random input being an RNG seed I guess?). That article does include monte carlo algorithms, which technically could not terminate (Montecarlo simulation of a bouncing photon could technically go for ever) so I am left confused. The lecturer was Prof. Tadao Takaoka, who was great, and apparently (per google) was on the editorial board of the journal Algorithms (http://www.mdpi.org/algorithms/editors.htm http://www.mdpi.org/algorithms/editors.htm)
- shoo 8y agosmall thought experiment: what if we decouple the issue of "finite" from the probabilistic aspect? Perhaps-Algorithm A: step 1: x := sample a value from a roll of a fair D6 step 2: print x Is Perhaps-Algorithm A an algorithm? Can we argue that we're in a well defined state after step 1 has executed? We have some variable x bound to one value from {1, ..., 6}, with a known probability distribution, although we don't know which integer we've got. edit: on the other hand perhaps we're just haggling over definitions here. it is definitely the case that non-terminating algorithms exist and can be useful, and non-deterministic algorithms exist and can be useful. it might be the case that some powerful theory and analysis restricts attention to terminating, deterministic algorithms, it doesnt meant that that's all there is.
- rdlecler1 8y agoTechnically speaking, even physical computers have error rates and are, therefore probabilistic. With large distributions, your mean approaches your expected value -- the same kind of analytical result you get from boolean logic. Similarly, biological systems run on probabilistic algorithms and the fact that two twins starting from the same DNA can be so remarkably similar after millions of steps it a testament to the power of probabilistic algorithms.
- rocqua 8y agoSee [1], which is about the 'complexity class' Bounded-error Probabilistic Polynomial time. Similar to the P=NP conjecture, there is a BPP=P conjecture. Also consider [2], which concerns variations of the Church-Turing thesis. Notably, it mentions probabilistic computation. To answer your original question, indeed probabilistic algorithms are an extension of normal algorithms. One way to make the extension (and retain the property that algorithms give the same output on the same input) is to add a 'random oracle'. [1] https://en.wikipedia.org/wiki/BPP_(complexity) https://en.wikipedia.org/wiki/BPP_(complexity) [2] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Variations https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#V...
- kiriakasis 8y agoFrom a mathematical point of view probabilistic algorithm simply manipulate probability distributions instead of value. The output is a random variable.