Sum of roll of N dice

[Gerald H]

(05-03-2018 12:39 PM)Werner Wrote:  

(05-02-2018 08:01 AM)Gerald H Wrote:  

Code:

« DUP 6. SWAP ^ RAND * FLOOR
  DO 6. IDIV2 ROT + SWAP DUP NOT
  UNTIL
  END DROP
»

DUP 6. SWAP = 6. OVER

But I see no reason to form 6^N? Simply do

Code:

\<< RAND OVER 1 SWAP
    START
      6. * + DUP IP SWAP FP
    NEXT
    DROP
\>>

Same thing.
Cheers, Werner

Very elegant, Werner, bravo.

"DUP 6. SWAP" is embarrassing.

"OVER 1 SWAP" could be "1 PICK3".

[Werner]

(05-03-2018 04:49 PM)Gerald H Wrote:  "OVER 1 SWAP" could be "1 PICK3".

I know, but I like to stay 48-compatible ;-)
Werner

[SlideRule]

(05-03-2018 08:16 AM)Csaba Tizedes Wrote:  N×3.5
N is the number of dices.

Cs.

I find more evidence to support your statement than other(s). Please follow up with your reasoning/analysis, if only for my benefit.

BEST!
SlideRule

[Csaba Tizedes]

(05-04-2018 12:23 AM)SlideRule Wrote:  

(05-03-2018 08:16 AM)Csaba Tizedes Wrote:  N×3.5
N is the number of dices.

Cs.

I find more evidence to support your statement than other(s). Please follow up with your reasoning/analysis, if only for my benefit.

BEST!
SlideRule

May I do not understand your English, but:

N×3.5 was my first intuitive thought about it.

If I want to understand it, it can be summarize in two simple steps:
1.) The expected value (E()) of one dice rolling(X) is E(X)=3.5 ( =(1+2+3+4+5+6)/6 )
2.) The expected value has a linear property: expected value of sum of N dice rolling is E(X+X+...+X)=E(X)+E(X)+...+E(X)=N×E(X)

This is the most probably value of the sum of N dice rolling.

I think the Joe Horn's question is not exact. Maybe the better answer is "between N and 6×N".

Cs.

[Gamo]

DICE for the 42S
Happen to found this on our forum is this the right program for this topic.

http://www.hpmuseum.org/software/42dice.htm

Gamo

[Joe Horn]

(05-04-2018 06:27 AM)Gamo Wrote:  DICE for the 42S
Happen to found this on our forum is this the right program for this topic.
http://www.hpmuseum.org/software/42dice.htm

No. That program uses the same simple brute-force method that everybody has always used, namely, it simulates the total of N dice throws by adding N pseudo-random numbers together. That's not what this thread is about. Sorry if the original post was unclear, but I don't know any way to make it clearer.

[Joe Horn]

(05-04-2018 06:09 AM)Csaba Tizedes Wrote:  N×3.5 was my first intuitive thought about it.
This is the most probably value of the sum of N dice rolling.

That's not what is being sought here. What is desired is a program which simulates rolling N dice and returning the total of the numbers on their faces. So different runs would get different results (just like throwing N dice gets different results). This task has been programmed a zillion times in every programming language... but always by generating N random numbers between 1 and 6, and adding them all together. My question is: How can a program be written which generates only ONE random number, and then somehow turns it into a number which is statistically indistinguishable from the total of N dice rolls?

I'm not looking for a single value (that's trivial). Nor am I looking for a way to add N random integers (also trivial). I'm looking for a way to simulate getting the total on N rolled dice, but using only ONE random number to generate the "total" directly (without generating any of the individual dice throws).

(05-04-2018 06:09 AM)Csaba Tizedes Wrote:  I think the Joe Horn's question is not exact.

I hope my attempt above was more clear.

[SlideRule]

Thanks Joe

SlideRule

[Michael Zinn]

Interesting question!

