Sum of roll of N dice

[Joe Horn]

THE QUESTION: Is there a direct way to return the sum of a roll of N dice without generating N random numbers and adding them together?

BACKGROUND: In a recent Facebook discussion, it was suggested that you simply generate a random number uniformly between N (a roll of all 1's) and 6N (a roll of all 6's). But that assumes that every total is equally probable, which is not true.

For example, the sum of a roll of 4 dice can be anything between 4 and 24... but not every sum has equal probability of occurring. Since there are 4 dice, each of which can have 6 values, there are 6^4 (1296) possible ways to roll 4 dice. There is only 1 way to roll a total of 4:

{ 1 1 1 1 }

so rolling a total of 4 has a probability of 1/1296. But there are 4 ways to roll a total of 5:

{ 1 1 1 2 }
{ 1 1 2 1 }
{ 1 2 1 1 }
{ 2 1 1 1 }

so rolling a total of 5 has a probability of 4/1296. There are 10 ways to roll a total of 6:

{ 1 1 1 3 }
{ 1 1 3 1 }
{ 1 3 1 1 }
{ 3 1 1 1 }
{ 1 1 2 2 }
{ 1 2 1 2 }
{ 2 1 1 2 }
{ 1 2 2 1 }
{ 2 1 2 1 }
{ 2 2 1 1 }

so rolling a total of 6 has a probability of 10/1296. Different totals have different probabilities. How can this be taken into account when simulating throwing N dice directly, without summing N random integers between 1 and 6?

[Gerald H]

No.

Somewhere in your calculation you'll need 4 independent (pseudo-) random events to replicate the dice throw.

CLAIMER:

As in most of my utterances, what I say here is my true opinion (otherwise I might introduce an idea by using "You could assume....." or "Suppose that....") & represents my best attempt at expressing myself clearly.

I have given the matter due attention & arrived at my conclusion.

It will take the force of good argument to sway my opinion, but should this unlikely event occur I will acknowledge the superiority of my antagonists' reasoning.

[pier4r]

Throwing some quick ideas.

A sort of montecarlo method?

If one has N dice, one knows the theoretical distribution for all the results between N and 6*N.

Therefore one can just work with it. The main idea is to roll one large dice to simulate the result of a series of smaller dice.

Ex:
N = 3
Smallest probability { 1 1 1 } (or { 6 6 6 } ) -> 1/216

