# Are probabilisitc algorithms deterministic?

I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness?

Initially, I thought only algorithms outputting random numbers are called probabilistic. They are obviously non-deterministic.

However, what about the following algorithm: Take BubbelSort and randomly decide whether to start sorting from left to right or from right to left. If you modify the sorting order, the algorithm is deterministic, because small values will always be on the left and great values on the right side (or vice versa). As there is some randomness in the algorithm, do we call this algorithm probabilistic?

In short: Any algorithm using some randomness is called probabilistic. Is that correct? However, this term has nothing to do with determinism and non-determinism. Is that correct?

• "probabilistic algorithm" isn't really a well-defined term, it's more colloquial. I think no one would call you out on this usage but I'm not sure it's standard. I'd like to point out that determinism and nondeterminism are however well defined. Their definitions come in two flavors. One flavor is that the same input will produce the same output. Another flavor has to do with automata and Turing machines which always produce the same result but can execute many branches at the same time. Your bubble sort example uses randomness but is deterministic. – Jake Dec 4 '17 at 8:31
• This means that my bubble sort example is deterministic and probabilistic as well? – null Dec 4 '17 at 8:42
• My claim is that there is no authority on whether or not your algorithm is probabilistic or not because this quibble over definition is not one that matters in practice. I think calling your example "random" or "probabilistic" is perfectly fine but it's not as if it's right either. – Jake Dec 4 '17 at 8:45
• – Yuval Filmus Dec 4 '17 at 8:59