Probability Distribution of Dice

[Drawmack]

You could do it recursively. The probability of rolling 7 of 3d6 is the probability of rolling a 1 on one die times the probability of rolling 6 on 2d6, plus the probability of rolling a 2 on one die times the probability of rolling 5 on 2d6 ...

Might make for a quicker computation of very large sample spaces (frex 42d20).

PS

This truly is an interesting method. The problem comes when you have to factor the original number.

For example 42d20 and you want the probability of rolling 104. You have to first calculate every combination that would yield 104 which brings us right back to the initial problem. Also using recursion on this could cause the person to run out of stack space and that's just not a good thing.

 

[Kugar]

s = sides
n = number of dice
p = probability
tr = total sets to this result
tc = total sets
r = result
nr = number of results


-snip-
Here is what we think we've got so far
Max = s + n -1

The total number of results is s * n - n
The total number of combinations is s^n
-snip-

It appears that the maximum happens at n * (s-1).

I think the general term is max = n*(s+1)/2
In my 4d6 analysis I get the max being 14. Dead on your formula gives 20 not correct.
There is some interesting things happening. I am more sure that the number of dice somehow relate to the order of the expression, but I also think we need some sort of factorial expressions or series expansions because of the discrete nature of the problem.

 

[Drawmack]

I think the general term is max = n*(s+1)/2
In my 4d6 analysis I get the max being 14. Dead on your formula gives 20 not correct.
There is some interesting things happening. I am more sure that the number of dice somehow relate to the order of the expression, but I also think we need some sort of factorial expressions or series expansions because of the discrete nature of the problem.

The more dice you roll the closer to the bell curve you get, big surprise right - the larger the sample the more acurate the results.

It is a discrete problem, if we haven't arrived at an answer by tomorrow night, first chance I have, I'll dig out my discrete textbook and see if I can find an answer to the problem in there.

As it is a bell curve I am at a loss for calculating the number of sets that produce a given result.

 

[Storminator]

I think the general term is max = n*(s+1)/2
In my 4d6 analysis I get the max being 14. Dead on your formula gives 20 not correct.
There is some interesting things happening. I am more sure that the number of dice somehow relate to the order of the expression, but I also think we need some sort of factorial expressions or series expansions because of the discrete nature of the problem.

His formula worked for his example because he had 3 sided dice. In that case s-1=(s+1)/2

In general Kugar's formula is correct.

PS

 

[Drawmack]

So our mean is n * (s+1)/2 no all we need is the standard derviation based on sides and number rolled.

 

[Storminator]

Hey! This is slick. Hopefully I can convey the idea:

In the attached sheet I built up Drawmack's "tr" recursively.

In the 1d6 column are the number of ways a d6 can come up. Only 1-6 have values, and those are all one. The 2d6 column has the "tr" for 2d6. Check out the formula in cell C8.

It sums 6 numbers from the previous column (because each die is a d6). The minimum number rolled on the 2nd die is 1, so we look up one row in the previous column. Once the basic pattern is established (back one column, six previous rows), the exact same formula is applied to every cell.

Did that hurt anyone's brain? I sure tortured mine trying to explain. Just look at the sheet, and absorb it. It certainly isn't general, but it looks like a really cool way to figure these out.

PS

 

[Drawmack]

Let me start by saying there is a recursive algorithm at the end for those who wish to skip the logic that brought me to that algorithm. Now on with the insanly long post.

Taken From Discrete Mathematics (Fourth Edition) by: Kenneth A. Ross & Charles R.B. Wright ISBN: 0-13-096141-8

Pg. 294
How many numbers in {1, 2, 3,…, 100000}have the property that the sum of their digits is 7? We can ignore the very last number, 100000, and we can assume that all the numbers have five digits, by placing zeros in front it necessary. So, for example, we replaces 1 by 00001 and 73 00073. Our question is now: How many strings of five digits have the property that the sum of their digits is 7? We can associate each such string with the placement of seven balls in five boxes; for example,

00142 --> | | |*|****|**|
30121 --> |***| |*|**|*|

There are 11 choose 4 (could not do mathematical formatting in the boards) = 330 = 11!/(11-4)! * 4! such placements, so there are 330 numbers with the desired property.

We can also take objets out of their boxes. Assume that each of k boxes contains an unlimited suppy of objects labeled according to which box they are in. Applying the principle in reverse, we see that there are (n+k-1) choose (k-1) ways to remove n objects from the k boxes. In other words,

