An algorithm to calculate probability of a sum of the results happening

Question

The algorithm I'm talking about using would allow you to present it with x number of items with each having a range of a to b with the result being y. I would like to have an algorithm which would, when presented with the values as described would output the possibility of it happening.

For example, for two die. Since I already know them(due to the possible results being so low). It'd be able to tell you each of the possibilities.

The setup would be something like. x=2 a=1 b=6. If you wanted to know the chance of having it result in a 2. Then it'd simply spit out 1/36(or it's float value). If you put in 7 as the total sum, it'd tell you 6.

So my question is, is there a simple way to implement such a thing via an algorithm that is already written. Or does one have to go through every single iteration of each and every item to get the total number of combinations for each value.

The exact formula would also, give you the combinations to make each of the values from 1-12.

So it'd give you a distribution array with each one's combinations at each of the indexes. If it does 0-12. Then 0 would have 0, 1 would have 0, and 2 would have 1.

I feel like this is the type of problem that someone else has had and wanted to work with and has the algorithm already done. If anyone has an easy way to do this beyond simply just looping through every possible value would be awesome.

I have no idea why I want to have this problem solved, but for some reason today I just had this feeling of wanting to solve it. And since I've been googling, and using wolfram alpha, along with trying it myself. I think it's time to concede defeat and ask the community.

I'd like the algorithm to be in c, or maybe PHP(even though I'd rather it not be since it's a lot slower). The reason for c is simply because I want raw speed, and I don't want to have to deal with classes or objects.

Pseudo code, or C is the best ways show your algorithm.

Edit:

Also, if I offended the person with a 'b' in his name due to the thing about mathematics I'm sorry. Since I didn't mean to offend, but I wanted to just state that I didn't understand it. But the answer could've stayed on there since I'm sure there are people who might come to this question and understand the mathematics behind it.

Also I cannot decide which way that I want to code this up. I think I'll try using both and then decide which one I like more to see/use inside of my little library.

The final thing that I forgot to say is that, calculus is about four going on five years ago. My understanding of probability, statistics, and randomness come from my own learning via looking at code/reading wikipedia/reading books.

If anyone is curious what sparked this question. I had a book that I was putting off reading called The Drunkards Walk and then once I say XKCD 904, I decided it was time to finally get around to reading it. Then two nights ago, whilst I was going to sleep... I had pondered how to solve this question via a simple algorithm and was able to think of one.

My coding understanding of code comes from tinkering with other programs, seeing what happened when I broke something, and then trying my own things whilst looking over the documentation for the build in functions. I do understand big O notation from reading over wikipedia(as much as one can from that), and pseudo code was because it's so similar to python. I myself, cannot write pseudo code(or says the teachers in college). I kept getting notes like "make it less like real code make it more like pseudo code." That thing hasn't changed.

Edit 2: Incase anyone searching for this question just quickly wanted the code. I've included it below. It is licensed under the LGPLv3 since I'm sure that there exists closed-source equivalents of this code.

It should be fairly portable since it is written entirely in c. If one was wanting to make it into an extension in any of the various languages that are written in c, it should take very little effort to do so. I chose to 'mark' the first one that linked to "Ask Dr. Math" as the answer since it was the implementation that I have used for this question.

The first file's name is "sum_probability.c"

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

/*!
*    file_name: sum_probability.c
*    
*    Set of functions to calculate the probabilty of n number of items adding up to s
*    with sides x. The question that this program relates to can be found at the url of
*    http://stackoverflow.com/questions/6394120/
*    
*     Copyright 2011-2019, Macarthur Inbody
*    
*   This program is free software: you can redistribute it and/or modify
*   it under the terms of the Lesser GNU General Public License as published by
*   the Free Software Foundation, either version 3 of the License, or
*   (at your option) any later version.
*
*   This program is distributed in the hope that it will be useful,
*   but WITHOUT ANY WARRANTY; without even the implied warranty of
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*   GNU General Public License for more details.
*
*   You should have received a copy of the Lesser GNU General Public License
*   along with this program.  If not, see <http://www.gnu.org/licenses/lgpl-3.0.html>.
*     
*   2011-06-20 06:03:57 PM -0400
*    
*   These functions work by any input that is provided. For a function demonstrating it.
*   Please look at the second source file at the post of the question on stack overflow.
*   It also includes an answer for implenting it using recursion if that is your favored
*   way of doing it. I personally do not feel comfortable working with recursion so that is
*   why I went with the implementation that I have included.
*
*/

