Re: How to prove that a random sort algorithm converges?

In article <1147834161.829694.302560@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>, "Chip Eastham" <hardmath@xxxxxxxxx> writes:

James wrote:
Supposed I want to sort four numbers {5, 2, 4, 3}
I randomly select a pair of two numbers at adjacient poisitions, say i
and i+1, and I swap their position if the value at position i is
greater than the value at position i+1 (e.g., 5 > 2 so swap their
positions).

If I do this (random selection and ordering) long enough, I would
expect that
the numbers are sorted.

My question is: how do I prove that this algorithm converges?

Some terms that may be useful to you in a keyword search are
permutations and transpositions.

Various ways to prove this are possible, some more satisfying
than others. I'll sketch one that is perhaps less satisfying.

You have (say) four numbers. There are only finitely many ways
to arrange them.

Let K count how many pairs of numbers (not necessarily adjacent)
are out of order in the list. If a pair of _adjacent_ numbers are
chosen that are out of order, then they get swapped. When this
occurs, K decreases by exactly one (since every other pair of
numbers remains in the same order in the list as before).

Since K is always decreasing, there is no way that a sequence
of swaps can cycle through the same arrangement more than
once. Since there are only finitely many arrangements, we
must eventually come to an arrangement which does not
allow any further swaps, ie. every pair of adjacent entries is
in order.

One proves by induction that if every pair of adjacent entries
is in order, then the whole list is sorted.

Interestingly, nothing up to this step had assumed transitivity.
So even if we have a "rock paper scissors" ordering, we are still
guaranteed to eventually permute the list into a stable state,
regardless of whether that can be proven to be a sorted state.
.