Roll all 6s

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Roll all 6s

Postby GreedyAlgorithm » Fri Apr 04, 2008 4:32 pm UTC

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?
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

User avatar
Indon
Posts: 4433
Joined: Thu Oct 18, 2007 5:21 pm UTC
Location: Alabama :(
Contact:

Re: Roll all 6s

Postby Indon » Fri Apr 04, 2008 4:46 pm UTC

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.

Image

User avatar
SimonM
Posts: 280
Joined: Sat Jul 21, 2007 4:49 pm UTC
Location: Guernsey, CI
Contact:

Re: Roll all 6s

Postby SimonM » Fri Apr 04, 2008 4:57 pm UTC

Tentative method (I've never done anything like this before)

Spoiler:
Let Pn(X) be the probability of needing exactly X rolls to "get rid" of n.
Let Fn(X) be the sum of Pn(x) for all x <= X

Consider the one die which which last out the whole time before being removed

The probability of it will be (5/6)X-1(1/6)

Therefore Pn(X) = (5/6)X-1(1/6) * Fn-1(X)

Consider one of the die left over. The probability that it will be removed before or equal to X is 1 - the probability of lasting longer. Therefore our probability is 1-(5/6)X

Therefore the probability is Pn(X) = (5/6)X-1(1/6) * (1-(5/6)X)n-1

I assume that from this we can ascertain an expected value (haven't done that in stats yet)

In terms of me checking my solution. P2(1) = 1/36 which is good enough for me


Warning: This comes from a quick look at WP
E(X) is the sum of probabilities times the values achieved.

Therefore E(X) = sum from k = 1 to infinity of (5/6)X-1(1/6) * (1-(5/6)X)n-1k

Can someone plug and chug that? Thanks

Right... I attempted it. Ti-89 wouldn't give me a closed form answer. Lots of exs I guess there was a Taylor expansion somewhere in there.
mosc wrote:How did you LEARN, exactly, to suck?

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Roll all 6s

Postby Xanthir » Fri Apr 04, 2008 5:23 pm UTC

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)))

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Roll all 6s

Postby antonfire » Fri Apr 04, 2008 5:42 pm UTC

For better looking formulas and more generality, let's say that a die rolls its maximum value with probability p, and let q=1-p. There are n dice.

The probability that a particular die is gone by step k is 1-qk. The probability that they're all gone by step k is thus (1-qk)n. The probability that k is the first step at which they are all gone, then, is (1-qk)n-(1-qk-1)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: En=1+Sumk=0n nCk qkpn-kEk

(Yes, En occurs on both sides, so you need to solve for it. Also, E0 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?

rabuf
Posts: 15
Joined: Thu Mar 20, 2008 2:30 pm UTC

Re: Roll all 6s

Postby rabuf » Mon Apr 07, 2008 3:59 pm UTC

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+r-1)C(r-1)pr(1-p)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(1-p)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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26767
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Roll all 6s

Postby gmalivuk » Mon Apr 07, 2008 5:20 pm UTC

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 not-six 114 times in a row, which isn't very likely when you've only got 23 to start with...
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Roll all 6s

Postby Xanthir » Mon Apr 07, 2008 5:57 pm UTC

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)))

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Roll all 6s

Postby mike-l » Mon Apr 07, 2008 7:02 pm UTC

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 non-sixes left after j rolls.

Then T_n(x) = T_n-1(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^n-1(0)^23).
Even neater is, this works if we don't start with a fixed number. Say you pick a number uniformly from 1-10 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.

Ampoth
Posts: 5
Joined: Sun Apr 20, 2008 12:31 am UTC

Re: Roll all 6s

Postby Ampoth » Sun Apr 20, 2008 4:38 am UTC

Edit: Gah! Wrong by argument below.
Spoiler:
You'd expect him to have to do the process six times.

Assuming the dice are fair and independent.

You'd expect to have to roll a die six times to get a six, because if it is a fair die the probability of each side being one sixth, rolling it six times you'd expect to observe one six.

