[robinhouston]

Bogosort terminates with probability 1. Is it really reasonable to say it doesn’t guarantee termination? People often do say that about randomised algorithms, which confuses me a little. Probability 1 is as guaranteed as anything probabilistic can reasonably hope to be, isn’t it?

[Edited to add: thanks for the replies. I think I expressed myself poorly here. It’s not that I don’t understand the difference between “with probability 1” and “always”. What I mean is that I don’t understand why people sometimes make a big deal out of it, and say “that algorithm is not even guaranteed to terminate” as though that somehow means the algorithm is untrustworthy or useless. The trouble with the game “roll a die until you get 100 sixes in a row” is that it has an astronomical expected running time – not that it might _never_ end, but that it will almost certainly take a very long time.]

[vog]

Probability 1 is as guaranteed as anything probabilistic can reasonably hope to be, isn’t it?

Unfortunately, it isn't. This is the reason why in mathematics, we say that "possibility 1" means that an event is "almost sure", which is different from a "sure" event.

For instance, you can play a game where you roll a dice over an over again. You win if you get 100 times a 6 in sequence. If you play this game without any time limit, your possibility to win is exactly 1, which means that you can be "almost sure" you'll win in the end. However, you can't be sure, because there is still the possibility that you don't get 100 times a 6 in an eternity.

Note that this only happens in infinite probability spaces. In finite spaces, "almost sure" and "sure" are equivalent.

Also note that the same holds for "probability 0" which means "almost impossible", not to be confused with "impossible".

[nhaehnle]

Your example is misleading, because the same can be said about the game where you roll a dice over and over again, and you win if you get a 6.

The probability that the game ends is 1, but it is not guaranteed to end. Yet no reasonable person will worry about this in practice.

Your example with 100 times 6 in a row is conceptually exactly the same, just the expected time until the game terminates is much, much larger.

[btilly]

Bogosort terminates with probability 1. Is it really reasonable to say it doesn’t guarantee termination?

Yes.

Particularly when done on real machines that use pseudo-random numbers that will repeat in finite time. For instance many use http://en.wikipedia.org/wiki/Mersenne_twister with a version that will repeat after 2^19937-1 steps. With a random array of 2500 elements, the odds are very good that bogosort will fall into a loop before it has successfully sorted the array.

[Retric]

I think that depends on how you cycle the numbers. If you use the new positions as part of the randomization process then the average cycle time becomes much larger than 2^19937-1.

AKA: (Ignoring the fact it takes more than one number to shuffle a deck). After the first cycle of 2^19937-1 you have ~1 in (2500!) that you repeat the initial position. After the second cycle it's ~2 in (2500!) etc. It may be possible that your odds of success are around (2^19937-2)/(2^19937-1).

[btilly]

Of course how you cycle the numbers matters. I assumed that you take the original deck and keep on coming up with random shuffles of it. If so, then your cycle time will be the cycle time of the algorithm times (worst case) the length of the array. However if you do the obvious trick of doing each random shuffle to the previously shuffled deck, then the cycle time for the permutations to repeat becomes much, much longer - long enough that you are very, very likely to hit sorted at some point. But it is possible that you won't. And if you hit the case where you won't, then you'll absolutely never terminate.

[unignorant]

There is a distinction between "surely" and "almost surely":

http://en.wikipedia.org/wiki/Almost_surely

Bogosort almost surely terminates.

[perlgeek]

If you talk about O(something(n)) run times there's an implicit agreement that you are talking about worst case behavior.

And the worst case of bogosort is not to terminate.

[cdavid]

Not sure about that: qick sort is generally said to be O(NlogN), but its worst case is O(N^2) (the simple implementation anyway).

[sesqu]

That's an abuse of notation. Quicksort is expected O(N log N), where the expectation is usually over a uniform distribution of all permutations.

The actual notation for proportional asymptotic dominance of expectation is too convoluted for use, so people just don't use one. But to even leave out the word "expected" is just plain wrong.