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.
 A: 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.
