# Probability of Repeats in Successive Combinatorial Selections

I'm not even sure if the title is an apt description of the problem, but here it goes: Suppose you have 400 unique items, and you are to select a combination of 10 distinct items at at time. You do this multiple times. What is the probability that your second set of 10 items contains a repeated item from your first set of 10 items? What is the probability any of the items in the third set contains a repeat from any of the previous selections? What about the Nth set?

A scenario would be if you are a tutor trying to create 10-question quizzes for your students by selecting 10 random questions out of a collection of 400 test questions. What is the chance that your students will see a repeated question on their Nth quiz?

Suppose each item has an equal chance of being selected.

Let $X_i$ denotes the number of items selected in the $i$-th trial that has already been selected in the $(i-1)$-th trial. Trivially, $P(X_1=0)=1$.

For the second trial we have \begin{align} P(X_2=0)&=\frac{390 \cdot 389\cdot 388\cdot 387\cdot 386\cdot 385\cdot 384\cdot 383\cdot 382\cdot 381}{400 \cdot 399\cdot 398\cdot 397\cdot 396\cdot 395\cdot 394\cdot 393\cdot 392\cdot 391}\\ &=\frac{390!}{380!}\cdot\frac{390!}{400!}\\ P(X_2=1)&={10 \choose 1} \frac{390 \cdot 389\cdot 388\cdot 387\cdot 386\cdot 385\cdot 384\cdot 383\cdot 382\cdot 10}{400 \cdot 399\cdot 398\cdot 397\cdot 396\cdot 395\cdot 394\cdot 393\cdot 392\cdot 391}\\ &={10 \choose 1}\cdot\frac{10!}{9!}\cdot\frac{390!}{381!}\cdot\frac{390!}{400!}\\ P(X_2=2)&={10 \choose 2} \frac{390 \cdot 389\cdot 388\cdot 387\cdot 386\cdot 385\cdot 384\cdot 383\cdot 10\cdot 9}{400 \cdot 399\cdot 398\cdot 397\cdot 396\cdot 395\cdot 394\cdot 393\cdot 392\cdot 391}\\ &={10 \choose 2}\cdot\frac{10!}{8!}\cdot\frac{390!}{382!}\cdot\frac{390!}{400!}\\ &\vdots\\ P(X_2=r)&={10 \choose r}\cdot\frac{10!}{(10-r)!}\cdot\frac{390!}{(380+r)!}\cdot\frac{390!}{400!}\\ \end{align}

Now for the higher order trials things will get really complicated because it will be conditional on the number of repeated items from previous trials.

Let $R_i$ denotes the number of items that are yet drawn by the $i$-th trial. $$R_1=400-10+0=390$$ $$R_2=R_1-10+X_2$$ $$\vdots$$ $$R_i=R_{i-1}-10+X_i$$

$$P(X_i=r \mid R_{i-1}=k)={{400-k} \choose r}\cdot\frac{(400-k)!}{(400-k-r)!}\cdot\frac{k!}{(k+r-10)!}\cdot\frac{390!}{400!}$$

You can find the probability $p$ that $X_1=X_2=\ldots=X_{N-1}=0$ so that $R_{N-1}=390$ then find $P(X_N=0 \mid R_{N-1}=390)$ and $P(X_N=0 \mid R_{N-1}=390)$. The probability the students will not see a single repeated question up until the $N$-th quiz will be $p \cdot P(X_N=0 \mid R_{N-1}=390)$. This probability is in fact quite simple since it is just $$\left(\frac{390!}{380!}\cdot\frac{390!}{400!}\right)^N$$ but other required probability will likely has to be done step by step.

If anyone can simply the expression further please feel free to add on.