# How to calculate Mean of a giant Array of Integers with unknown distribution and standard deviation?

I have a giant array of integer numbers like this:

giantArray = [2048,128,512,512,128,8,....]


The content of this array changes every day and I need to estimate its mean really quick. I have limited processing resource for this job. Moreover, there is no guarantee that distribution and standard deviation of the array remain the same every day. The smallest integer in the array is 8 and the largest one is 2048. All other integers are the power of two numbers.

The size of the array is about 500 million entry and I cannot afford to read it all. Therefore, I think, I need to use simple random samples (SRS) to estimate the Sample mean.

However, Since I don't know my standard deviation I cannot calculate how big should be my minimum sample size for a given confidence level of 95% and error margin of +/- 8.

Do you know how can I calculate the standard deviation and then determined the minimum sample size?

Can I use this online algorithm to calculate standard deviation during sampling time and then use it to find out If I have sampled enough?

• How many entries can you afford to read? Must they be sequential? (if so, this will not be a random sample) Note also that the maximum standard deviation would be when the data is evenly split between max and min, so it will be less than 1024 (e.g. see here). – GeoMatt22 Apr 25 '17 at 4:55
• You can create a 95% confidence interval of the mean by taking a single random value from this array. It will be a very broad interval! The larger the sample size, the narrower the confidence interval will tend to be. How narrow would you like it to be? – whuber Apr 25 '17 at 14:52
• You could compute variance online or use the worst-case upper bound of $\sigma<1024$ that I gave before (like whuber suggested). You will have to judge if the extra computation required for the online variance calculation and convergence test is worth it. – GeoMatt22 Apr 25 '17 at 17:20
• This may help clarify? – GeoMatt22 Apr 25 '17 at 18:02
• If you are sampling only a small fraction of the population, there is no finite-population correction needed. The finite-population correction comes in only when the sample is too large relative to the population, e.g. as the linked question notes, if the sample is the population then there is obviously no error at all in the "estimated" mean. By the way, you should probably update your question to include your desired confidence interval (95%) and margin of error (+/-8), and perhaps also your maximum # samples constraint (e.g. 100k?). – GeoMatt22 Apr 25 '17 at 18:27

Since the array entries $x\in[8,2048]$ are bounded, then no matter what their frequency distribution is, the maximum standard deviation is $$\sigma_x\leq\frac{x_\max-x_\min}{2}=\frac{2048-8}{2}=1020$$ So for a random sample of size $n$ the standard deviation of the sample mean is bounded by $$\sigma_\bar{x}=\frac{\sigma_x}{\sqrt{n}}\leq\frac{1020}{\sqrt{n}}$$ Assuming that $n$ is large enough so that $\bar{x}$ is approximately normal, then for a 95% confidence interval of $\pm{8}$, you have $$1.96\times\sigma_\bar{x}\approx{8}\implies{n}\approx{62450}$$ So as noted in the comments, $n=63000$ is enough samples to ensure your required bound.
• This is an awesome technical answer, but I think it's important to emphasize that $n = 62,450$ is a minimum value. And it's a pretty small minimum. OP could probably get away with sampling a half-million on a local computer. Probably a lot more. – Tim Atreides Apr 25 '17 at 20:15
• ARH, it is simply an alternative notation, your link just uses it without introducing a new symbol: $\sigma/\sqrt{n}$ is $\sigma_\bar{x}$. – GeoMatt22 Apr 26 '17 at 14:25