Probability Distribution of Dice

[Drawmack]

My earlier algorithm was significantly flawed. Here is how the problem can be done recursivly.

Problem:
Calculate the probability of a given result coming up when rolling xdy.

Solution:
You have a set (A) of dice, each element of A is a set (B) of sides. So we need to calculate the set (C) such that C = all the elements of B such that they can be added to any total produced by summing one element from each set B in A such that the total (F) = our desired result (G)

Extremely Abstract Agorithm

1) Calculate the maximum from the current B that can be added to the minimum of all other Bs to equal G.
2) Calculate the minimum from the current B that can be added to the maximum of all other Bs to equal G.
3) Repeat with each B in A

There are a couple of points about working with dice that make this simpler. Namely we are only working with integers between 1 and n, where n is the number of side the die has. This being the case our minimum (min) is:
1 * number of dice (nd)
and our maximum (max) is:
sum(sides of all dice), except the current one (sd)

We can calculate the minimum roll possible on this die like so:
x = G-(max - current die)
if x < 1 then
x = 1

We can calculate the maximum roll possible on this die like so:
x = G-(min - 1)
if x < 1 then
result is impossible

the tricky part is putting this together recursivly to calculate all of the possible sets for a given number.

I believe this is the quickest way to make a computer handle it.

 

[Drawmack]

I have the algorithm almost complete, just one last problem. It does not account for this being an ordered set. In other words if the combination is 1,1,1 it returns 3 when it should only return 1.

Here is the algorithm with this bug in it.

[color=white]
  function getPossibleCombinations($result,$arySides,$position) {
    if($result < count($arySides)) {return 0;}
    $current = $arySides[$position];
    $min = count($arySides)-1;
    $max = array_sum($arySides) - $current;
    $minCurrent = $result - $max;
    if($minCurrent < 1) {$minCurrent = 1;}
    $maxCurrent = $result - $min;
    if($maxCurrent > $current) {$maxCurrent = $current;}
    $set = $maxCurrent - $minCurrent + 1;
    if($position == (count($arySides)-1)) {return $set;}
    else {return($set + getPossibleCombinations($result,$arySides,$position+1));}
  }
[/color]

I could translate this into pseudocode but this php is so close to pseudocode that seems redundant. If anyone knows how to trim out duplicates of duplicates that would be greatly appreciated.

 

[nsruf]

If anyone knows how to trim out duplicates of duplicates that would be greatly appreciated.

You shouldn't get any duplicates if you consider all 1..p possible values for the first die and call your function recursively p times to get the number of combinations that make up the remainder. However, you get a huge number of function calls. I'd advise you to implement the recursive calculation without actual recursion, sort of like my matlab script does it for n equal dice.

 

[Riveneye]

Wow, I seem to have sparked a lot of interest. I never knew so many people had been wondering the same thing.

Drawmack, could you explain that function a bit? I hate to ask people to comment their work, but i'm just wondering what arguments I'm meant to pass to it. What is the array $arySides? just (1, 2, 3, 4, 5, 6) for a d6? And what is $position? I'd like to help you out with this one, but I think I'm going to need more info before I can. It's starting to get quite confusing with everyone using different notations for number of dice, sides, outcomes etc.

frisbeet, your formulae were very interesting, and are the closest thing I have seen to a perfect solution. If you could fix that one problem, we'd have our formula, and if Drawmack could fix his bug, we'd have a perfect (small) algorithm.

 

[Storminator]

I have a matlab script that implements the idea from my spreadsheet, in a bit more robust form:

[color=white]
function space = recurvp
sides   = input('Input dice sides as a vector:')         % ex: [4 6 6 6] for a d4 and 3d6
n       = length(sides);                                 % n==number of dice
maxroll = sum(sides);                                    % largest roll is the sum of all sides
space   = zeros(n,maxroll);                              % the array with a row(i) being the distribution of the first i dice
space(1,1:sides(1))=1;                                   % the first die has equal probability of getting each number, up to the number of sides it has
for k=2:n                                                % compute the rest of the dice
    for q=k:sum(sides(1:k))                              % compute each possible roll
        minnum=max(1,q-sides(k))                         % Error trap so we don't sum beyond the end of the array
        space(k,q)=sum(space(k-1,minnum:q-1));           % sums up a number of entries from the previous row
    end
