3
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ 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). $\endgroup$
    – GeoMatt22
    Apr 25, 2017 at 4:55
  • 1
    $\begingroup$ 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? $\endgroup$
    – whuber ♦
    Apr 25, 2017 at 14:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – GeoMatt22
    Apr 25, 2017 at 17:20
  • 1
    $\begingroup$ This may help clarify? $\endgroup$
    – GeoMatt22
    Apr 25, 2017 at 18:02
  • 2
    $\begingroup$ 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?). $\endgroup$
    – GeoMatt22
    Apr 25, 2017 at 18:27

1 Answer 1

Reset to default
4
$\begingroup$

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.

You could compute variance online to get a better estimate, but you will have to judge if the extra computation required for the online variance calculation and convergence test is worth it.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tim Atreides
    Apr 25, 2017 at 20:15
  • 1
    $\begingroup$ @TimAtreides the OP's constraints are not clear to me. (In the comments my first question was if random access was allowed, vs. sequential access e.g. in some embedded system). I would suggest that if it is at all possible to save all the numbers for a sample of days, then an (offline) validation study would be good to do, to give confidence in the online (production/deployed) approach. $\endgroup$
    – GeoMatt22
    Apr 25, 2017 at 20:21
  • 2
    $\begingroup$ +1. Some comments: (1) @Tim the 62000 value is a maximum because it is based on the largest possible variance. The actual variance likely is much smaller. (2) I don't think you have to worry about normality, given the bounds on the possible values of the data. (3) A sequential sampling procedure easily could stop after a few dozen or few hundred observations. (4) A two-phase procedure would be routine: sample, say, 30 values; estimate the variance from those; use that to (overestimate) the sample size needed; and collect the required sample. It's highly likely to be much less than 62000. $\endgroup$
    – whuber ♦
    Apr 25, 2017 at 20:32
  • 1
    $\begingroup$ There is no null hypothesis, because this procedure is designed to estimate a value. Sequential sampling will give you the smallest expected sample size, but on rare occasions it could require larger samples than recommended by traditional fixed-size designs. If this is something you will be repeating over and over, a sequential sampling method would be an excellent choice. Based on the (few) numbers you gave in the question, it looks like your sample sizes would be up to a few thousand, but unlikely any greater than that. $\endgroup$
    – whuber ♦
    Apr 26, 2017 at 14:02
  • 1
    $\begingroup$ ARH, it is simply an alternative notation, your link just uses it without introducing a new symbol: $\sigma/\sqrt{n}$ is $\sigma_\bar{x}$. $\endgroup$
    – GeoMatt22
    Apr 26, 2017 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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