Imperfect random permutation of 2^k elements

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 04/08/04 

Date: Thu, 08 Apr 2004 22:06:57 +0200

Let me first explain why one would do at all what the title
line says, given that one has available the Algorithm P of
Knuth vol. 2, which is 'perfect'. (1) Nothing is 'practically'
perfect actually. (2) Some degree of imperfection could often
be tolerated or economically justified. (3) The algorithm
(very trivial and containing nothing new/novel!) to be
discussed below has the advantage of being able to directly
utilize a given random bit sequence conveniently (namely
without performing division operations to appropriately derive
from the given random bit sequence real-valued random numbers
in the range [0.0, 1.0) ) and of being flexible enough to
provide any practically desired degree of 'randomness' of the
permutations, though it is, it must be stressed, never
(absolutely) 'perfect'.

Sometime ago I mentioned in a thread that doing the following
'biased' algorithm (A is an array of n elements):

    for i from 0 to n-1 do

      k = next random number in [0,n-1];

      exchange A[i] with A[k];

    od;

twice, once in the forward (as above) and once in the (similarly
done) backward direction, could result in an (imperfect) random
permutation of sufficiently reduced bias, as some experiments
with (albeit very) small values of n showed. This requires about
2n random numbers, which can be directly taken from the given
random bit sequence in case (as we assume throughout, see thread
title) where n is a power of 2 (one uses k bits for each random
number, if n=2^k). Apparently, if one wants to improve the
result, i.e. to further reduce the possibly remaining bias, one
could do a repetition of the operations, which would mean a
requirement of 4n random numbers, etc.

One knows, however, that any permutaion can be transformed
to any other permutation by applying to it a certain permutation
and that any permutation (e.g. the last mentioned) can be
expressed in terms of a number of transpositions (swapping of
elements of pairs of elements). From this one sees that, in
order to generate random permutations, one could apply each
time (i.e. to get from one such to the next) a 'suitable'
number m of random transpositions, i.e. one does the following:

    for i from 0 to m-1 do

      k1 = next random number in [0,n-1];

      k2 = next random number in [0,n-1];

      exchange A[k1] with A[k2];

    od;

This is flexible in the sense that the number of random numbers
used is 2m, where m is arbitrary, while in the previous
algorithm that's 2n (or 4n etc.) where n is fixed, being the
size of the array.

Certainly the very crucial question now is how to judiciously
choose the value of m. I know no 'exact' answer. (I doubt also
that such could be given.) On the other hand, it seems
intuitively clear that, the larger the value of m, the better
will be the result, and that on the other hand no finite value
of m will give (absolutely) perfect result. I 'conjecture' that
a value of m in the range of n to 2n would likely to be o.k.
for practical situations of interest.

It may be noted that the dynamically varying S-box of RC4 is
'akin' (though not identical) to a random permutation generation
as described above with m=1. (BTW, for a variant of RC4 that
changes more than two elements of the S-box in each step, see
a recent thread initiated by me.)

Thanks.

M. K. Shen
---------------------------------------

[General personal notes:]

I may be reached at the e-mail address in the header above.

For the purpose of bandwidth confinement, follow-ups may
under circumstances have to be selectively processed. My
sincere apology in advance to the general readers for any
eventual confusion, inconvenience, etc. resulting therefrom.

Relevant Pages

  • Some PERL code for detecting/displaying "toroidal" trees "invariant under a half-turn
    ... This algorithm will be reviewed by Dr. David Wagner ... Such trees can be termed "invariant" under a half-turn ... not display "the same" oDAG as the first, ... and detects whether this permutation will yield a tree ...
    (sci.math.num-analysis)
  • Re: Challenae question for mathematician
    ... problems relating to permutation groups. ... adjacent books. ... called "bubble sort" - it is a quadratic time algorithm, ... efficient as a sorting method - efficient sorting is O. ...
    (sci.math)
  • Some PERL code for detecting/displaying "toroidal" trees " invariant under a half-tur
    ... This algorithm will be reviewed by Dr. David Wagner ... "oDAGs " invariant under a half-turn. ... Such trees can be termed "invariant" under a half-turn ... and detects whether this permutation will yield a tree ...
    (sci.math)
  • Re: ISO proof of permutation enumeration algorithm
    ... >I'm looking for a proof that the following algorithm indeed enumerates ... >transforming the sequence s *in place*. ... s "visits" each permutation of its original value. ... the continue and break statements in the algorithm instruct ...
    (sci.math)
  • Re: permutations and combinations
    ... > Right now I'm using a string, sorting it and passing it repeated into ... In this article he defines a generic algorithm: ... for_each_permutation calls fn for each permutation of last-first items ... The printing functor keeps a simple state which is just the line number. ...
    (comp.lang.cpp)