Probability: No of ways to win if you have n dice with m faces each

Question

You are given a number of dices n, each with a number of faces m. You roll all the n dices and note the sum of all the throws you get from rolling each dice. If you get a sum >= x, you win, otherwise you lose. Find the probability that you win.

I thought of generating all combinations of 1 to m ( of size n ) and keeping count of only those whose sum is more then x . Total no of ways are m^n

After that its just the divison of both.

Is there a better way ?

Answer 1

[EDIT: As noted by jpalacek, the time complexity was wrong -- I've now fixed this.]

You can solve this more efficiently with dynamic programming, by first changing it into the question:

How many ways can I get at least x from n dice?

Express this as f(x, n). Then it must be that

f(x, n) = sum(f(x - i, n - 1)) for all 1 <= i <= m.

I.e. if the first die has 1, the remaining n - 1 dice must add up to at least x - 1; if the first die has 2, the remaining n - 1 dice must add up to at least x - 2; and so on.

There are m terms in the sum, so if you memoise this function, it will be O(m^2*n^2), since it will be required to do this summing work at most (m * n) * n times (i.e. once per unique set of inputs to the function, assuming that the first parameter x <= m * n).

As a final step to get a probability, just divide the result of f(x, n) by the total number of possible outcomes, i.e. m^n.

Answer 2

Just to add up on @j_random_hacker's basically correct answer, you can make it even faster when you note that

f(x, n) = f(x-1, n) - f(x-m-1, n-1) + f(x-1, n-1) if x>m+1

This way, you'll only spend O(1) time calculating each of the f value.