3 ms·

I don't think testing for randomness makes sense. Randomness is something we assume. There's always a non-zero probability that randomness will appear non-rando

by runeks 10y ago

I don't think testing for randomness makes sense. Randomness is something we assume. There's always a non-zero probability that randomness will appear non-random. In fact, this whole comment is a random string of characters. I just got really lucky, and there's essentially no way to disprove that. Throwing a dice a trillion times and getting all 6's is not an invalid outcome, just very improbable. Randomness is about unpredictability. How can you assert that something is or is not predictable? It's always possible you just haven't observed it for long enough. An initial, randomly-appearing sequence may turn out to start repeating itself after some point in time; and an initial, self-repeating sequence can always be statistically cancelled out by later data. Randomness is not something we can have; it's something we don't have (the ability to predict).

flukus 10y ago
Is there an alternative? Can you mathematically prove randomness? (real question I'm not a mathemagician) If you can how do you verify that there is not an implementation bug in the code? I think it might be a case of perfect being the enemy of good, the best approach is to minimize the false negatives.
- rocqua 10y ago
  You can disprove randomness (by prediction) but you can't prove randomness. You can prove that certain results are as one would expect for a random source, but that is neither guaranteed to be passed by uniform randomness, nor does passing guarantee true randomness. On a more philosophical level, as you get better measurements, entropy of a random source will always decrease. Time-stamp seeding, for example, can be weakened by timing. What can be done, on the theoretical level for PRNGs is to see how easy it is to predict the next iteration from the current iteration. An easy bound here is simply the period of the PRNG.
misja111 10y ago
On the contrary, randomness is everywhere. Newtonian physics are nothing more than the statistical properties of quantum randomness with a large enough sample size. To test the randomness of the RNG you could make the sample size so large that the chance of a false positive would be smaller than the chance of some memory bit flipping as a result of the Heisenberg uncertainty principle.
Normal_gaussian 10y ago
If you are using a hardware RNG there is the potential that there is some hardware fault causing a static readout or other such catastrophic failure. It depends what happens when the test fails as to whether it is reasonable or not.

by runeks 10y ago

flukus 10y ago

Is there an alternative? Can you mathematically prove randomness? (real question I'm not a mathemagician) If you can how do you verify that there is not an implementation bug in the code? I think it might be a case of perfect being the enemy of good, the best approach is to minimize the false negatives.

rocqua 10y ago
You can disprove randomness (by prediction) but you can't prove randomness. You can prove that certain results are as one would expect for a random source, but that is neither guaranteed to be passed by uniform randomness, nor does passing guarantee true randomness. On a more philosophical level, as you get better measurements, entropy of a random source will always decrease. Time-stamp seeding, for example, can be weakened by timing. What can be done, on the theoretical level for PRNGs is to see how easy it is to predict the next iteration from the current iteration. An easy bound here is simply the period of the PRNG.

misja111 10y ago

On the contrary, randomness is everywhere. Newtonian physics are nothing more than the statistical properties of quantum randomness with a large enough sample size. To test the randomness of the RNG you could make the sample size so large that the chance of a false positive would be smaller than the chance of some memory bit flipping as a result of the Heisenberg uncertainty principle.

Normal_gaussian 10y ago

If you are using a hardware RNG there is the potential that there is some hardware fault causing a static readout or other such catastrophic failure. It depends what happens when the test fails as to whether it is reasonable or not.