Minimal number of trials

Question

How many trials would you need to roll a die so that the probability of getting one of each number is greater than half?

My Solution:

We want it so that after $n$ rolls, we have at least one of each number. We can use the stars and bars method here, where we have $n$ stars and $5$ dividers.

For example, the following sequence represents scoring exactly one of each number, except the number "6", which is scored three times.

$$\star | \star | \star| \star|\star| \star\star \star$$

However, to guarantee that we always have one of each type, we need the following two conditions.

1. The bars cannot be together, because if they were then that means that there is a number that was not rolled.

2. No bars can be at the ends.

Now, there are $n$ stars, which means $n-1$ gaps excluding the end-gaps. Place the five dividers there, so $\binom{n-1}{5}$. Since this is a probability, we can divide by the total number of outcomes, which is $6^n$. Hence, the probability is the quotient, and then we can use whatever program to give approximate solutions.

Am I even close here? My gut feeling is telling me to look at a binomial distribution but again this could be way off.

Answer 1

There is a fairly simple recursive way to do the problem...

Let $p_i(n)$ be the probability that you have thrown exactly $i$ different values in $n$ tosses. Then $$p_i(n+1)=\frac {i}6\times p_i(n)+\frac {7-i}6\times p_{i-1}(n)$$

That expression makes it relatively easy to compute $p_6(n)$ numerically and we get $$p_6(13)=0.513858194$$

as the first value greater than $.5$

I don't immediately see a quick analytic way to solve it.

Answer 2

The solution obtained by counting, that is, the number of ways of getting all $6$ numbers in a series of tosses divided by the total number of outcomes of the series is long and intricate. If I use lulu's solution of $13$, then..........

$$p(13) = \frac{\text{ways of getting all 6 numbers}}{6^{13}}$$

$$\frac{[\frac{13!}{8!}\cdot 6]+[\frac{13!}{7!2!}\cdot 30]+[\frac{13!}{6!3!}\cdot 30]+[\frac{13!}{5!4!}\cdot 30]+[\frac{13!}{6!2!2!}\cdot 60]+[\frac{13!}{5!3!2!}\cdot 120]+[\frac{13!}{4!4!2!}\cdot 60]+[\frac{13!}{4!3!3!}\cdot 60]+[\frac{13!}{5!2!2!2!}\cdot 60]+[\frac{13!}{4!3!2!2!}\cdot 180]+[\frac{13!}{3!3!3!2!}\cdot 60]+[\frac{13!}{4!2!2!2!2!}\cdot 30]+[\frac{13!}{3!3!2!2!2!}\cdot 60]+[\frac{13!}{3!2!2!2!2!2!}\cdot 6]}{6^{13}}$$ $$= .513858$$