Random number generators based on permutations can pass the collision test

We investigate pseudorandom number generators (PRNGs) based on random permutations which may be considered as models of block ciphers with randomly chosen keys. A simple method for calculating upper and lower bounds on the collision probability in a finite length output sequence based on the conditional probability bounds of the next symbol to appear after a known prefix was developed. We found that the difference between these upper and lower bounds may be made extremely small for any practical output length. Moreover the collision probability for a true RNG always lies within these bounds. This implies that the investigated generators will pass the collision test, i. e. they are indistinguishable by this test from a true RNG.