0
$\begingroup$

I want to compare in a practical sense two methods of random permutations -- one theoretically perfect, namely that of Fisher and Yates, and another ad hoc, let's call it X. A way of comparison I could think of is the following:

One starts from the standard configuration of n objects [0, 1, 2, ...., n-1] and apply each method a fairly large number of times successively to permute them and each time one computes the Hamming distance of the result from the standard configuaration. One obtains thus the frequency distribution of the Hamming distances for each method. If these are fairly comparable to each other, then X could be practically employed in place of the theoretically perfect one.

Is this line of thought of mine correct? Does anyone have an idea of a better method of comparison? Thanks in advance.

$\endgroup$
5
  • 1
    $\begingroup$ What's wrong with the Fisher-Yates algorithm? $\endgroup$ May 8, 2013 at 12:35
  • $\begingroup$ It's theoretically perfect, but it requires for n objects n-1 (pseudo-)random numbers. I desire to reduce the amount of random numbers needed and hopefully also the runtime threby. Of course, that would in any case be a compromise in practice, if successful (according to the No Free Lunch Principle). $\endgroup$ May 8, 2013 at 21:07
  • 1
    $\begingroup$ Can you explain in what kind of situation the Fisher-Yates algorithm is too slow? If you're pressed for speed, use a faster PRNG. $\endgroup$ May 8, 2013 at 21:25
  • $\begingroup$ Well, I am afraid not being able to answer your question satisfactorily, for I would have to refer to the method X which is however yet very premature and my OP is in fact meant to check whether it could be useful at all. Anyway, if X requires far less number of random numbers than Fisher-Yates, then I suppose it is conceivable that X (assuming also that it's code is efficient) could run faster. $\endgroup$ May 8, 2013 at 21:53
  • $\begingroup$ I have recently coded a practical alternative of the method of Fisher & Yates and compared the two methods on the basis of Hamming distance as stated above, see s13.zetaboards.com/Crypto/topic/7071388/1 $\endgroup$ Jun 24, 2013 at 21:43

1 Answer 1

1
$\begingroup$

Your method of comparison is very easy to defeat. I assume that by "Hamming distance from the regular configuration" you mean the number of fixed points. Make a table of the number of permutations in $S_n$ having $k$ fixed points (this can be computed recursively), and fix a single permutation with $k$ fixed points for every $k$. This way you can sample a permutation in a ways that matches this particular statistic of random permutations, but probably performs rather differently compared to a truly random permutation.

$\endgroup$
1
  • $\begingroup$ Sorry for my poor knowledge (I don't understand what fixed points mean in the current context). In OP I wrote the "standard configulation", meaning the list [0, 1, 2, ... n-1] that one starts with. During repeated application of the algorithms one computes the Hamming distance at each step relative to that configulation. $\endgroup$ May 8, 2013 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.