# Thread: Probability of getting every result after n tries

1. ## 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.

2. ## Re: Probability of getting every result after n tries

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

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.

3. ## Re: Probability of getting every result after n tries

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?

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!

4. ## Re: Probability of getting every result after n tries

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?

5. ## Re: Probability of getting every result after n tries

Originally Posted by Plato
Have you seen this webpage?
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.

6. ## Re: Probability of getting every result after n tries

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}$

7. ## Re: Probability of getting every result after n tries

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!