Pick a uniform integer number between 1 and 216 and assign results accordingly.
For example if 1 -> { 1 1 1 }
the range 2-4 is for the combinations of { 1 1 2 } (the order doesn't matter)
the range 5-7 is for the combinations of { 1 1 3 }
...
the range 216-216 is for { 6 6 6 }

If the order matters, like below, then every combination has weight 1.

Note that if one doesn't want to keep a table: "range - combination", one has to compute it on the fly given a number between 1 and 216, to identify the right combination. The combination is increasing, a bit like a number in base 7 excluding zeroes. so
{1 1 1}
{1 1 2}
{1 1 3}
...
{2 4 4}
{2 4 5}
...
{5 5 5}
{5 5 6}
...
{6 6 5}
{6 6 6}
And each combination has a known weight ( equal to 1, as one is going to check all of them, for example { 1 1 2 } as well as { 2 1 1} or { 1 2 1 } ) so one can compute the different ranges increasingly.
Then one, knowing the combination chosen by the number between 1 and 216, can sum its digits. Returning the result with proper probability.

The same can be done to, instead of matching the combinations, matching directly the sum of the digits, that maybe saves space.
I am pretty sure that one can simplify the computation even more.

side observation.
The HP calculator group on Facebook is now quite active. It is a pity that it has interesting questions that are difficult to reach again by Facebook's design. Facebook is focused on the last posts, while old posts get increasingly hard to reach due to the infinite scrolling. Damn the designers that keeps using infinite scrolling.

edit.

(05-02-2018 05:48 AM)Gerald H Wrote:  should this unlikely event occur I will acknowledge the superiority of my antagonists' reasoning.

Now I demand, given my superior argument, that you post even more programming challenges and guardian puzzles! HA!

[Jim Horn]

Hello, Joe!

If you roll N six sided dice and put them next to each other and write down the values they show *minus 1* each, you'll get an N digit integer in base 6. All such 6^N integers are equally likely for fair dice. So, just find a random number from 0 to (6^N)-1, convert to base 6, add the sum of its digits plus N (to correct the "subtract 1 from each digit") and there you go: the sum of the six rolled dice with only one random number generation.

Of course, converting an integer to base 6 will likely require a loop which can do the running sum of the base 6 integer as it goes (N iterations needed). But still only involves a single random number generation to get all N random dice thrown.

[Gerald H]

I acknowledge pier4r's superior reasoning & admire Jim's solution, thanks to both.

My penance finishes with the programme below:

Code:

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

[pier4r]

(05-02-2018 07:01 AM)Jim Horn Wrote:  So, just find a random number from 0 to (6^N)-1, convert to base 6, add the sum of its digits plus N (to correct the "subtract 1 from each digit") and there you go: the sum of the six rolled dice with only one random number generation.

That is the optimization I meant. Quite short and effective. How much I need to learn!

[Gamo]

Our member Michaelzinn already solve this problem by using single Random with DSE Counter function.
Here is the link:

http://www.hpmuseum.org/forum/thread-10451.html

With that program is it possible to show each dice result then total? His program directly show only the total.

Gamo

[Joe Horn]

(05-02-2018 07:01 AM)Jim Horn Wrote:  If you roll N six sided dice and put them next to each other and write down the values they show *minus 1* each, you'll get an N digit integer in base 6. All such 6^N integers are equally likely for fair dice. So, just find a random number from 0 to (6^N)-1, convert to base 6, add the sum of its digits plus N (to correct the "subtract 1 from each digit") and there you go: the sum of the six rolled dice with only one random number generation.

Of course, converting an integer to base 6 will likely require a loop which can do the running sum of the base 6 integer as it goes (N iterations needed). But still only involves a single random number generation to get all N random dice thrown.

Oh my goodness, that is so cool! Thank you! <scampers off gleefully to code it>

(05-02-2018 10:54 AM)Gamo Wrote:  Our member Michaelzinn already solve this problem by using single Random with DSE Counter function.
Here is the link:
http://www.hpmuseum.org/forum/thread-10451.html

No, that program generates N random numbers and adds them up. That's not what we're looking for here. We're looking for a way to simulate getting the final total by generating only ONE random number. Jim's base 6 idea does that.

[Joe Horn]

(05-02-2018 12:03 PM)Joe Horn Wrote:  <scampers off gleefully to code it>

In CAS view of the HP Prime, this can be implemented in one line. Caution: "convert" must be typed in lowercase or it won't work.

sum(convert(RANDINT(6^N-1),base,6))+N

Unfortunately, this only works up to N=18. The following brute-force sum of N random rolls (which is what I was trying to avoid) works up to N=10000:

sum(RANDINT(N,1,6))

... and it's plenty fast. It returns the sum of 10000 dice rolls in 0.0845 seconds, which is a tad faster than the HP-11C program.

[John Keith]

(05-02-2018 07:01 AM)Jim Horn Wrote:  Of course, converting an integer to base 6 will likely require a loop which can do the running sum of the base 6 integer as it goes (N iterations needed).

Or use the ListExt command I\->BL.

Note also that this method becomes increasingly less accurate with increasing values for N greater than 15 as 6^N will be greater than 10^12 and the random number thus generated will begin to lose significant bits.

John

[Jim Horn]

In theory, theory and practice are the same.
In practice, theory and practice are different.

Thank you for noting that, John! Looks like time for a variable precision math package...

(05-02-2018 02:07 PM)John Keith Wrote:  

(05-02-2018 07:01 AM)Jim Horn Wrote:  Of course, converting an integer to base 6 will likely require a loop which can do the running sum of the base 6 integer as it goes (N iterations needed).

Or use the ListExt command I\->BL.

Note also that this method becomes increasingly less accurate with increasing values for N greater than 15 as 6^N will be greater than 10^12 and the random number thus generated will begin to lose significant bits.

John

[Didier Lachieze]

(05-02-2018 02:00 PM)Joe Horn Wrote:  In CAS view of the HP Prime, this can be implemented in one line. Caution: "convert" must be typed in lowercase or it won't work.

sum(convert(RANDINT(6^N-1),base,6))+N

Unfortunately, this only works up to N=18.

With a single random number you can also do :

sum(convert(rand(6^N)-1,base,6))+N

It works for N up to 1659 but it is much slower than the sum of N random numbers.

[John Keith]

(05-02-2018 06:41 PM)Didier Lachieze Wrote:  With a single random number you can also do :

sum(convert(rand(6^N)-1,base,6))+N

It works for N up to 1659 but it is much slower than the sum of N random numbers.

Interesting, I wonder where the number 1659 comes from. After all, 6^1659 has "only" 1291 digits.

[John Keith]

(05-02-2018 05:58 PM)Jim Horn Wrote:  Looks like time for a variable precision math package...

One could always use LongFloat on the HP 50 but as Didier notes this would be much slower than summing multiple RANDs.

[Dieter]

(05-02-2018 05:06 AM)Joe Horn Wrote:  THE QUESTION: Is there a direct way to return the sum of a roll of N dice without generating N random numbers and adding them together?

Here is another possible method – but I have no idea if it makes sense here. So please correct me if I'm wrong.

Let's assume you roll a really BIG number of dice. Not just 3 or 5, maybe n=10 or 50. According to the central limit theorem this should approximate a Normal distribution. If we assume tossing a single die does not only result in six disctinct outcomes (1, 2, 3, 4, 5, 6) but a continuous result (1...6), the mean is (1+6)/2 = 3,5 and the variance is n · (6–1)²/12. Now simply generate a normally distributed random number, i.e. apply the Normal quantile function (or an approximation thereof) to the usual RAN# result, then rescale it with mean + √var · ran#.

I have tried this on the WP34s and it seems to work fine, even for n as low as 5. Maybe the two parameters require an adjustment (is it 6–1 or 6 in the variance?), but... is the general idea a possible solution, at least for larger n ?

For the record, here is a result for 1000 tosses of 4 dice:

Code:

sum  frequency (w/mod. σ)
-------------------------
4       0         0
5       0         6
6       2        10
7       9        14
8       18       19
9       23       47
10      63       60
11      77       73
12      100      94
13      121     100
14      147     125
15      116      98
16      109      99
17      87       84
18      58       64
19      34       43
20      16       26
21      13       18
22      2         8
23      3         6
24      3         7

Note: the right column shows the frequencies based on the modified variance, i.e. σ² = n · 6²/12.

Edit: for a discrete random variable (1, 2, 3, 4, 5, 6) the variance seems to be 35/12, so I tried another run with σ² = n · 35/12. The results were similar and looked good either.

Dieter

[pier4r]

I thought about the central limit theorem too, but with a mapping of an integer interval to numbers it is already precise. Still having multiple ways is always good, as with the mapping integer: solution you have limits when N is big.

The normal function should always work I think, all the more with many dice.

[Jim Horn]

One minor issue for using a single random number to simulate rolling N dice which each have S sides: if S^N > 10^(number of significant digits), then the simulation fails in that not all possible dice rolls can be represented (the pigeonhole principle). After all, any random number function can only attain a finite number of output values but a large number of dice could exceed that number of states.

I'm sure the statistics of such a limited situation wouldn't be far off of theory, though.

[Csaba Tizedes]

N×3.5
N is the number of dices.

Cs.

[Werner]

(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

[SlideRule]

Very interesting exegesis on the topic.

BEST!
SlideRule