0
$\begingroup$

Title states an example, I'll give the general case question then repeat an example. I have N images and plan to randomly pick k of the possible N images into a set. The order does not matter. I repeat for T trials. What is the chance that any of the k-image sets are repeated at least once across the T trials? More specifically, I have 20 images and plan to randomly pick 10 of the possible 20 images into a set. The order does not matter. I repeat this for 100 trials. What is the chance that any 10-image sets are repeated at least once across the 100 trials?

I realize this is similar to the Birthday problem, however I believe in that problem N equals T. Could be wrong...

1 Answers 1

0

Let $M = {N \choose k}$, the number of possible $k$-image sets. There are $M!/(M-T)!$ possible sequences of $T$ distinct sets, and $M^T$ possible sequences if they don't have to be distinct, so the probability of no repetitions is $\dfrac{M!}{(M-T)! M^T}$, and the probability of at least one repetition is $1 - \dfrac{M!}{(M-T)! M^T}$.

In your example with $N=20$, $k=10$, $T=100$, $M = 184756$ and the probability of at least one repetition is approximately $.02644105288$.