3
$\begingroup$

I have a random number generator as part of a system that - putatively - randomly selects one of 10,000 drive locations to store an incoming file fragment. Multiple file fragments can fill a drive location. For simplicity, let's say it's a short time window and thus there is no ceiling on number of fragments stored per location. Say that this system receives 1,000,000 file fragments in a given time period of operation.

I would expect a uniform distribution across the 10,000 locations if the system is working correctly (with some spread due to chance), but I am not sure how I would go about testing this. Would this simply be a $\chi^2$ test with 10,000 bins and an expected value of 100 fragments per bin? Then if I fail to reject the null hypothesis I can assume a sufficiently uniform distribution of fragments?

If the above is correct, how would I go about finding the point at which I can no longer assume uniformity without re-calculating $\chi^2$ using each bin? I can get alerts when a drive is above a threshold number of fragments relative to the number of fragments parsed. Say that if $5\%$ of my drive locations have more than $\mu+x$ fragments I can assume there is a deviation from random assignment; what is $x$?

$\endgroup$
1
  • 1
    $\begingroup$ Kolmogorov-smirnov test could be what you're looking for? $\endgroup$ – David Kozak Jun 28 '17 at 21:54
2
$\begingroup$

What you propose looks OK. Since there is no estimated parameters, the number of degrees of freedom should be $10000 - 1$. Then you can find p-values from the $\chi^2_{9999}$ distribution.

But your last paragraph indicated the setting is different:

I can get alerts when a drive is above a threshold number of fragments relative to the number of fragments parsed.

So your situation is online, with information arriving continuously. That is often treated by s, but I don't know how you would compute control limits for such a chart. Alternatively, see it as a problem of sequential testing. Here is a paper discussing a sequential version of the chi-square test.

$\endgroup$

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.