Comment by danvet

Actually this is about one of the first things you learn in in a probability theory course, and the probability that bogosort completes in finite time is 1.

Now of course, there's infinitely many conceivable scenarios where bogosort never completes, but it doesn't matter. The theoretical foundation (Lebesgue measure theory) to make this mathematically rigid is a bit complex. An example to illustrate:

Assume you have're looking at a 2-dimensional space (over the real numbers) and you want to measure the area of subsets of it. E.g. the area of a square defined as:

{ (x,y) \in \R | 0 <= x <= 1 and 0 <= y <=1 }

Now the area of that is 1. Then carve out the y-axis like this:

{ (x,y) \in \R | 0 < x <= 1 and 0 <= y <=1 }

It's obviously a smaller set than the square above, but the set that's missing doesn't have any area (it's a line with no width). So it's sane to assume that the area of the new subset is still 1.

[btw: Lebesgue measure theory throws in a few more simple assumption and then derives a very nice theory for computing areas, and in extension integration of functions.]

Now probabilities are the same: Instead of points in the plane you have different runs of bogosort and the measure of the "area" for all events is defined to be 1. But you still can carve out complete "lines" (i.e. sets with even infinte many different runs of bogosort) that don't have any influence on the value of your total "area", i.e. probability.

To conclude, your in /pratice/ actually holds up in theory, too ;-)

Edit: Lebesgue measure is actually only the application onto real spaces, the fundamental thing that also applies to probabilities is just called measure theory. Mixed that up a bit.