What Every Experimenter Must Know About Randomization
spawn-queue.acm.org
spawn-queue.acm.org
Sure I can understand why for a research trial you might want just want to be totally safe and use a source of true randomness, but for all practical purposes a decent PRNG used for sorting balls into buckets is totally indistinguishable from true randomness is it not?
I was half expecting this to have been written a few decades ago when really bad PRNGs were in common usage, but the article seems to be timestamped 2025.
Perhaps you could say otherwise for a CSPRNG.
So you must choose a PRNG wisely, depending on the intended purpose.
There are PRNGs good enough for any application, including those that use cryptographic mixing functions, but in many cases people prefer the fastest PRNGs.
The problems appear when the fastest PRNGs are used in applications for which they are not good enough, so the PRNG choice must be done carefully, whenever it is likely to matter.
With recent CPUs, the PRNG choice is much simpler than in the past. They can produce high quality random numbers by using AES at a rate only a few times lower than they can fill memory.
Because of this, the speed gap between the fastest PRNGs and good PRNGs has become much narrower than in the past. Therefore, if you choose a very good PRNG you do not lose much speed, so you can make this choice much more often.
Many kinds of non-cryptographic PRNGs have become obsolete, i.e. all those that are slower than the PRNGs using AES, SHA-2 or SHA-1, which use the dedicated hardware included in modern CPUs.
The non-cryptographic PRNGs that remain useful, due to superior speed, contain a linear congruential generator or a Galois field counter, which guarantee maximum period and allow sequence jumps and the ability to generate multiple independent random streams, together with some non-linear mixing function for the output, which improves the statistical properties.
Yes, there are theoretical issues with assuming PRNGs are truly random. However, there are also theoretical issues with assuming that Newton's law of universal gravitation is true.
I am confident is saying that more experiments have gone wrong due to not considering relativity, than have gone wrong due to the proper usage of a statistically sound (even if not cryptographically so) PRNG.
I also suspect that both classes of errors are dwarfed by improper usage or non sound PRNGs.
The first sentence is obviously true, but I'm going to need to see some evidence for "enormous bias" and "total nonsense". Let's leave aside lousy/little/badly-seeded PRNGs. Are there any non-cryptographic examples in which a well-designed PRNG with 256 bits of well-seeded random state produces results different enough from a TRNG to be visible to a user?
I imagine you could change the p-value test to randomly sample assignments generated via the exact same process that was used to generate the assignment used by the experiment, and as you run more and more iterations of this the calculated p-value should converge to the correct value, but then the question becomes is the p-value calculated this way the same as the p-value you'd get if you actually went ahead and used equiprobable assignment to begin with?
Ultimately, this all comes down to the fact that it's not hard to use true randomness for the whole thing, and true randomness produces statistically valid results, if you use true randomness for assignment then you can't screw up the p-value test, and so there's no reason at all to even consider how to safely use a PRNG here, all that does is open the door to messing up.
Of course a PRNG generates the same sequence every time with the same seed, but that's true of every RNG, even a TRNG where the "seed" is your current space and time coordinates. To get more results from the distribution you have to use more seeds. You can't just run an RNG once, get some value, and then declare the RNG is biased towards the value you got. That's not a useful definition of bias.
It doesn't matter how many universes it would take to generate all of them, there are some assignments that are less likely.
Perhaps it would help to think of the randomization in two stages. In the first, we select 2^256 members from the set of all possible permutations. (This happens when we select our CSPRNG algorithm.) In the second, we select a single member from the new set of 2^256. (This happens when we select our seed and run the CSPRNG.) I believe that measurable structure in either selection would imply a practical attack on the cryptographic algorithm used in the CSPRNG, which isn't known to exist for any common such algorithm.
Let's say that you have a uniform random number generator, which generates with equal probability anyone of N numbers. Then you want to choose with equal probability one of M choices.
If M divides N, then you can choose 1 of M by either multiplication with taking the integer part, or by division with taking the remainder.
When M does not divide N, for unbiased choices you must reject a part of the generated numbers, either rejecting them before the arithmetic operation (equivalent to diminishing N to a multiple of M), or rejecting them after the arithmetic operation (diminishing the maximum value of the integer part of product or of the division remainder, to match M).
This is enough for handling the case when M < N.
When M is greater than N, you can use a power of N that is greater than M (i.e. you use a tuple of numbers for making the choice), and you do the same as before.
However in this case you must trust your RNG that its output sequence is not auto-correlated.
If possible, using from the start a bigger N is preferable, but even when that is impossible, in most cases the unreachable parts of the space of random number tuples will not make any statistical difference.
To be more certain of this, you may want to repeat the experiment with several of the generators with the largest N available, taking care that they really have different structures, so that it can be expected that whichever is the inaccessible tuple space, it is not the same.
For example, the turkeys could be randomized by generating 256 bits of randomness per turkey, then sorting by that and taking the first half of the list. By a counting argument this must be biased (since the number of assignments isn't usually a power of two), but the bias is negligible.
The rejection methods may be faster, and thus beneficial in something like a Monte Carlo simulation that executes many times. Rejection methods are also often the simplest way to get distributions other than uniform. The additional complexity doesn't seem worthwhile to me otherwise though, more effort and risk of a coding mistake for no meaningful gain.
I assume that as long as p-values are concerned, the issue raised could very well be measured with simulations and permutations. I really doubt though that the distribution of p-values from pseudorandom assignments with gaps would not converge very fast to the "real" distribution you would get from all permuations due to some version of a law of large numbers. A lot of resampling/permutation techniques work by permuting a negligible fraction of all possible permutations, and the distribution of the statistics extracted converges pretty fast. As long as the way the gaps are formed are independent of the effects measured, it sounds implausible that the p-values one gets are problematic because of them.
Bakker and Wicherts (2011) would like to disagree! Apparently 15 % screw up the calculation of the p-value.
Suppose I'm doing something where I need N(0,1) random variates. I sample from U(0,1) being sure to use a TRNG, do my transformations, and everything's good, right? But my sample isn't U(0,1), I'm only able to get float64s (or float32s), and my transform isn't N(0,1) as there's going to be some value x above which P(z>x)=0. The theory behind what I'm trying to do assumes N(0,1) and so all my p-values are invalid.
Nobody cares about that because we know that our methods are robust to this kind of discretization. Similarly I think nobody (most people) should care (too much) about having "only" 256 bits of entropy in their PRNG because our methods appear to be robust to that.
We can create a balanced partitioning of the 300 turkeys with a 300 bit random number having an equal number of 1's and 0's.
Now suppose I randomly pick 300 bit number, still with equal 0's and 1's, but this time the first 20 bits are always 0's and the last 20 bits are always 1's. In this scenario, only the middle 260 bits (turkeys) are randomly assigned, and the remaining 40 are deterministic.
We can quibble over what constitutes an "enormous" bias, but the scenario above feels like an inadequate experiment design to me.
As it happens, log2(260 choose 130) ~= 256.
> Are there any non-cryptographic examples in which a well-designed PRNG with 256 bits of well-seeded random state produces results different enough from a TRNG to be visible to a user?
One example that comes to mind is shuffling a deck of playing cards. You need approximately 225 bits of entropy to ensure that every possible 52 card ordering can be represented. Suppose you wanted to simulate a game of blackjack with more than one deck or some other card game with more than 58 cards. 256 bits is not enough there.
For example. Suppose I have 2^128 unique playing cards. I randomly select 2^64 of them and place them in a deck. Someone proceeds to draw 2^8 cards from that deck, replacing and reshuffling between each draw. Does it really matter that those draws weren't technically independent with respect to the larger set? In a sense they are independent so long as you view what happened as a single instance of a procedure that has multiple phases as opposed to multiple independent instances. And in practice with a state space so much larger than the sample set the theoretical aspect simply doesn't matter one way or the other.
We can take this even farther. Don't replace and reshuffle after each card is drawn. Since we are only drawing 2^8 of 2^64 total cards this lack of independence won't actually matter in practice. You would need to replicate the experiment a truly absurd number of times in order to notice the issue.
Sure, at a point. I'm not disputing that. I'm asking for a concrete bound. When the state space is >= 2^64 (you're extremely unlikely to inadvertently stumble into a modern PRNG with a seed smaller than that) how large does the sample set need to be and how many experiment replications are required to reach that point?
Essentially what I'm asking is, how many independent sets of N numbers must I draw from a biased deck, where the bias takes the form of a uniformly random subset of the whole, before the bias is detectable to some threshold? I think that when N is "human" sized and the deck is 2^64 or larger that the number of required replications will be unrealistically large.
Yeah, but the question is: who cares?
Suppose you and I are both simulating card shuffling. We have the exact same setup, and use a 256-bit well-behaved PRNG for randomness. We both re-seed every game from a TRNG. The difference is that you use all 256 bits for your seed, while I use just 128 and zero-pad the rest. The set of all shuffles that can be generated by your method is obviously much larger than the set that can be generated by mine.
But again: who cares? What observable effect could there possibly be for anybody to take action if they know they're in a 128-bit world vs a 256-bit one?
The analogy obviously doesn't generalize downwards, I'd be singing a different tune if it was, say, 32 bits instead of 128.
If you can't generate all possible assignments, you care about second and third order properties etc. of the sequence.
Huh? If you can chew through however many gigabytes of the supposed CSPRNG’s output, do some statistics, and with a non-negligible probability tell if the bytes in fact came from the CSPRNG in question or an actual iid random source, then you’ve got a distinguisher and the CSPRNG is broken.
No CSPRNG is absolutely perfect, no CSPRNG has ever absolutely passed every statistical test thrown at it.
In MCMC, it stresses very different statistical tests than the typical CSPRNG tests.
Every PRNG is absolutely broken if you want to be absolute about it. MCMC and crypto applications push on different aspects where statistical issues will cause application level failures.
See e.g. this paper https://www.cs.hmc.edu/tr/hmc-cs-2014-0905.pdf
(it's not the end all be all, but it's a good survey of why this stuff matters and why it's different)
As far as I know (admittedly not a high standard), there is no published statistical test that you could run on, for example, a single AES-256-CTR bitstream set up with a random key and IV, running on a single computer, that would be able to tell you with a meaningful likelihood ratio that you were looking at a pseudorandom rather than truly random input before the computer in question broke down. (I’m assuming related-key attacks are out of scope if we’re talking about an RNG for simulation purposes.)
One way to imagine what symmetric cryptography does is a cellular automaton that is completely shuffled every iteration. In the case of Keccak/SHA3, that is almost exactly what happens too.
What is a perfect CSPRNG?
For all of them there are theoretical methods that can distinguish a sequence generated by them from a random sequence, but all such methods require an impossible amount of work.
For instance, a known distinguisher for the Keccak function that is used inside SHA-3 requires an amount of work over 2^1500 (which was notable because it was an improvement over a naive method that would have required an amount of work of 2^1600).
This is a so ridiculously large number in comparison with the size and age of the known Universe, that it is really certain that nobody will ever run such a test and find a positive result.
There are a lot of other such CPRNGs for which the best known distinguishers require a work of over 2^100, or 2^200, or even 2^500, and for those it is also pretty certain that no practical tests will find statistical defects.
There are a lot of CSPRNGs that could not be distinguished from TRNGs even by using hypothetical quantum computers.
Even many of the pretty bad cryptographic PRNGs, which today are considered broken according to their original definitions, can be made impossible to distinguish from TRNGs by just increasing the number of iterations in their mixing functions. This is not done because later more efficient mixing functions have been designed, which achieve better mixing with less work.
A good MCMC simulation might test that! E.g. say, training a large diffusion model. It takes way more computing power than the average time for a single computer to fail.
Also, the standards of those tests vs. does it bias the statistical model fitted with MCMC are different.
However at some point, 100x faster performance w/o an exploitable attack vector is also relevant! (though sometimes people find ways).
CSPRNGs are mostly worried about very specific attack vectors, and sure, they're like to be completely unpredictable. But other applications care more about other attack vectors like lack of k-dimensional equiprobability, and that hurts them far more.
The idea that CSPRNGs are the end all and be all of rngs holds CS back.
For emphasis, an empirically measurable deviation from k-equidistribution would be a cryptographic weakness (since it means that knowing some members of the k-tuple helps you guess the others). So that would be a strong claim requiring specific support.
Contrary to GP’s statement, I can’t find any claims of an actual test anywhere in the PCG materials, just “k-dimensional equdistribution: no” which I’m guessing means what I’ve just said. This is, at worst, correct but a bit terse and very slightly misleading on O’Neill’s part; how GP could derive any practical consequences from it, however, I haven’t been able to understand.
Computational feasibility is what matters. That's roughly what I meant by "measurable", though it's better to say it explicitly as you did. I'm also unaware of any computationally feasible way to distinguish a CSPRNG seeded once with true randomness from a stream of all true randomness, and I think that if one existed then the PRNG would no longer be considered CS.
Is it enough to truly matter? Maybe not, but does it also matter if 80 bit SHA1 only has 61 bits?
If you think there's any practical difference between a stream of true randomness and a modern CSPRNG seeded once with 256 bits of true randomness, then you should be able to provide a numerical simulation that detects it. If you (and, again, the world's leading cryptographers) are unable to adversarially create such a situation, then why are you worried that it will happen by accident?
SHA-1 is practically broken, in the sense that a practically relevant chosen-prefix attack can be performed for <$100k. This has no analogy with anything we're discussing here, so I'm not sure why you mentioned it.
You wrote:
> There are concepts like "k-dimensional equidistribution" etc. etc... where in some ways the requirements of a PRNG are far, far, higher than a cryptographically sound PRNG
I believe this claim is unequivocally false. A non-CS PRNG may be better because it's faster or otherwise easier to implement, but it's not better because it's less predictable. You've provided no reference for this claim except that PCG comparison table that I believe you've misunderstood per mananaysiempre's comments. It would be nice if you could either post something to support your claim or correct it.
However I have never seen a place where the author says something about finding a statistical defect in ChaCha. She only correctly says that ChaCha is significantly slower than PRNGs like those of the PCG kind (and that it also shares the same property that any PRNG with a fixed state size has, of limited high-dimensional equidistribution; this is also true for any concrete instantiation of the PRNGs recommended by the author; the only difference is that with PRNGs having a simple definition you can make the same structure with a bigger state, as big as you want, but once you have chosen a size, you have again a limit; the PCG PRNGs recommended there, when having greater sizes than cryptographic PRNGs, they become slower than those cryptographic PRNGs, due to slow large integer multiplications).
In the past, I have seen some claims of statistical tests distinguishing cryptographic PRNGs that were false, due to incorrect methodology. E.g. I have seen a ridiculous paper claiming that an AI method is able to recognize that an AES PRNG is non-random. However, reading the paper has shown that they did not find anything that could distinguish a number sequence produced by AES from a true random sequence. Instead, they could distinguish the AES sequence from numbers read from /dev/random on an unspecified computer, using an unspecified operating system. Therefore, if there were statistical biases, those were likely in whichever was their /dev/random implementation (as many such implementations are bad, and even a good implementation may appear to have statistical abnormalities, depending on the activity done on the computer), not in the AES sequence.
Also worth noting that the situations where this matters are usually where your effect size is fairly small compared to the unexplained variation, so a few percent error in your p-value can make a difference.
Your numbers don't make sense. Your number of assignments is way fewer than 2^256, so the problem the author is (mistakenly) concerned about doesn't arise--no sane method would result in any measurable deviation from equiprobable, certainly not "twice as likely".
With a larger number of turkeys and thus assignments, the author is correct that some assignments must be impossible by a counting argument. They are incorrect that it matters--as long as the process of winnowing our set to 2^256 candidates isn't measurably biased (i.e., correlated with turkey weight ex television effects), it changes nothing. There is no difference between discarding a possible assignment because the CSPRNG algorithm choice excludes it (as we do for all but 2^256) and discarding it because the seed excludes it (as we do for all but one), as long as both processes are unbiased.
Any high-gain electronic amplifier whose input is connected to a resistor, or for a higher signal level, to a diode, will produce copious amounts of random noise at its output. If the output is converted with a comparator to digital, you have a good source of random bits.
Older people can remember the random audio or video noise of ancient radio receivers or TV sets, when they were tuned outside a correct channel.
In the past, there were easily available analog TV tuners for PCs, which could be used as noise sources. Nowadays, it is still possible to use the microphone input of a PC and connect to it an external analog noise source with a negligible cost, made on a little PCB with a small amplifier IC, e.g. an operational amplifier or an audio amplifier. The microphone input of PCs provides a weak 5 V supply, which would be enough to power a noise source.
The only problem that exists with any analog noise source is that the imperfections of analog-to-digital conversion, e.g. the fluctuations of comparator thresholds, due to temperature or age, can cause a bias in the random bits, so they do not have a truly uniform distribution. This problem also exists with radioactive sources.
Thus the bits must be processed to remove any bias. There are more sophisticated methods, but even the brute force method of using a one-way hash function, e.g. one of the SHA-3 or SHA-2 variants, to hash the bits and produce a uniform random number, is good enough.
Most modern CPUs, since Intel Ivy Lake, have instructions for providing true random numbers. However those are less useful outside their main intended application, of providing temporary session keys for TLS or other network protocols.
Some CPUs, especially from AMD, had bugs in their RNG, so they provided bad values. Even where the TRNG is good, the output passes through AES-128. Its state is small so you may encounter the problems mentioned in the parent article, of unreachable parts of the solution space that you are investigating in some Monte Carlo simulation.
It is preferable to be able to choose yourself the bias-removing method, to be able to use a hashing method with a much greater state.
These are so fun. One time I was able to get a device to replay an entire WPA2 handshake by triggering a signal generator with its reset line and feeding the output to its rng ADC. Good parlour trick that one.
But you have the same issue with a PRNG, just boiled down to the seed value. Disprove that I didn't chose seed 42 by random, you can't.
The only way to protect against this is registering the study with a third party beforehand and letting them dice out the numbers as soon as the hashed data is there.
By registering your plan beforehand, someone can check if you altered it to cherrypick or p-hack your results after the fact. By letting them chose the random numbers you protect against you rerolling the numbers when inconvenient. By letting them only see the hashed data you protect against them rerolling/altering based on their interest and against you swapping out data point indicies after the fact, since they can rehash the actual values and check if it matches their selection.
For many experimental designs this could be overkill, but registering studies is becoming more common in medical studies. I doubt they go as far as I described with the random numbers.
Not so. Assuming I don't need a whole bunch of runs in the final paper I can use the zero seed for the published work. I don't think anyone will contest that.
If you need to use a rejection method to achieve a uniform distribution you can do so via plaintext=( ( serial_number << 32 ) | sample_counter ).
By adhering to such a scheme it becomes extremely difficult for anyone to reasonably accuse you of underhanded tricks via RNG manipulation.
> “Of course not!” thundered the surgeon. “That would have doomed half of the patients to death!”
> Stunned silence filled the lecture hall, and the student softly asked,
> “Which half?”
damn that was good
yes, exactly that?
it's a parable about null hypothesis - without data to compare against we have no idea whether new procedure is actually any good (as in, better)
in reality conversation would (should) soon turn towards observations by other surgeons, general death rate of the disease or even some basic theory - but simply saying "they would've died, trust me bro" is not it
also note that surgeon is overreacting. "set aside" does not automatically mean "do nothing" - control group should probably be given previous accepted version of treatment, as that's what the new idea is trying to replace
> Significance tests are meaningful and valid if AND ONLY IF assignment was properly randomized.
OK I agree with the “if” but not the “only if” part of this implication. My intuition is that significance tests are still meaningful if a non-random method of assignment is chosen, but the bias introduced by the method is not in any way correlated with the observations under study.
This leads to the whole thing the author gets into about PRNGs not being valid for assignment. But a much simpler and more deterministic method of sampling is stratified sampling, which is used all over the place for various types of statistical experiments. The random entropy of a stratified sample is nowhere near enough to be fully random, yet I haven’t seen anyone claim that all experiments done using stratified sampling have invalid or meaningless p-values.
Basically stratified sampling works as follows. Say you want to study the effects of age and gender on income. One way is to just study everyone, record their age, gender and income and do your study. But that gets pretty unweildy and you may not be able to get accurate data over the whole population. What you can do instead is get a list of people, sort them by age and gender and pick a size that’s convenient. So say you have capacity to analyse a sample 1/20th the size of the total. Cool. Then you just take every 20th person on your list and that’s your sample. By the magic of stratified sampling, because your list is sorted by age and gender, the sample will more or less have the same proportions as the total population with respect to age and gender.
Not random, but used all over the place for statistical studies.
What I personally would like to see is some kind of quantization of how the biases that the author talks about (such as insufficient seed volume of a PRNG) affects computed p-values. Specifically, why there must no "cancellation of errors" happen? So far, IIUC, the author only shows theoretical possibility of errors, but what's more interesting is a real effect. When it all boils down to a p-value being less than a certain threshold (choosing which is another pita), it might not matter whether a true p-value is within, say, 2^-16 from the computed.
Maybe that's the problem? With 256 bits we will only get the "typical" assignments and not the edge cases which are the ones that are important for randomisation tests?
^[1]: There are other interpretations, of course. And those other interpretations are equally explanatory. But they do not claim to be explanations of what is actually happening to unobserved quantum particles. There is also Bohmian mechanics, but I don't know how many people take it seriously.
Most prefer to believe in randomness.
What's bullshit about it? This is how TRNGs in security enclaves work. They collect entropy from the environment, and use that to continuously reseed a PRNG, which generates bits.
If you're talking "true" in the philosophical sense, that doesn't exist -- the whole concept of randomness relies on an oracle.
Because of this, the best non-cryptographic PRNGs are made from either a LCG or a GFC that ensures the properties mentioned above, together with a non-linear mixing function that scrambles the output, for much better statistical properties than a linear generator would have alone.
The good cryptographic RNGs have the same kind of structure, but where a one-way hash function or a block cipher function is used to scramble the output of a counter. The counter ensures in a simpler way the same properties as a LCG or GFC. A simple counter can be used here because the output mixing function is much more complex.
It's a lot easier to use diodes (light emitting and otherwise).