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

On Wed, 17 May 2006 21:39:32 -0400, Tim Peters wrote:
[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.

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.

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

In fact, since there can be only a finite number of transpositions, it is
a certainty that the state must converge. 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. 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". All we need is for the
state to become eventually constant, which it certainly does. A constant
sequence of states converges pointwise.

(3) It also appears that saying "the algorithm converges with
probability 1" is better than saying "the algorithm will converge".

Not really, unless _you_ define "convergence" in terms of probability.

Note the difference betweeen "convergence" and "convergence to the sorted
state." The former is a mathematical certainty, while the latter merely
occurs with probability 1.

Consider the sequence "1 3 2 4". In order for the sequence to become
sorted, it is necessary that the middle pair of numbers be selected for
comparison at some point. We cannot prove that this comparison will ever
be selected, but we can show that it will eventually be selected with
probability 1.

However, whether the central pair is ever selected or not, we can say
with certainty that the sequence converges. It may converge to "1 3 2 4"
(which happens with probability 0), or it may converge to "1 2 3 4"
(which happens with probability 1), but it most definitely converges to
*something*.


--
Dave Seaman
U.S. Court of Appeals to review three issues
concerning case of Mumia Abu-Jamal.
<http://www.mumia2000.org/>
.

Relevant Pages

  • Re: convergence of probability measures?
    ... >I have a question about convergence of probability measures that is ... Instead of working with the sequence ... measures for which you have convergence along each fixed row, ... Of course you can impose conditions on triangular arrays to ensure ...
    (sci.stat.math)
  • Re: request for algorithm
    ... >that can be solved by means of N-dimensional iterative algorithms, ... but when using only previous points convergence gives me ... >algorithm ensures convergence. ...
    (sci.math.num-analysis)
  • Re: Convergence of random variables
    ... >When talking about almost sure convergence, do we have to clarify the underlying sample space beforehand? ... Given the probability distributions and independence, ... is called convergence in distribution. ...
    (sci.math)
  • Re: Convergence of random variables
    ... contrast to your original statement. ... Are you confusing almost sure convergence with convergence in *distribution*? ... Convergence in distribution is also called weak convergence; do not confuse it with convergence in measure (also called convergence in probability). ...
    (sci.math)
  • Re: request for algorithm
    ... but when using only previous points convergence gives me ... > discretization compared to a central alternative one, ... > algorithm ensures convergence. ... because by nature the flow of information comes from every ...
    (sci.math.num-analysis)