Then because each die is independent it doesn't matter how many dice you have, be it twenty three or one million, you'd expect to only have to roll each die six times to get one six, so you'd expect to repeat the process only six times.
Last edited by Ampoth on Sun Apr 20, 2008 5:32 am UTC, edited 1 time in total.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Roll all 6s

Postby antonfire » Sun Apr 20, 2008 5:23 am UTC

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.
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?

Ampoth
Posts: 5
Joined: Sun Apr 20, 2008 12:31 am UTC

Re: Roll all 6s

Postby Ampoth » Sun Apr 20, 2008 8:37 pm UTC

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.
Spoiler:
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}{(1-p)}^{y-1}[/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 we have our sample of N dice, represented by ([imath]Y_1,Y_2, ... , Y_N[/imath]), so each [imath]Y_i[/imath] can take on the discrete values 1,2,3,... where that is how many times the die had to be rolled before a six was gotten. For the answer to how many times we'd expect to have to roll N dice we want the sum of all of these random variables [imath]Y_i[/imath].

We'll let [imath]T = Y_1 + Y_2 + ... + Y_N[/imath], then the expected value of T is the number of times we'd expect to have to roll a die until N dice are all showing six.

It turns out this was easy to get when we assume that the [imath]Y_i[/imath] are independent, and identically distributed as a Geometric Random Variable with parameter p=1/6 being the probability of getting a six on a roll of a die.

[imath]E(T) = E(Y_1 + Y_2 + ... + Y_N)[/imath]
[imath]=E(Y_1) + E(Y_2) + ... + E(Y_N)[/imath]
[imath]=N*E(Y_i)[/imath], This is due to our assumption of independence and identical distribution.
We know that the expected value of a Geometric Random Variable is 1/p where in this cause p=1/6 so then,
[imath]=6*N[/imath]

And we end up expecting to roll a die 6N times if we want N dice to show six.

So if we only have one die, we expect to roll a die six times before it's showing six.
If we have two dice, we expect to roll a die twelve times before both are showing six. I'm not saying that this is the number of times each die has to be rolled, just that this is the number of times you'll expect to have to pick up a die and roll it until two dice are showing sixes.

If anyone can see anything I've done wrong please correct me.

Then on to the second and much harder part.


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}{(1-p)}^{y-1}[/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))}^{N-1}[/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{(1-p)}^{y-1}[/imath] and the cumulative density function is [imath]F_{Y}(y)=1-{(1-p)}^{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{(1-p)}^{y-1}{(1-{(1-p)}^{y})}^{N-1}[/imath]

Then the expected value of the Nth order statistic by definition is:
[imath]E(Y_{(N)})=\sum^{\infty}_{y=1}[yNp{(1-p)}^{y-1}{(1-{(1-p)}^{y})}^{N-1}][/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:
N= | [imath]E(Y_{(N)})\approx[/imath]
1 | 6
2 | 9.02479
3 | 11.0307
4 | 12.5347
5 | 13.738
6 | 14.7408
7 | 15.6003
8 | 16.3524
9 | 17.0209
10 | 17.6225
11 | 18.1695
12 | 18.6709
13 | 19.1337
14 | 19.5635
15 | 19.9646
16 | 20.3406
17 | 20.6945
18 | 21.0288
19 | 21.3455
20 | 21.6463
21 | 21.9328
22 | 22.2063
23 | 22.4679
24 | 22.7186
25 | 22.9592
26 | 23.1907
27 | 23.4135
28 | 23.6284
29 | 23.8358
30 | 24.0364


I went ahead and graphed it for the values in the table as well:
Image

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!(N-n)!} {(-1)}^{n+1} \displaystyle \frac {n {(1-p)}^{n-1}}{{(1-{(1-p)}^{n})}^{2}}[/imath].
Last edited by Ampoth on Tue Apr 22, 2008 8:03 pm UTC, edited 2 times in total.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Roll all 6s

Postby Token » Sun Apr 20, 2008 9:31 pm UTC

I think this does the trick.
diceeq.png
diceeq.png (1.95 KiB) Viewed 2329 times

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests