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

[James]
Thanks to all who contributed in one way or another.
Although I will need sometime to digest your suggestions, there are a
few things I learn at the moment:

(1) There are more than one way to prove the algorithm.

[Tim Peters]
That's true. The way I suggested is the easiest of all those I saw,
although it also gives the least information.

(2) It appears that saying "the algorithm converges is not precise
enough". We need to define what is the convergence criterion.

Well, "converges" has no conventional meaning here at all, so you have to
define what you mean. Convergence usually applies to iterative numerical
algorithms, such as talking about how quickly a root-finding algorithm
can be expected to converge to a root to within a given tolerance.


[Dave Seaman]
What's wrong with pointwise convergence? It looks like a perfectly
standard example of convergence to me.

Primarily because I think it's non-responsive. The OP said "I am not a
maths person", and I think it's obvious (although I may be wrong) that he
only cares about whether he'll reach the sorted state.

In fact, since there can be only a finite number of transpositions, it is
a certainty that the state must converge.

The number of transpositions needed is the number of inversions, which is
why I pushed him toward reasoning about inversions.

However, we need to allow for the possibility of convergence to something
other than the sorted state, since a needed comparison might never be
made.

As above, I fear that gets into weeds the OP doesn't want to visit ;-)

The probability of this happening is 0, but it is nonetheless possible.
The distinction between "convergence" and "convergence to the sorted
state" is one that I overlooked previously.

It appears that what you want to know is whether your algorithm
_terminates_, but there was no termination criterion given. People are
reasonably guessing that you intend for your algorithm to terminate
when the list reaches a wholly sorted state.

It's not necessary to speak of "termination".

Neverthless I believe it's most _helpful_ to the OP to do so (under the
belief that when he said "how do I prove that this algorithm converges?" he
_meant_ ""how do I prove that this algorithm reaches the sorted state?").

All we need is for the state to become eventually constant, which it
certainly does. A constant sequence of states converges pointwise.

As above, I doubt the OP cares about that possibility (although I agree he
needs to understand it-- if only vaguely --in order to grasp why no upper
bound can be given for the number of steps needed to reach the sorted state
whenever the start state has at least 3 elements and at least 1 inversion).

...


.