end
return
[/color]

You don't really need recursion here. You use recursion when you don't know the answer to the most basic version of the problem, as you have to "unwrap" the problem to its simplest state, solve that, and build up. Here we know the answer to the 1 die problem, so we can start there and build forward. Much simpler.

So mine works on any set of dice (my example in the comment is a d4 and 3d6).

And Frisbeet, the issue is that there are 3 regions of the solution:
oc < s + n -1
s + n -1 < oc < s*(n-1) + 1
s*(n-1) < oc

You had "oc greater than twice s" in your formula because you were checking against three dice.

Try your first formula for the third region, but replace oc with "max-oc" as the distributions should be symmetrical.

PS

 

[nsruf]

So mine works on any set of dice (my example in the comment is a d4 and 3d6).

Good, so I won't have to update my script (which is the same as yours anyway, except for assuming equal dice). Now we only need someone to solve the theoretical problem and give an explicit formula for the number of combinations...

 

[Bugaboo]

It all seems to be a lot of unnecessary, hard work to me. Here's the process I use:

1. Pick up impressive-looking calculator or pocket PC.
2. Poke at keyboard so that others cannot see what you're doing.
3. Furrow brow and frown a little.
4. Poke at machine some more.
5. Look up with a smile and announce some result you think sounds appropriate. Use decimals for greater effect.

Example: "Ah! 97.23 percent!"

 

[nsruf]

It all seems to be a lot of unnecessary, hard work to me. Here's the process I use:...

In this case, might I interest you in this little private lottery game I offer...

 

[Storminator]

It all seems to be a lot of unnecessary, hard work to me. Here's the process I use:

1. Pick up impressive-looking calculator or pocket PC.
2. Poke at keyboard so that others cannot see what you're doing.
3. Furrow brow and frown a little.
4. Poke at machine some more.
5. Look up with a smile and announce some result you think sounds appropriate. Use decimals for greater effect.

Example: "Ah! 97.23 percent!"

That just proves the conjecture that 42.64% of all statistics are made up on the spot!

PS

 

[Drawmack]

First I have optimized the recursion so you only call it once for each die in your initial set. For example 100d10 would call this 100 times, for each result you queried it for.

[color=white]
  function getPossibleCombinations($result,$arySides,$position) {
    if($result < count($arySides)) {return 0;}
    $current = $arySides[$position];
    $min = count($arySides)-1;
    $max = array_sum($arySides) - $current;
    $minCurrent = $result - $max;
    if($minCurrent < 1) {$minCurrent = 1;}
    $maxCurrent = $result - $min;
    if($maxCurrent > $current) {$maxCurrent = $current;}
    $set = $maxCurrent - $minCurrent + 1;
    if($position == (count($arySides)-1)) {return $set;}
    else {return($set + getPossibleCombinations($result,$arySides,$position+1));}
  }
[/color]

Code explained:
$result = the result you a querying for the number of sets that will produce it.
$arySides = is an array that holds the number of sides on your die. (i.e. (4,6,6,8) would be 1d4, 2d6, 1d8)
$position = which die you are looking at on this iteration, always 0 when you call the function it just uses it internally so it must be there.

now that the parameters are out of the way here's how the algorithm works
test the requested result for existenc in the supplied array
get the number of sides on the die for this iteration
calculate the minimum that can be rolled excluding this die
calculate the maximum that can be rolled excluding this die
calculate the minimum that is needed from this die to roll result
make sure minimum is 1
calculate the maximum that can be rolled from this die to roll result
make sure maximum is <= die sides
calculate the size of the set that can be used from this die
either return set
or return set * call function again with the next position.

The problem with the algorithm is that is counts doubles, tripples, etc. multiple times and I don't know how to make that stop.

for example rolling 3d4 and query for 3. We all know the answer is 1, however with this algorithm it reports 3 because each 1 can be in any position.