# How many random permutations to cover all possible permutations?

I have code that generates a random permutation. In my case, a permutation consists of N binary features, and each of the N features is set or unset randomly. How many times must I generate a random permutation in order to be reasonably assured that I have covered all possible permutations? I'm not sure how to define "reasonably assured" (50%, 95%?).

For example, let's say that N = 10, so there are 1024 possible permutations, how many times should I randomly generate a permutation to be 50% confident that I have generated all 1024 permutations?

It seems to me that this is related to the 36.8% duplicate hit rate when drawing a sample with resampling, but I'm not a statistician.

-
If you have the computing power to generate all permutations (or some well-defined set of re-assignments of the data), why not systematically generate each exactly once? That would normally be far more efficient and give you exact, rather than approximate, answers. (This idea is identical to the difference between sampling a small finite population with and without replacement: why sample with replacement when you can obtain a complete census and eliminate all sampling error?) –  whuber Oct 11 '12 at 21:28
My goal is not to generate all permutations, but rather to find a way to quantify how "good" a randomly generated sample is. –  Tyro Oct 11 '12 at 22:59
Huh? If you can exhaustively generate all permutations, then you can answer any question of that sort with perfect accuracy. Generating, and re-generating, far more permutations than you need is just a complete waste of computing time and will give you less accurate answers. –  whuber Oct 12 '12 at 14:29

Permutation usually refers to something else, so it's probably better to call your problem "random binary words" or something similar.

The question of how long it takes to get at least one representative of each type is called the Coupon Collector Problem. If you assume that all binary words of length $N$ are equally likely, then there are $2^N$ types of coupons. You can write the time to collect all coupons as a sum of the times to collect the $i$th new coupon, a sum of independent geometric random variables. So, the expected number of coupons it takes to collect them all is $2^N \sum_{i=1}^{2^N} 1/i \sim 2^N \log 2^N$, or more precisely $2^N \log 2^N + 2^N \gamma + 1/2 + o(1)$. For $N=10$ this is about $7689$. The variance is $2^{2N} \sum_{i=1}^{2^N} 1/i^2 \approx 2^{2N} \frac {\pi^2}{6}$, so the standard deviation is about $2^N \frac{\pi}{\sqrt{6}}$. For $N=10$ this is about $1313$. Note that a normal approximation is NOT appropriate here.

One crude bound is Chebyshev's inequality, which says that the chance that a random variable is more than $k$ standard deviations away from the mean is at most $1/k^2$, and the similar Cantelli's inequality is that the chance that a random variable is at least $k$ standard deviations above the mean is at most $1/(k^2+1)$. This gives you an upper bound of about $7689 + 1313 \approx 9002$ for the median, and $7689 + 1313\sqrt{19} \sim 13412$ for the $95$th percentile.

If these bounds are not good enough, there are more precise but more complicated asymptotics known. Another approach, suitable perhaps up to $N = 25$, is to compute the exact distribution numerically using the representation as a sum of independent geometric distributions.

-
I don't follow where the sqrt(19) came from for the bound for the 95th percentile. –  Tyro Oct 11 '12 at 23:28
If $k=\sqrt{19}$ then $1/(k^2+1) = 1/20 =5\%$. So, Cantelli's lemma says that the probability that the result is at most $\sqrt{19}$ standard deviations above the mean is at least $95\%$. –  Douglas Zare Oct 11 '12 at 23:58
Thanks for the clarification. –  Tyro Oct 12 '12 at 0:08