Calculating Probability of Sixth Die Face on Nth Consecutive Throw

[LittleWolf]

Does anyone know how to determine the probability that the sixth side of a fair die will appear on the Nth consecutive throw.

 

[SpaceTiger]

I suggest you sit down and try to reason this through, but it's just

P(N)=\frac{1}{6^N}

 

[LittleWolf]

The problem I was trying to ask was " You throw a die until all six faces have shown up and then you stop." What is the probability that you stop on the Nth throw. I believe that P(N=6)=6!/(6^6) and P(N<6)=0 but I am confused about the probability of stopping for N>1.

 

[Hurkyl]

I don't expect that to have a simple answer. It's easy enough to answer:

"What is the probability of getting u 1's, v 2's, w 3's, x 4's, y 5's, and z 6's in N (= u+v+w+x+y+z) throws"

But then to get the answer to your problem, you have to add up a lot of individual cases.

 

[BicycleTree]

Counting the number of ways that all the faces can come up on n rolls is the same as counting the number of onto functions from {1, 2, ... n} to {1, 2, 3, 4, 5, 6}, since each time you roll the die you effectively map the number of the roll to one of the faces on the die.

 

[BicycleTree]

There is a formula for counting the number of onto functions.

 

[CRGreathouse]

I think a good strategy would be counting the number of ways to get at least 1 of each of 5 numbers in N-1 throws and exactly 0 of the last. This way order doesn't matter, which simplifies the problem (I think/hope). This should be exactly six times P(N).

 

[CRGreathouse]

Musing aloud

Let F_k(n) represent the number of ways a die with k equiprobible faces can land once on all but one faces at least once, with the last face never coming up, out of n+k-1 throws. Clearly the probability of the desired event is P(n)=\frac{F_6(n-6)}{6^n} as long as n>=6.

F_6(0)=6\cdot5!, since there are 5! ways for the 5 objects to be chosen once each, and 6 ways to choose which element is last. This brings us to P(6)=6!/6^6=5/324, as LittleWolf pointed out.

In fact, in general F_k(0)=\frac{k!}{k^k}, since each of the faces other than the last must be landed on exactly once.

F_2(n)=2, since either all the results are 1 or all the results are 2.

F_3(n)=3\left(\sum_{l=1}^{n+1}{n+2\choose l}\right)=3\left(\sum_{l=0}^{n+2}{n+2\choose l}-{n+2\choose0}-{n+2\choose n+2}\right)=3\left(2^{n+1}-2\right)

Is there some good pattern, or some Bell-related OEIS sequence I'm missing here?

 

[BicycleTree]

I said there was already a formula for counting the number of onto functions. Given that LittleWolf was asked the problem, he probably already has that formula. I looked it up and this is it, using ^ for exponentiation and C(a, b) for "a choose b":

The number of onto functions from a set of size m to a set of size n is equal to the sum for i = 0 to n of ((-1)^i * C(n, i) * (n - i)^m).

So to find the answer to LittleWolf's question, you substitute N for m and 6 for n in that expression.

 

[CRGreathouse]

The number of onto functions from a set of size m to a set of size n is equal to the sum for i = 0 to n of ((-1)^i * C(n, i) * (n - i)^m).

So to find the answer to LittleWolf's question, you substitute N for m and 6 for n in that expression.

First: Thanks for the formula, I couldn't think of that one. Actually, I'm not sure if I even knew of it before... it looks vaguely familliar, but no more. If you don't mind I'll \TeX it so I can follow it a little better...

\sum_{i=0}^{n}(-1)^i{n\choose i}(n-i)^m=\sum_{i=0}^{n-1}(-1)^i{n\choose i}(n-i)^m

\sum_{i=0}^{6}(-1)^i{6\choose i}(6-i)^N= {6\choose 0}6^N-{6\choose 1}5^N+{6\choose 2}4^N-{6\choose 3}3^N+{6\choose 4}2^N-{6\choose 5}= 6^N-6\cdot5^N+15\cdot4^N-20\cdot3^N+15\cdot2^N-6

OK... this is the number of ways to have all 6 faces show up by the Nth turn. The probability of it turning up on the Nth turn is then
P(N)=6^{-N}\left((6^N-6\cdot5^N+15\cdot4^N-20\cdot3^N+15\cdot2^N-6)-(6^{N-1}-6\cdot5^{N-1}+15\cdot4^{N-1}-20\cdot3^{N-1}+15\cdot2^{N-1}-6)\right)

Right?

 

[BicycleTree]

Looks right to me.

I think the reason it might be familiar to you is that (so says my book) the summation is a Stirling number of the second kind, S(m, n), multiplied by n!.
http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
The Stirling numbers count the number of ways to divide a set of size m into n nonempty sets, so to count functions you want to have the order of the n sets important so you multiply by n!.

 

[CRGreathouse]

Looks right to me.

I think the reason it might be familiar to you is that (so says my book) the summation is a Stirling number of the second kind, S(m, n), multiplied by n!.

I thought that Stirling numbers (of the second kind; I've never used Stirling numbers of the first kind) should come up, but I didn't actually follow through with that.

Thanks for the formula!

 

[LittleWolf]

Modifying your notation, the probability P(N,6) is the cumulative distribution function. The probability that the last face shows up on the Nth throw is 6*P(N,5). If you consider the recursion formula for Stirling#s of the 2nd kind, you can see why P(N,6) is the CDF. Thanks to everyone for clearing up this problem.

 

[davidseed]

a related problem is
what is the the expected number of throws to get a six on a fair dice

this was raised at
https://www.physicsforums.com/archive/topic/t-45262_The_expected_value_of_a_Geometric_Series.html
which seems to be closed now.

yes the answer is 6 but how do you prove it.

if p=1/6 and q=1-p
x is the number of throws

then E(x) is sum(x.P(X=x)) = sum(x.p.q^(x-1))
the sums are for x=1 to infinity
i.e. E(x) is p(1 +2q +3q^2 +4q^3+...)

let S= E(x)/p = 1 +2q +3q^2 +4q^3+...

rearranging the sum as
S=
1 + q + q^2 + q^3 + ...
+ q + q^2 + q^3 + ..
+ q^2 + q^3 +...
then rearrange these lines as

S= 1 ( 1 + q + q^2 + q^3 + ...)
+q (1 + q + q^2 + q^3 + ...)
+q^2 ( 1 + q + q^2 + q^3 + ...)
...

so S= (1 + q + q^2 + q^3 + ...)*(1 + q + q^2 + q^3 + ...)

i.e S= (1 + q + q^2 + q^3 + ...)^2
this geometric series sums to 1/(1-q)

i.e. S= (1/(1-q))^2
i.e. = 1/p^2
So E(x) =pS = 1/p
in the case of six sided die, p=1/6, E(x) =6


this solutiuon found at http://math.berkeley.edu/~mchrist/Math55/Lectures/L28.pdf

probably a good source several problems in this forum