Suppose that I have $n$ different sets of numbers , each containing $m$ different numbers and I can only form sums of $n$ numbers by choosing only one element of each set. Is there an easy way to find the standard deviation of the sums or even an approximation especially if the set of sums increases exponentially and reaches huge numbers (in my case $300 \times 10^6$) .
Asked
Active
Viewed 95 times
2
-
Are the sets of numbers independent of each other? – Marc Mar 31 '14 at 14:05
-
Are the sets i.i.d.? – Eric Towers Apr 29 '14 at 07:55
1 Answers
0
Enumerating all possible combinations does not scale computationally. The simplest solution I can think of is to use Monte Carlo method. Take $K$ random selections and estimate standard deviation from only those samples. The error in the estimate should decrease exponentially, so you wouldn't need all the samples.
If your sets are independent, you could estimate the variance of each set and sum it up, but I guess that is not the case (it's super easy). In any case, it would give you an upper bound.
Memming
- 2,028
- 15
- 25