How many dice do you have to roll to get your odds of seeing each face at least once equal to 0.5? In a pub the owner is throwing a number of dice simultaneously. "I am trying to get one of each of the six faces", he says, "But it hasn't happened yet". "No", I said "You need at least four more dice to make the odds in favour of such a thing" How many dice does the owner have?
That is, i'm trying to find a general equation in N, the number of dice thrown,to the probability of getting at least one of each face. Its proving much harder than anticipated, I come up with a form of equations but they would require looping upon looping as n increases and I'm struggling to code it. I'm sure I'm missing something and I would love to know if there is a general solution which you could use to find the number of dice that would give you odds of 0.5, from which you could simply subtract four.
 A: The easiest way to attack this is probably to consider the set of possible sequences of rolls (i.e. we order the dice and read off the rolls in some specific way, so there are $6^N$ possible outcomes) and to then consider the set $S_n$, the set of sequences not using the $n^{th}$ face of the die. It's fairly clear that
$$|S_n|=5^N$$
since we simply must choose any sequence of the other five faces. However, we have to use the inclusion-exclusion principle to find the size of $S_1 \cup S_2 \cup S_3 \cup S_4 \cup S_5\cup S_6$, but this is easy enough, since we can calculate the size of the intersection of any pair of sets as
$$|S_a \cap S_b|=4^N$$
So, in total, there are $\binom{6}{2}=15$ overlapping pairs of sets. However, triples overlap too and
$$|S_a \cap S_b \cap S_c| = 3^N$$
and there are $\binom{6}{3}=20$ overlapping triples. Essentially, when all is said and done, we can continue this pattern and apply the inclusion-exclusion principle to get that the size of the union of the $S_n$ is:
$$\binom{6}{1}5^N-\binom{6}{2}4^N+\binom{6}{3}3^N-\binom{6}{4}2^N+\binom{6}{5}1^N-\binom{6}{6}0^N$$
the complement thereof having size
$$\binom{6}{0}6^N-\binom{6}{1}5^N+\binom{6}{2}4^N-\binom{6}{3}3^N+\binom{6}{4}2^N-\binom{6}{5}1^N+\binom{6}{6}0^N$$
and, after simplification, and dividing by $6^N$, the probability of every face being used is
$$\frac{6^N-6\cdot 5^N + 15 \cdot 4^N - 20 \cdot 3^N +15 \cdot 2^N - 20}{6^N}.$$
In general, if "dice" is replaced by "uniform distribution on $k$ discrete values", the probability of seeing every value at least one from a sample of $N$ values is
$$\frac{\sum_{i=0}^k (-1)^i\binom{k}{i}(k-i)^N}{k^N}$$
I doubt there's any nice closed form for when this surpasses a probability of $\frac{1}2$, but it's easy enough to do by computation.