Fact. The number of ways to select a set of n objects of k distinguishable types, allowing repetitions, is (n+k-1) choose (k-1) = (n+k-1) choose n.

As has been previously noted this is in fact a heavily factorial problem.

Question: Where do the 11 and the 4 come from?
Answer: 11 = (7+5-1) = (result + set length – 1) and 4 = (5 – 1) = (set length -1)

Question: Will this formula need to be modified to work with dice?
Short Answer: I don’t know.
Long Answer: This formula is known to with when your possible value for each element in the set is 0 – 9 (i.e. d10 where 0 = 0). So it will work on calculating the probability of a d10 if we take into account that 10 = 0 when we query for the probability of a desired number. However with dice you have can have a value for each element in the set of n, where n is the number of sides on the die being represented. Eliminating zeros eliminates a lot of possibilities and therefore means that this formula will need to be modified but this can get us working in the appropriate direction.

Also this has lead me to more thinking on the idea of a recursive algorithm to solve this problem of the number of sets possible.

[color=white]
getPossibleCombinations (desiredMin,desiredMax,arySides)
  thisDie = pop(arySides)
  desiredMax = desiredMax – 1
  possibleMax = total(arySides)
  possibleMin = count(arySides)
  i = 0
  while((thisDie – i  + possibleMin) > desiredMax)
     i++
  return (thisDie-1) * getPossibleCombinations((desiredMax – thisDie), desiredMax – 1,arySides)
[/color]

This function should yield us the number of possible combinations that will yield any result. I would still like a mathematical formula to accomplish this, but this function is easy enough to implement. That is if it’s correct.

I'm going to implement this formula on a php page now, shouldn't take long, and when I'm done I'll post the link so we can all go beat up on it and see if it really works.

 

[Drawmack]

before anyone else says it I could a couple of errors in my algorithm as I was typing it in and there are some more to work out. I will post when I get the page working and at that point I'll include the completed algorithm as well.

 

[frisbeet]

In the spirit of Drawmack's posts, particularily the discrete mathematics ref., help me with this:

oc = outcome
n = number of identical dice
s = number of sides on die

Then sometimes,

#ways=

(oc-1)!/[(oc-n)!(n-1)!] - n*(oc-s-1)!/[(oc-n-s)!(n-1)!]

So for 3d12, the # of ways of getting a 19 is 108.

But if (oc-n)<(s-1), it's just

#ways=

(oc-1)!/[(oc-n)!(n-1)!]

On the other hand, if oc is more than twice s, the n*(oc-s-1)!/[(oc-n-s)!(n-1)!] overcorrects. That's where I'm stuck and should get some sleep.

 

[nsruf]

Here is a matlab function that should do the trick with a time complexity of (p^2)*(n^2) instead of the awful p^n for complete enumeration. So you can calculate the probabilities for a moderate number of dice (e.g. 10d6) in reasonable time. It uses a recursive scheme without actual recursion:


function d = roll(n, p)
% determine probabilities to roll less than
% or equal to any number with n p-sided dice

N = n * p;
% maximal roll result

last = [ones(1, p), zeros(1, N - p)];
% contains the number of combinations
% for rolling a given number found in the
% previous iteration of the outer for-loop;
% initialized with the single die roll

next = zeros(1, N);
% contains the number of combinations
% for rolling a given number if you add
% one more die

for i = 2:n;
% number of dice considered for
% calculating next

mu = ceil((p + 1) * i / 2);
% expectation value, rounded up

for j = i:mu; for k = 1;
% determine values in next up to expectation
% mu; k is the number rolled on the additional
% die

if j - k >= i - 1;
% if it is possible to roll k on one die and
% still get a result of j

next(j) = next(j) + last(j - k);
% add the number of possibilities to roll
% (j - k) with (i - 1) dice

end; end; end;

I = i * p;
% maximal roll on i dice

for j = (mu + 1):I;
% determine remaining values in next

next(j) = next(I + i - j);
% find values larger then mu by symmetry

end;

last = next;

next = zeros(1, N);

end;

d = cumsum(last) / (p ^ n);
% probability to roll less is cumulative sum
% divided by total number of combinations

d = [n:N; d(n:N)];
% first row of output contains possible rolls,
% second row contains probability to roll
% equal or less