/*
* The following functions implement falling factorials so that we can
* do binomial coefficients more quickly.
* Via the following formula.
*
*   K
*  PROD    (n-(k-i))/i
*   i=1;
*
*/

//unsigned int return
unsigned int m_product_c( int k,  int n){
    int i=1;
    float result=1;
    for(i=1;i<=k;++i){
        result=((n-(k-i))/i)*result;
    }
    return result;
}

//float return
float m_product_cf(float n, float k){
    int i=1;
    float result=1;
    for(i=1;i<=k;++i){
        result=((n-(k-i))/i)*result;
    }
    return result;
}


/*
* The following functions calculates the probability of n items with x sides
* that add up to a value of s. The formula for this is included below.
*
* The formula comes from. http://mathforum.org/library/drmath/view/52207.html
*
*s=sum
*n=number of items
*x=sides
*(s-n)/x
* SUM  (-1)^k * C(n,k) * C(s-x*k-1,n-1)
* k=0
*
*/

float chance_calc_single(float min, float max, float amount, float desired_result){
    float range=(max-min)+1;
    float series=ceil((desired_result-amount)/range);
    float i;
    --amount;
    float chances=0.0;
    for(i=0;i<=series;++i){
        chances=pow((-1),i)*m_product_cf(amount,i)*m_product_cf(desired_result-(range*i)-1,amount)+chances;
    }
    return chances;
}

And here is the file that shows the implementation as I said in the previous file.

#include "sum_probability.c"

/*
* 
* file_name:test.c
*
* Function showing off the algorithms working. User provides input via a cli
* And it will give you the final result.
*
*/
int main(void){
        int amount,min,max,desired_results;
        printf("%s","Please enter the amount of items.\n");
        scanf("%i",&amount);
        printf("%s","Please enter the minimum value allowed.\n");
        scanf("%i",&min);
        printf("%s","Please enter the maximum value allowed.\n");
        scanf("%i",&max);
        printf("%s","Please enter the value you wish to have them add up to. \n");
        scanf("%i",&desired_results);
        printf("The total chances for %i is %f.\n", desired_results, chance_calc_single(min, max, amount, desired_results));
}

Answer 1

First of all, you do not need to worry about the range being from a to b. You can just subtract a*x from y and pretend the range goes from 0 to b-a. (Because each item contributes at least a to the sum... So you can subtract off that a once for each of your x items.)

Second, note that what you are really trying to do is count the number of ways of achieving a particular sum. The probability is just that count divided by a simple exponential (b-a+1)^x.

This problem was covered by "Ask Dr. Math" around a decade ago:

http://mathforum.org/library/drmath/view/52207.html

His formulation is assuming dice numbered from 1 to X, so to use his answer, you probably want to shift your range by a-1 (rather than a) to convert it into that form.

His derivation uses generating functions which I feel deserve a little explanation. The idea is to define a polynomial f(z) such that the coefficient on z^n is the number of ways of rolling n. For a single 6-sided die, for example, this is the generating function:

z + z^2 + z^3 + z^4 + z^5 + z^6

...because there is one way of rolling each number from 1 to 6, and zero ways of rolling anything else.

Now, if you have two generating functions g(z) and h(z) for two sets of dice, it turns out the generating function for the union of those sets is just the product of g and h. (Stare at the "multiply two polynomials" operation for a while to convince yourself this is true.) For example, for two dice, we can just square the above expression to get:

z^2 + 2z^3 + 3z^4 +4z^5 + 5z^6 + 6z^7 + 5z^8 + 4z^9 + 3z^10 + 2z^11 + z^12

Notice how we can read the number of combinations directly off of the coefficients: 1 way to get a 2 (1*z^2), 6 ways to get a 7 (6*z^7), etc.

The cube of the expression would give us the generating function for three dice; the fourth power, four dice; and so on.

The power of this formulation comes when you write the generating functions in closed form, multiply, and then expand them again using the Binomial Theorem. I defer to Dr. Math's explanation for the details.