How to make a hypothesis test for a simple statistical test for a certain RNG? I'm self-studying about hypothesis test in the context of RNGs.  I'm building a hypothesis test from scratch.  I'm taking the simplest statistical test I can think of: how many $1$s are there in the sequence sample?  My null hypothesis is that the RNG is uniform, so I expect the average number of $1$s to be close to $n/2$, where $n$ is the size of the sample.

I believe (or I guess) the sample averages should follow a normal distribution.  To implement the hypothesis test, I will have to know the variance, though.  

What should I do here?  Should I look at a good RNG and come up with a variance relative to my simple statistical test?  This makes sense to me.  A good RNG will likely present averages close to $n/2$, specially if $n$ is large.  I could then empirically determine the variance this way.

Is there anything wrong with this construction?  Can you advise?  My main interest is not in testing real world RNGs.  My main interest is in knowing how to do hypothesis test, but I'm looking for an example in this precise context.
The number of one bits in a sequence of iid Bernoulli trials won't be normal: it will be binomial.  But you have the right intuition that, as the number of bits grows, the binomial distribution converges to a normal distribution—specifically, for fixed $p$, as $n \to \infty$, $$\operatorname{Binom}(n, p) \to \mathcal N\bigl(np, np(1 - p)\bigr),$$ or, more precisely and with less abuse of notation, if $X_n \sim \operatorname{Binom}(n, p)$, then $(X_n - np)/\sqrt{np(1 - p)} \to Z$ where $Z \sim \mathcal N(0, 1)$ is a standard normal.  This is a standard theorem of probability theory, the de Moivre–Laplace theorem; see, e.g., Feller, Vol. I, Ch. VII, ‘The Normal Approximation to the Binomial Distribution’, for an introduction.

That said, once you have decided on your test statistic and cutoff for a prescribed false alarm rate (‘statistical significance’), your job is not done: you should also have alternative hypotheses for the bugs you might have in your software, or physical defects you might have in your hardware.  For instance, will you detect deterministic alternating 0/1 bits?

The hypothesis test is valuable only insofar as it distinguishes plausible nonuniform distributions from uniform ones.  After all, if all you want is a hypothesis test with statistical significance 0.05 like any good little psychology journal, you could ignore the data altogether, roll a d20, and raise an alarm if you rolled a 1.


If you're talking about a pseudorandom generator, which is a deterministic function of a key, then your hypothesis test should be designed with knowledge of the function.
If you're talking about a hardware entropy source, which is a physical process, then your hypothesis test should be designed with knowledge of the physics.


If you just count bits and apply a test for goodness-of-fit in terms of the ratio of zeros to ones with significance level 0.05, and stop there, you've only made an entertaining way to implement a d20 in software.