Not sure how to do it quickly for N dice, but you can do it for 2 by using a lookup table for the 36 possible rolls of 2 6 sided dice, i.e. you generate a number between 0 and 35, do a look-up and you are down.

The code might look something like this (the line numbers are important):

Code:


000 - 0
001 - 2
002 - RTN
003 - 0
004 - 3
005 - RTN
006 - 0
007 - 3
008 - RTN
008 - 0
009 - 4
010 - RTN
... [ 4 4 5 5 5 5 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 9 9 9 9 10 10 10 11 11 12 ] ...
...
LBL D
  RAN #
  3
  6
  *
  INT
  3
  *
  CHS
  STO I
  GTO (i)

The "shape" of the lookup table is very regular, so maybe there is an easy way to calculate the distribution directly from the random number.

[Dieter]

(05-04-2018 06:35 PM)michaelzinn Wrote:  The "shape" of the lookup table is very regular, so maybe there is an easy way to calculate the distribution directly from the random number.

A direct calculation can be done by applying the inverse Normal distribution to the random number, which is then rescaled with variance and mean. I have described this approach in my first post in this thread and tested it on a WP34s. Here it seems to work fine.

This only requires a reasonably fast Normal quantile function. Or at least an approximation thereof.

Dieter

[Dieter]

(05-04-2018 06:35 PM)michaelzinn Wrote:  The "shape" of the lookup table is very regular, so maybe there is an easy way to calculate the distribution directly from the random number.

There is a way to calculate the distribution, i.e. the probabilty for a sum of n, n+1, n+2, ... 6n. I found this PDF (in German) that shows an interesting approach:

Expand (x+x^2+x^3+x^4+x^5+x^6)^n to get a polynomial of degree 6n.
Here the coefficient at x^k divided by 6^n is the probability for a sum of k.

Example for n=3:

(x+x^2+x^3+x^4+x^5)^3 =
x^3+3x^4+6x^5+10x^6+15x^7+21x^8+25x^9+27x^10+27x^11+25x^12+21x^13+15x^14+10x^15+​6x^16+3x^17+x^18

So the expected frequency for k=9 is 25, and the probability for a sum of 9 is 25/216.

I haven't checked the mathematical background, but it can't be too difficult: the PDF is from nibis.de, a web portal for education in the schools of Lower Saxonia, Germany. ;-)

Dieter

Edit: the expanded polynomial of course has powers up to 6n.

[zooropa1844]

Dieter, that is a wonderful (and obvious) technique to compute the number of different positive integer solutions to an equation x_1+x_2+...+x_n=k where the x_i must be between to given natural numbers.

I think this belongs to what is called "generating function" but it wasn't covered in the basic probability courses I took.

Regards

[Dieter]

(05-05-2018 06:38 PM)Dieter Wrote:  There is a way to calculate the distribution, i.e. the probabilty for a sum of n, n+1, n+2, ... 6n. I found this PDF (in German) that shows an interesting approach:

I now have calculated the probability distribution function for some small n (=3, 4 and 5) and compared it with the approximation by a Normal distribution with µ=n·3,5 and σ²=n·35/12. The results look quite good:

Code:

n=3

dice     probabilty
sum   exact     approx.
-----------------------
 3    0,0046    0,0054
 4    0,0139    0,0121
 5    0,0278    0,0239
 6    0,0463    0,0424
 7    0,0694    0,0670
 8    0,0972    0,0944
 9    0,1157    0,1186
10    0,1250    0,1330
11    0,1250    0,1330
12    0,1157    0,1186
13    0,0972    0,0944
14    0,0694    0,0670
15    0,0463    0,0424
16    0,0278    0,0239
17    0,0139    0,0121
18    0,0046    0,0054

The max. absolute error is < 0,008 in the center, else even < 0,004. So both distributions agree very well.

For n=4 the largest error is ~ 0,004.

For n=5 the largest error is ~ 0,003.

