Is there a way to incrementally degrade the quality of a PRNG?

Question

I have an application that depends on a random number generator to perform. The application might be sensitive to the quality of the random numbers, but I don't know for sure. I'd like to test this, and if it is, what the degree of sensitivity is.

I've currently got a xorshift1024* PRNG plugged in. It's fast and I can directly inject a full 1024 bit state.

I need to be able to degrade it in a controlled fashion, ranging from it's high quality native mode to something quite bad. By quite bad, I mean something far far worse than a simple linear congruential generator. I'm not interested in slowly changing it's output distribution from uniform to say, normal. I just want to be able to make it (technically) crappier and crappier.

I have the sense that this might be a common requirement in other testing applications, so there might be a best practice methodology. At this point my only alternative is to switch off the generator entirely.

Is there a way to incrementally degrade the quality of my PRNG?

Answer 1

There are many possible ways to degrade its output, but here is one simple choice:

Think of your PRNG as outputting a sequence of bits. For a good PRNG, each bit would be uniformly distributed (equally likely to be 0 or 1), independent of the previous bits. We can build a degraded PRNG where each bit of the output is 1 with probability $p$ or 0 with probability $1-p$, independent of all of the previous bits. This gives us a parameter $p$ that can be varied from $1/2$ down to $0$: with $p=1/2$, there's no degradation, and smaller values of $p$ correspond to increasing amounts of degradation. Effectively, $p$ is a tuning knob that allows us to control the amount of degradation.

From this, you can derive a way to get other quantities. If you want a 32-bit integer, you generate each of its bits using this degraded PRNG. etc.

This model has some nice properties. For instance, if you generate a random $k$-bit value using your degraded PRNG, the resulting value will have $k h_2(p)$ bits of entropy. This varies from $k$ bits smoothly down to $0$ bits as $p$ varies from $p=1/2$ down to $p=0$. As a very crude approximation, the $k$-bit value will be approximately uniformly distributed on a set of size $2^{k h_2(p)}$; as $p$ gets smaller (as you introduce more degradation), the size of this set gets smaller smoothly.

Of course, we can't tell you whether this is the "right" degradation model for your particular application, as that will depend on your particular application. There are many other possible ways of degrading a PRNG's output, and since we haven't been given any specific criteria for selecting among them, I have semi-arbitrarily chosen one that is especially simple to implement and simple to think about.