Roll all 6s
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 286
 Joined: Tue Aug 22, 2006 10:35 pm UTC
 Contact:
Roll all 6s
A friend of mine was rolling some dice yesterday. He took 23d6, rolled them, separated the 6s from the rest, rolled the rest, separated the 6s, etc. until there were only 6s. Then another friend & I did some maths to determine characteristics of his behavior.
What is the most likely number of rolls needed to turn 23d6 into 6s? Nd6? NdD into Ds? Average?
What is the most likely number of rolls needed to turn 23d6 into 6s? Nd6? NdD into Ds? Average?
GENERATION 1i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
Re: Roll all 6s
The _most_ likely number of rolls would probably be obtainable by simply multiplying the total die count by 5/6 until you have less than .5 left. Other probabilities strike me like they'd be more complex.
So, I like talking. So if you want to talk about something with me, feel free to send me a PM.
My blog, now rarely updated.
My blog, now rarely updated.
Re: Roll all 6s
Tentative method (I've never done anything like this before)
Spoiler:
mosc wrote:How did you LEARN, exactly, to suck?
 Xanthir
 My HERO!!!
 Posts: 5413
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Roll all 6s
Indon wrote:The _most_ likely number of rolls would probably be obtainable by simply multiplying the total die count by 5/6 until you have less than .5 left. Other probabilities strike me like they'd be more complex.
You are *almost* right. Just keep going until you get a number less than 1, not .5. Each time you roll you expect 1/6 of the dice to show a 6 and thus not be rolled any longer. So 5/6 of them get rolled again. When you drop below 1, this means that you are expecting that less than 1 die remains that doesn't show a 6.
This is easy to compute. Just find the smallest natural x such that 23*(5/6)^{x} < 1, or x > ln(1/23)/ln(5/6) (you have to reverse the inequality since you divided by ln(5/6), a negative number). The answer here is 18 (x > 17.1976). After 18 rolls, you are slightly more than 50% likely to have all of them be showing a 6.
It should be obvious how to generalize this to arbitrary number and size of dice.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
Re: Roll all 6s
For better looking formulas and more generality, let's say that a die rolls its maximum value with probability p, and let q=1p. There are n dice.
The probability that a particular die is gone by step k is 1q^{k}. The probability that they're all gone by step k is thus (1q^{k})^{n}. The probability that k is the first step at which they are all gone, then, is (1q^{k})^{n}(1q^{k1})^{n}.
You can differentiate w.r.t. k and solve for zero if you want the general area of the most likely number of times it will take.
For the expectation value, this recursive formula might be more useful: E_{n}=1+Sum_{k=0}^{n} nCk q^{k}p^{nk}E_{k}
(Yes, E_{n} occurs on both sides, so you need to solve for it. Also, E_{0} is, of course, 0.)
I don't feel up to doing much more than this.
The probability that a particular die is gone by step k is 1q^{k}. The probability that they're all gone by step k is thus (1q^{k})^{n}. The probability that k is the first step at which they are all gone, then, is (1q^{k})^{n}(1q^{k1})^{n}.
You can differentiate w.r.t. k and solve for zero if you want the general area of the most likely number of times it will take.
For the expectation value, this recursive formula might be more useful: E_{n}=1+Sum_{k=0}^{n} nCk q^{k}p^{nk}E_{k}
(Yes, E_{n} occurs on both sides, so you need to solve for it. Also, E_{0} is, of course, 0.)
I don't feel up to doing much more than this.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
Re: Roll all 6s
GreedyAlgorithm wrote:What is the most likely number of rolls needed to turn 23d6 into 6s? Nd6? NdD into Ds? Average?
The way I'm interpreting this uses the negative binomial distribution (see wikipedia or MathWorld for more discussion of it). This distribution describes the scenario where you have Y failures before you have a total of r successes, with each success having probability p
Pr(Y=y)=(y+r1)C(r1)p^{r}(1p)^{y}
As it applies to this question then, it will tell you how many times (on average) you must roll a single die before you will have a total of N Ds.
It's been a few years since I studied this distribution, but I found the formula for the mean at MathWorld:
E(Y)=r(1p)p^{1}
So for the case of 23d6:
E(Y)=23(5/6)(1/6)^{1}=23(5)=115
So the expected total number of die rolls will be 115.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26767
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Roll all 6s
rabuf wrote:So the expected total number of die rolls will be 115.
Either you're misinterpreting the way to count rolls, or I am. As I understand it, the first roll includes all 23 dice, the second includes all of the ones which were not sixes the first time, and so on. In which case 115 is rather absurd, because it means that one of your dice has come up notsix 114 times in a row, which isn't very likely when you've only got 23 to start with...
 Xanthir
 My HERO!!!
 Posts: 5413
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Roll all 6s
It looks like he's meaning "a total of 115 dice will be rolled". The first round of rolling will contribute 23 toward that total.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
Re: Roll all 6s
Here's (what I think is) a neat method.
Let T(x) = 1/6 + 5/6x
Let T_n(x) = a_0,n + a_1,n x + ... + a_r,n x^r
where a_i,j is the probability of having i nonsixes left after j rolls.
Then T_n(x) = T_n1(T(x)).
In our case, T_0(x) = x^23.
Since T(x) is linear, it's easy to iterate, and so the odds will be T^n(0)^23 of being done after n tries. (I suppose with this method you want to look at this number minus T^n1(0)^23).
Even neater is, this works if we don't start with a fixed number. Say you pick a number uniformly from 110 and play the game with that many dice. Then we just change T_0(x) to 1/10(x+x^2+ .. + x^10).
Cheers,
Mike
Let T(x) = 1/6 + 5/6x
Let T_n(x) = a_0,n + a_1,n x + ... + a_r,n x^r
where a_i,j is the probability of having i nonsixes left after j rolls.
Then T_n(x) = T_n1(T(x)).
In our case, T_0(x) = x^23.
Since T(x) is linear, it's easy to iterate, and so the odds will be T^n(0)^23 of being done after n tries. (I suppose with this method you want to look at this number minus T^n1(0)^23).
Even neater is, this works if we don't start with a fixed number. Say you pick a number uniformly from 110 and play the game with that many dice. Then we just change T_0(x) to 1/10(x+x^2+ .. + x^10).
Cheers,
Mike
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Re: Roll all 6s
Edit: Gah! Wrong by argument below.
Spoiler:
Last edited by Ampoth on Sun Apr 20, 2008 5:32 am UTC, edited 1 time in total.
Re: Roll all 6s
Well, that's pretty obviously not true.
Imagine two dice. The probability that you're done at step k is less than the probability that you're done with one die. So the expected time to complete the process with two dice is higher that with one die. In fact, by the above, it's 96/11.
The mistake in your reasoning is that you implicitly assume that each die gets rolled at each iteration. Instead, fewer and fewer dice get rolled, so it takes longer and longer.
To add something useful to the post, note that the expected number of times you roll a particular die is, indeed, 6. So the expected number of die rolls you end up making (that is, rolling 10 dice counts as 10 die rolls) is 6n. Unfortunately, I can't find a way to get this to say anything concrete about the expected number of times that you repeat the process.
Imagine two dice. The probability that you're done at step k is less than the probability that you're done with one die. So the expected time to complete the process with two dice is higher that with one die. In fact, by the above, it's 96/11.
The mistake in your reasoning is that you implicitly assume that each die gets rolled at each iteration. Instead, fewer and fewer dice get rolled, so it takes longer and longer.
To add something useful to the post, note that the expected number of times you roll a particular die is, indeed, 6. So the expected number of die rolls you end up making (that is, rolling 10 dice counts as 10 die rolls) is 6n. Unfortunately, I can't find a way to get this to say anything concrete about the expected number of times that you repeat the process.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
Re: Roll all 6s
Alright, I've gone back and done the math for it all this is what I've gotten.
For the expected number of times you'll have to roll N dice to get sixes on all of them.
I realize that antonfire said this in the post above but this is the a more formal derivation of it.
The number of times we can expect to repeat the process until all dice are showing sixes.
I model each die in this process using a geometric random variable Y, where Y can take on the values 1, 2, 3,... and P(Y=y)=[imath]{p}{(1p)}^{y1}[/imath] where [imath]{0}\le{p}\le{1}[/imath] is the probability of a success, or a die rolling a six. So in this case p=1/6.
Then I represent our sample of N dice by {[imath]Y_1,Y_2, ... , Y_N[/imath]}, where each [imath]Y_i[/imath] can take on the values 1, 2, 3,... just like above. Then for a sample the number of times we would do the process, is the largest value [imath]Y_i[/imath] takes on in our sample, or the Nth order statistic [imath]Y_{(N)}[/imath].
So for three dice if our sample was {1,2,3}, then the number of times we did the process was three, because all dice had sixes after the third time, so we stop.
The probability density function of the Nth order statistic is given by the formula:
[imath]f_{Y_{(N)}}(y)=N*f_{Y}(y){(F_{Y}(y))}^{N1}[/imath], where [imath]f_{Y}(y)[/imath] and [imath]F_{Y}(y)[/imath] are the pdf and cdf of the underlying distribution.
In this case the probability density function is [imath]f_{Y}(y)=p{(1p)}^{y1}[/imath] and the cumulative density function is [imath]F_{Y}(y)=1{(1p)}^{y}[/imath]. You can check wikipedia for the cumulative density function, though I derived it just to be sure it was right.
So the probability density function for the Nth order statistic is:
[imath]f_{Y_{(N)}}(y)=N*p{(1p)}^{y1}{(1{(1p)}^{y})}^{N1}[/imath]
Then the expected value of the Nth order statistic by definition is:
[imath]E(Y_{(N)})=\sum^{\infty}_{y=1}[yNp{(1p)}^{y1}{(1{(1p)}^{y})}^{N1}][/imath]
I tried to solve this but wasn't able to get anywhere concrete after two pages of work. So instead I switched to using a computer to approximate the value based on N.
For N=1 I got [imath]E(Y_{(N)})\approx{6}[/imath], Which is what'd we'd expect from just one die.
For N=23 I got [imath]E(Y_{(N)})\approx{22.4679}[/imath]
Here's a table of approximate values:
I went ahead and graphed it for the values in the table as well:
So if anyone sees something I did wrong please correct me,and if you think you can solve the summation for the expected value of the Nth order statistic please be my guest.
Alright, I solved that infinite sum and I've ended up with a sum that matched the approximate values perfectly.
[imath]E(Y_{(N)})=p \sum^{N}_{n=1} \displaystyle \frac {N!}{n!(Nn)!} {(1)}^{n+1} \displaystyle \frac {n {(1p)}^{n1}}{{(1{(1p)}^{n})}^{2}}[/imath].
For the expected number of times you'll have to roll N dice to get sixes on all of them.
I realize that antonfire said this in the post above but this is the a more formal derivation of it.
Spoiler:
The number of times we can expect to repeat the process until all dice are showing sixes.
I model each die in this process using a geometric random variable Y, where Y can take on the values 1, 2, 3,... and P(Y=y)=[imath]{p}{(1p)}^{y1}[/imath] where [imath]{0}\le{p}\le{1}[/imath] is the probability of a success, or a die rolling a six. So in this case p=1/6.
Then I represent our sample of N dice by {[imath]Y_1,Y_2, ... , Y_N[/imath]}, where each [imath]Y_i[/imath] can take on the values 1, 2, 3,... just like above. Then for a sample the number of times we would do the process, is the largest value [imath]Y_i[/imath] takes on in our sample, or the Nth order statistic [imath]Y_{(N)}[/imath].
So for three dice if our sample was {1,2,3}, then the number of times we did the process was three, because all dice had sixes after the third time, so we stop.
The probability density function of the Nth order statistic is given by the formula:
[imath]f_{Y_{(N)}}(y)=N*f_{Y}(y){(F_{Y}(y))}^{N1}[/imath], where [imath]f_{Y}(y)[/imath] and [imath]F_{Y}(y)[/imath] are the pdf and cdf of the underlying distribution.
In this case the probability density function is [imath]f_{Y}(y)=p{(1p)}^{y1}[/imath] and the cumulative density function is [imath]F_{Y}(y)=1{(1p)}^{y}[/imath]. You can check wikipedia for the cumulative density function, though I derived it just to be sure it was right.
So the probability density function for the Nth order statistic is:
[imath]f_{Y_{(N)}}(y)=N*p{(1p)}^{y1}{(1{(1p)}^{y})}^{N1}[/imath]
Then the expected value of the Nth order statistic by definition is:
[imath]E(Y_{(N)})=\sum^{\infty}_{y=1}[yNp{(1p)}^{y1}{(1{(1p)}^{y})}^{N1}][/imath]
I tried to solve this but wasn't able to get anywhere concrete after two pages of work. So instead I switched to using a computer to approximate the value based on N.
For N=1 I got [imath]E(Y_{(N)})\approx{6}[/imath], Which is what'd we'd expect from just one die.
For N=23 I got [imath]E(Y_{(N)})\approx{22.4679}[/imath]
Here's a table of approximate values:
Spoiler:
I went ahead and graphed it for the values in the table as well:
So if anyone sees something I did wrong please correct me,
Alright, I solved that infinite sum and I've ended up with a sum that matched the approximate values perfectly.
[imath]E(Y_{(N)})=p \sum^{N}_{n=1} \displaystyle \frac {N!}{n!(Nn)!} {(1)}^{n+1} \displaystyle \frac {n {(1p)}^{n1}}{{(1{(1p)}^{n})}^{2}}[/imath].
Last edited by Ampoth on Tue Apr 22, 2008 8:03 pm UTC, edited 2 times in total.
Re: Roll all 6s
I think this does the trick.
EDIT: It appears to agree with antonfire's recursive formula for N=1,2,3. This seems to confirm it was allowable to switch those summations when I derived it.
Therefore I can give a calculated figure for N=23, p=1/6 as 20.982.
EDIT: It appears to agree with antonfire's recursive formula for N=1,2,3. This seems to confirm it was allowable to switch those summations when I derived it.
Therefore I can give a calculated figure for N=23, p=1/6 as 20.982.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
Who is online
Users browsing this forum: No registered users and 7 guests