The match seems even better for σ²=n·36/12  and  σ²=n·37/12.
So the inversion method (apply the Normal quantile function to the generated random number) seems to be a good approach.

Dieter

[zooropa1844]

Dieter, how did you get the general formula for the variance n*35/12? I just checked its exactness for the cases n=3, 4 and 5.

Regards,

[Dieter]

(05-06-2018 08:18 PM)zooropa1844 Wrote:  Dieter, how did you get the general formula for the variance n*35/12? I just checked its exactness for the cases n=3, 4 and 5.

A single (fair) die follows a discrete uniform distribution where the random variable can be anything in {1, 2, 3, 4, 5, 6}. Here the mean µ is (1+6)/2=3,5 and the variance σ² is [(1–3,5)²+(2–3,5)²+...+(6–3,5)²]/6 = 17,5/6 = 35/12. Or, according to the formula on the linked Wikipedia page, [(6–1+1)²–1]/12 = 35/12.

The sum of n equal, uniformly distributed random variables, i.e. the sum of n dice rolls, then simply is n times the individual variance, i.e. n·σ² or n·35/12.

Dieter

[zooropa1844]

Thank you for the detailed explanation. It seems a special case of the linearity of the variance when the variables are uncorrelated: Var(X+Y)=Var(X)+Var(Y).

Regards

[pier4r]

I like the idea that although an exact 1:1 simulation of N dice can be done with the method of Joe Horn (or a sort of mapping), one can try to find out other ideas that may work as well or may approximate the result. Variety is always healthy, one never knows what could be the limits of the next application of the solution, so have many ways to solve a problem can be helpful.

This is a stark contrast to some technical discussions online where people say "Why do you want to do this in this way? X is the best solution, end".

[Allen]

Supposing you know N in advance, it's easy enough to precalculate the probability distribution (as started above).. Then add up the individual probabilities to create an empirical cumulative distribution. Then you can generate 1 random number (from 0 to 1) and get the exact sum of dice just by a lookup table.

For example, if your random number is .855666 go down the cumulative pdr until you find a number greater than the rolled number.. that's your sum.

r-nomial coefficients here:https://oeis.org/A063260

sum prob cumulative probability
4 : 1/1296 = 0.000771604938272 0.000771604938272
5 : 4/1296 = 0.00308641975309 0.00385802469136
6 : 10/1296 = 0.00771604938272 0.0115740740741
7 : 20/1296 = 0.0154320987654 0.0270061728395
8 : 35/1296 = 0.0270061728395 0.054012345679
9 : 56/1296 = 0.0432098765432 0.0972222222222
10 : 80/1296 = 0.0617283950617 0.158950617284
11 : 104/1296 = 0.0802469135802 0.239197530864
12 : 125/1296 = 0.096450617284 0.335648148148
13 : 140/1296 = 0.108024691358 0.443672839506
14 : 146/1296 = 0.112654320988 0.556327160494
15 : 140/1296 = 0.108024691358 0.664351851852
16 : 125/1296 = 0.096450617284 0.760802469136
17 : 104/1296 = 0.0802469135802 0.841049382716
18 <---------------------- 0.855666
18 : 80/1296 = 0.0617283950617 0.902777777778
19 : 56/1296 = 0.0432098765432 0.945987654321
20 : 35/1296 = 0.0270061728395 0.97299382716
21 : 20/1296 = 0.0154320987654 0.988425925926
22 : 10/1296 = 0.00771604938272 0.996141975309
23 : 4/1296 = 0.00308641975309 0.999228395062
24 : 1/1296 = 0.000771604938272 1.0

[Allen]

or for integers.. take the same random number (0.855666*1296 = 1108.94 (1109)), and count how many coefficients of this polynomial you have to add until you get to 1109.

[zooropa1844]

Allen, the way you describe to solve the problem is the same I thought about when the problem first came about in a Facebook forum. But back then I didn't know exactly how to compute the probability mass function of the sum of a roll of N dice.

Regards