Suppose I have N sets of numbers (10 numbers per set) {a1, ....., a10}. I form a sum by taking one number at random from each set. SUM = num from set 1 +......+ num from set N. If I do this a large number of times I will generate a large number of different values for the SUM variable. How can I estimate the distribution of the SUM values (P10, P50, P90 etc.)?

  • $\begingroup$ First of all, you haven't defined a distribution, but I'm assuming that you're picking the number uniformly and independently. Second, what do you mean by "estimate the distribution of Sum"? What kind of answer are you looking for? $\endgroup$ – Yuval Filmus May 11 '15 at 14:23

Use a convolution.

For instance, write the generating function for each set, then multiply the generating functions; this gives you the generating function for the distribution of the sum.

This gives you the exact distribution (which is even better than an approximation!).

| cite | improve this answer | |
  • $\begingroup$ D.W. In order to find the exact distribution of the values of SUM would I not have to evaluate all possible combinations of the summed values/ $\endgroup$ – David Wilkinson May 12 '15 at 15:06
  • $\begingroup$ @DavidWilkinson, no, you would not. My answer describes how to do it, without evaluating all combinations. I recommend you read about convolutions and generating functions, if you're not already familiar with the subject, as they solve exactly this problem in an elegant, efficient way. $\endgroup$ – D.W. May 13 '15 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.