Probability of getting every result after n tries

Hello,

I need to determine a probability for some work related to my Master Thesis. It may seem really easy but I've been trying for the last two days and I couldn't get any solution:

Imagine that we roll **n**** times** a **6-sided die**. What's the **probability** of **getting each result **(*1, 2, 3, 4, 5, 6*) at least **once**?

Note: *n* should be greater than 6 (or equal), to have a probability greater than zero.

Given the number of times we get every result, we can calculate the probability using a multinomial distribution. For *n=6* or even for *n=7* the solutions are easy, but as* n* gets bigger the possibilities grow really fast, so it doesn't seem feasible to use combinations of multinomials. Since the problem seems really easy, I was wondering if there is a simple solution for this.

Thanks a lot.

Re: Probability of getting every result after n tries

Quote:

Originally Posted by

**brokenlugs** Imagine that we roll **n**** times** a **6-sided die**. What's the **probability** of **getting each result **(*1, 2, 3, 4, 5, 6*) at least **once**?

Note: *n* should be greater than 6 (or equal), to have a probability greater than zero.

This part is easy.

$\displaystyle \sum\limits_{k = 0}^5 {{{\left( { - 1} \right)}^k}{{\binom{6}{6-k}\left( {\frac{{6 - k}}{6}} \right)}^n}} $ That is the probability of each value appears at least once in $\displaystyle n$ trials

Quote:

Originally Posted by

**brokenlugs** Given the number of times we get every result, we can calculate the probability using a multinomial distribution. For *n=6* or even for *n=7* the solutions are easy, but as* n* gets bigger the possibilities grow really fast, so it doesn't seem feasible to use combinations of multinomials. Since the problem seems really easy, I was wondering if there is a simple solution for this.

I don't know exactly what that means.

Re: Probability of getting every result after n tries

Quote:

Originally Posted by

**Plato** This part is easy.

$\displaystyle \sum\limits_{k = 0}^5 {{{\left( { - 1} \right)}^k}{{\binom{6}{6-k}\left( {\frac{{6 - k}}{6}} \right)}^n}} $ That is the probability of each value appears at least once in $\displaystyle n$ trials

Wow, thank you very much!! This is what I was looking for! I wasn't even close to that. For a more general result, i.e. an experiment with *j* equiprobable possible results, I guess I just have to replace the *6* for a *j* and the *5* for a *j-1*. Am I wrong?

Quote:

Originally Posted by

**Plato** I don't know exactly what that means.

I meant that if I had to determine the probability of getting a 1 twice, a 2 three times, a 3 once, and so on (whichever combination I want), I could do that with a multinomial distribution, but looks like I was really far from getting a feasible result.

Just for curiosity, is that formula the probability mass function of any known distribution? Does it have any name? I am that kind of person that likes to understand everything, but looks like this formula may be out of my possibilities.

Thank you!

Re: Probability of getting every result after n tries

Quote:

Originally Posted by

**brokenlugs** Wow, thank you very much!! This is what I was looking for! I wasn't even close to that. For a more general result, i.e. an experiment with *j* equiprobable possible results, I guess I just have to replace the *6* for a *j* and the *5* for a *j-1*. Am I wrong?

I meant that if I had to determine the probability of getting a 1 twice, a 2 three times, a 3 once, and so on (whichever combination I want), I could do that with a multinomial distribution, but looks like I was really far from getting a feasible result.

Just for curiosity, is that formula the probability mass function of any known distribution? Does it have any name? I am that kind of person that likes to understand everything, but looks like this formula may be out of my possibilities.

Have you seen this webpage?

Re: Probability of getting every result after n tries

Quote:

Originally Posted by

**Plato**

Yes, that's where I learned what a multinomial distribution is, and I think I understand it.

This probability I wanted to get, if I'm not wrong, can also be obtained as a summatory of all the probabilities we can get with the multinomial distribution:

$\displaystyle Pr(X_1=x_1, ... , X_6=x_6)$ such as $\displaystyle \sum_{i=1}^6 x_i = n$ and $\displaystyle x_i\ge1, \forall x_i$

The number of vectors $\displaystyle x=(x_1, ... , x_6)$ that can be written following that condition grows a lot when *n* grows, so calculating the summatory of all those probabilities may be not feasible for large values of *n*, that's why I was asking for a easier solution.

However, I can't seem to find the relation between your formula and the multinomial distribution. Actually, is that $\displaystyle (-1)^k$ what really confuses me.

Re: Probability of getting every result after n tries

Quote:

Originally Posted by

**brokenlugs** $\displaystyle Pr(X_1=x_1, ... , X_6=x_6)$ such as $\displaystyle \sum_{i=1}^6 x_i = n$ and $\displaystyle x_i\ge1, \forall x_i$ The number of vectors $\displaystyle x=(x_1, ... , x_6)$ that can be written following that condition grows a lot when *n* grows, so calculating the summatory of all those probabilities may be not feasible for large values of *n*, that's why I was asking for a easier solution. However, I can't seem to find the relation between your formula and the multinomial distribution. Actually, is that $\displaystyle (-1)^k$ what really confuses me.

The formula I gave you has little to do with multinomial distribution. Rather it is using inclusion/exclusion: read this page.

The new posting has probability $\displaystyle \dfrac{\dfrac{n!}{[(x_1)!][(x_2)!][(x_3)!][(x_4)!][(x_5)!][(x_6)!]}}{6^n}$

Re: Probability of getting every result after n tries

Quote:

Originally Posted by

**Plato** The formula I gave you has little to do with multinomial distribution. Rather it is using inclusion/exclusion:

read this page.

Thanks again for this information! I was able to get the same formula as you, so I understand everything now. The probability I was looking for was $\displaystyle 1-P(\bigcup_{i=1}^6 A_i)$, where the event $\displaystyle A_i$ means that after rolling the dice *n* times, we didn't get the *i-th* side. Then, it's easy to calculate the probabilities of the intersections of the different $\displaystyle A_i$ and add them to the inclusion-exclusion formula:

$\displaystyle 1-P(\bigcup_{i=1}^6 A_i) = 1 - \sum_{k=1}^6 (-1)^{k-1}\binom{6}{k}\left( \frac{6-k}{6}\right)^n = \sum_{k=0}^5 (-1)^k \binom{6}{k} \left( \frac{6-k}{6} \right)^n$ which is your result.

Thank you very much!