Probability of choosing subset of already previous chosen unique objects over time In this question I asked about the chance of choosing the same unique objects over time without replacement, and it reduced to the Birthday Problem (collision probability).
But I realized after that the question I really wanted to answer was:
What is the probability that the unique objects I choose in a round are a subset of all the unique objects I've chosen in previous rounds?
From my computer simulation it seems this is much more likely, with a collision by the 240th round with 4096 unique objects and choosing 8 per round. Intuitively to me this seems quite early, but there could be an error in my simulation.
 A: To restate the question, we have 4096 objects, and we draw 8 objects at a time, without replacement.  After each draw the 8 objects are replaced.  We would like to know the probability that on the nth draw all 8 objects have been previously drawn.
In order to simplify notation, let's suppose that on the nth draw, the objects drawn are numbers 1 through 8.  Let's say the nth draw has "property $i$" if object $i$ has not been drawn in any of the previous $n-1$ draws, for $i=1,2,3,\dots,8$.  We will use the Principle of Inclusion / Exclusion (PIE) to compute the probability that the final draw has none of the properties, i.e. all of the objects $1,2,3, \dots ,8$ have been previously drawn.  Let $S_i$ be the total probability that the final draw has $i$ of the properties, for $i=1,2,3, \dots ,8$.  Then
$$\begin{align}
S_1 &= \binom{8}{1} \left( \frac{\binom{4095}{8}}{\binom{4096}{8}} \right)^{n-1} \\
S_2 &= \binom{8}{2} \left( \frac{\binom{4094}{8}}{\binom{4096}{8}} \right)^{n-1} \\S_3 &= \binom{8}{3} \left( \frac{\binom{4093}{8}}{\binom{4096}{8}} \right)^{n-1} \\
&\dots \\
S_8 &= \binom{8}{8} \left( \frac{\binom{4088}{8}}{\binom{4096}{8}} \right)^{n-1} 
\end{align}$$
By PIE, the probability that all  8 objects have been previously drawn is
$$p_n = 1 - S_1 + S_2 - S_3 + \dots +S_8$$
If we define a "success" as a draw in which all the objects drawn have been previously drawn, then the probability of a success on the 240th draw is
$p_{240} = 0.000373546$, and the expected number of successes in draws 2 through 240 is 
$$\sum_{n=2}^{240} p_n = 0.0121255$$
