3
$\begingroup$

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.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Computing the variance for a random sample is easy; you can compute the variance for a single bit, and for $n$ independent random variables $X_1, …, X_n$, we have $\text{Var}( \sum_{i=1}^n X_i ) = \sum_{i=1}^n \text{Var}( X_i )$ $\endgroup$ – poncho Apr 13 '19 at 14:59
3
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ There are various things I couldn't understand in your answer. (By the way, my objective is to just know how to implement a hypothesis test. I'm not seriously designing a test for an RNG.) I don't understand why I'd be implementing a d20. Also, if I rolled a 1, that'd be usual business. Can you clarify these things? Also, I won't determine alternating 0/1 because my test doesn't account for that. Thanks! $\endgroup$ – user45491 Apr 13 '19 at 16:34
  • $\begingroup$ I looked at a good RNG and I took $10$ samples of length $100$ and looked at their means and variance. The mean is usually between $0.4$ and $0.6$ and the variance is very close to $0.25$. I defined $H_0 := \text{RNG is really random}$. I define my standard normal variable $Z := (X - 0.5)/\sqrt{0.25})$, but the probability of my error type $1$ is $P(Z \leq 0\:|\: H_0) = 0.$ I don't think zero is a good answer here. I'm still trying to situate myself here. Thanks! $\endgroup$ – user45491 Apr 13 '19 at 17:28
  • 1
    $\begingroup$ @user45491 The type I error rate is precisely the statistical significance level. Rolling a d20 and rejecting the null hypothesis if you get a 1, without any reference to the data in front of you, is a test with a type I error rate of 0.05, the standard for many publications. If this seems pathological because you're ignoring the data altogether, your feeling is correct: the point is that focusing solely on a null hypothesis means nothing on its own. To give any practical meaning to the test, you need to have alternative hypotheses in mind that you're aiming to distinguish. $\endgroup$ – Squeamish Ossifrage Apr 14 '19 at 0:47
  • 1
    $\begingroup$ @user45491 I suggest you avoid phrases like ‘really random’, and instead say what distribution you mean: here, I assume you mean $H_0$ is that the RNG outputs are iid fair Bernoulli trials. What is $X$? Is it the number of one bits in 100 outputs? The fraction of one bits? Something else? How do you conclude $P(Z \leq 0 \mid H_0) = 0$? What is the statistical test you are applying? Not just the test statistic, but the test: under what circumstances do you raise an alarm (reject the null hypothesis), and under what circumstances do you decline to raise an alarm? $\endgroup$ – Squeamish Ossifrage Apr 14 '19 at 0:56
  • $\begingroup$ @user45491 It sounds like maybe what you're going for to test the null hypothesis of iid Bernoulli trials with weight $p$ is to count the number $X$ of one bits among $n$ trials, compute $Z := (X - np)/\sqrt{np(1 - p)}$, and reject if $|Z| > |\Phi^{-1}(0.025)|$, where $\Phi$ is the standard normal CDF. This ‘two-tailed Z-test’ has false alarm rate (‘type I error rate’, ‘statistical significance level’) approximately 0.05 if $n$ is large: if $Z$ were a standard normal, then obviously the false alarm rate would be exactly 0.05. But I'm not sure if that's what you're going for! $\endgroup$ – Squeamish Ossifrage Apr 14 '19 at 1:10
-2
$\begingroup$

Surprisingly, you've picked a toughie even though it is meant to be the simplest of the randomness tests. The easiest technique is the feely touchy approach in the ent test (explained here). You simply count them up and get a mean. The average of the means should be exactly 0.5 in the long run. See what you get and how you feel about it...

A longer technique is to say a bit generator is a coin tossing machine. You can then go to Wikipedia and look at Checking whether a coin is fair. You end up with a beta probability density function morphing into factorials, such as:-

pdf

for getting 7 heads and 3 tails( read ones and zeros). That's all a lot more complex, but there is a worked example that will guide you to a numerical probability.

Another version is the official NIST Frequency (Monobits) Test of NIST 800-22, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, Sections 2.1 & 3.1. They have both theory and a toy example.

It's not common to use $\sigma^2$ in randomness testing per se. Knowing that (for samples) $\sigma^2= 400 $ (one of my TRNGs) is more useful for entropy source health testing than general RNG verification. If you do get through to a p probability, it's typical to consider the hypothesis threshold as 0.01. Or NIST does any way.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This doesn't address the question about the variance of the number of one bits; doesn't address the context of the beta distribution in parameter estimation or Bayesian inference, nor connect it to hypothesis testing; and doesn't seem to connect use of $\sigma^2$ in ‘randomness testing’ to the question. $\endgroup$ – Squeamish Ossifrage Apr 14 '19 at 1:11
  • 1
    $\begingroup$ @SqueamishOssifrage But I have a nice graph... $\endgroup$ – Paul Uszak Apr 14 '19 at 1:15

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.