Probability of getting every result after n tries

**brokenlugs** · July 19th 2012, 08:13 AM

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.

**Plato** · July 19th 2012, 09:26 AM

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.
$\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 $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.

**brokenlugs** · July 19th 2012, 11:43 AM

Originally Posted by Plato

This part is easy.
$\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 $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!

**Plato** · July 19th 2012, 11:54 AM

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?

**brokenlugs** · July 19th 2012, 12:45 PM

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:
$Pr(X_1=x_1, ... , X_6=x_6)$ such as $\sum_{i=1}^6 x_i = n$ and $x_i\ge1, \forall x_i$

The number of vectors $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 $(-1)^k$ what really confuses me.

**Plato** · July 19th 2012, 01:13 PM

Originally Posted by brokenlugs

$Pr(X_1=x_1, ... , X_6=x_6)$ such as $\sum_{i=1}^6 x_i = n$ and $x_i\ge1, \forall x_i$ The number of vectors $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 $(-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 $\dfrac{\dfrac{n!}{[(x_1)!][(x_2)!][(x_3)!][(x_4)!][(x_5)!][(x_6)!]}}{6^n}$

**brokenlugs** · July 20th 2012, 07:05 AM

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 $1-P(\bigcup_{i=1}^6 A_i)$ , where the event $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 $A_i$ and add them to the inclusion-exclusion formula:

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

Thread: Probability of getting every result after n tries

LinkBack

Thread Tools

Display

Probability of getting every result after n tries

Re: Probability of getting every result after n tries

Re: Probability of getting every result after n tries

Re: Probability of getting every result after n tries

Re: Probability of getting every result after n tries

Re: Probability of getting every result after n tries

Re: Probability of getting every result after n tries

Similar Math Help Forum Discussions

Probability- result of multiple trials

HELP with Probability Result

Given a positive test result, find the probability that test taker has the disease.

how can u get this result?

A result of differentiability

Search Tags