Suppose we have a data stream which outputs integer values from $0$ to $2^{32}-1$. We know that either (A) all values occur equally often or (B) exactly half of the values occur $2^{10}$ times more often than the other half (but it is unknown which values are more likely).

I'd like to know how I can approach whether (A) or (B) is true. Also, I've been asked to state how many values I would need to observe to be confident of my result with a probability of $0.999$. Moreover, assume we can only observe up to $2^{18}$ values.

My rough attempt at a solution. We gather a certain amount of data, for example $2^{10} = 1024$ integers. We then record how many of these fall in the first half of possible values, that is $0$ to $2^{31}-1$. If (A) is true, all values are equally likely so one would expect to see around $512$ fall in this half. If (B) is true, the expected value could be anything so we would almost definitely get a very different amount.

This method makes sense to me but I don't know how many values I would need to observe to be confident enough to say the result is true with probability $0.999$. I've been told it is something to do with using the 3-sigma rule for a normal distribution but I'm not sure how I should apply this here.

Any tips would be greatly appreciated.

  • $\begingroup$ Hint: what do you expect to get if you sample N values and add them together? $\endgroup$ – Thanassis Dec 29 '16 at 12:33
  • $\begingroup$ That above hint can be used if you want to employ normal distribution properties (do you see how?) . I think it's more straightforward to directly calculate the probability of certain events happening (or not) $\endgroup$ – Thanassis Dec 29 '16 at 12:44
  • $\begingroup$ Regarding the hint, I imagine I would use the central limit theorem so I could then work with a normal distribution. But I'm still unclear how to proceed with that. Could you maybe suggest a "certain event" I should try calculating the probability of to start me off. $\endgroup$ – Myopic Dec 29 '16 at 17:10
  • $\begingroup$ Correct, you can use the central limit theorem. No need to think of "certain events" this way (my comment about that was for another method). Just find how your normal distributions will look like if you add 50 samples, depending on which of the three cases is true (numbers from whole interval, bottom half, top half). How much are they "separated". What if you add 100 samples? $\endgroup$ – Thanassis Dec 29 '16 at 23:45
  • $\begingroup$ As more and more samples are added I would expect to see the mean of the normal distributions converge to the central value of the interval (if case (A) is true). I still don't know how to make this rigorous though to get the required result of being 99.9% certain $\endgroup$ – Myopic Dec 31 '16 at 12:29

Your Answer

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

Browse other questions tagged or ask your own question.