Disclaimer: I'm a computer programmer more than a mathematician, so reading text like that of the answer to this question is a little (read: a lot) over my head.
I've written an algorithm (brute-force, O(nk) running time, where n is the number of dice, and k is the number of sides) that calculates the probability of rolling each possible value of a specified number of dice, each of may have a different number of faces. For example, rolling
d8 + 2d20 (1 8-sided die and 2 20-sided dice) has a minimum roll of
3 and a maximum roll of
48, each of which have a probability of
0.0003125. The values
26 are most likely to show up, each with a probability of
I'm wondering if there's a way, without doing the full calculation, to determine--or make a conservative estimate of--this maximum value of
0.045 in polynomial time. I know that this is also the probability of rolling the middle value, or
ceiling((max - min) / 2) + min.
I've written a probability distribution graph using jQuery Flot. Since this is such a long running calculation for large numbers of dice with large numbers of sides (e.g.
4d100), I calculate the distribution in chunks, and update the graph periodically. I'd like to have a maximum probability calculated ahead of time so the axes don't change as I make updates to the data.
Calculating the total number of permutations is obviously easy--multiple each die's number of sides together--so calculating the probability of any one permutation is
1 / totalPermutations. That's about as far as I got. Help?