4
$\begingroup$

I'm playing around with a novel kind of source of "random" data and Ent is currently giving me results like this:

Entropy = 7.977080 bits per byte.

Optimum compression would reduce the size of this 13239 byte file by 0 percent.

Chi square distribution for 13239 samples is 422.94, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 127.5968 (127.5 = random). Monte Carlo value for Pi is 3.180417044 (error 1.24 percent). Serial correlation coefficient is 0.009151 (totally uncorrelated = 0.0).

The Monte Carlo Pi value and Entropy results get even better as you increase the N value, but the Chi squared results get higher and higher and over trivially small N values you keep seeing the chi squared percent at less than 0.01.

What kind of non-randomness in the data does this suggest we're looking at?

Edit: It was recommended I specify that I understand that these high chi squared values suggest that the data is non-random. I'm trying to understand the data a bit better so I'm wondering what properties of the data would make it so good at all of these other entropy tests while failing at the chi square test in a specific way every time.

Edit 2: Running the program for a couple of days and I will report in with the Ent results and maybe put a hex dump of the data up when it's done. It would be a really big help if someone could just figure out exactly what makes this data "less than" random

$\endgroup$
1

1 Answer 1

3
$\begingroup$

I've seen this before in the true random number generators I've been working on. Look at the following test. I've ent'd two jpegs, one 10 times the size of the other. A jpg is highly compressed so can't be compressed much further, and incompressibility is one of the definitions of random. It has however, some non random bytes such as control structures and the golden bytes. So it's almost random, as is your data.


C:\scratch>ent lada.jpg Entropy = 7.956933 bits per byte.

Optimum compression would reduce the size of this 4685491 byte file by 0 percent.

Chi square distribution for 4685491 samples is 319354.77, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 132.0827 (127.5 = random). Monte Carlo value for Pi is 3.027673947 (error 3.63 percent). Serial correlation coefficient is 0.000597 (totally uncorrelated = 0.0).


C:\scratch>ent lena.jpg Entropy = 7.947390 bits per byte.

Optimum compression would reduce the size of this 408932 byte file by 0 percent.

Chi square distribution for 408932 samples is 33552.83, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 116.3320 (127.5 = random). Monte Carlo value for Pi is 3.357464603 (error 6.87 percent). Serial correlation coefficient is 0.020913 (totally uncorrelated = 0.0).


Compressibility stays similarish as a jpeg is a jpeg. pi improves for the larger lada file somewhat as you have more samples that are randomish. However, Chi increased exponentially as you have more and more control structures (read non random values) and as Chi uses a squared function in the calculation this error builds rapidly.

In summary, there are some values in your data set that occur at way too wrong a frequency. A histogram of the data over the full 0-255 range in a spreadsheet /gnuplot might help to show something obvious, but with chi of only 400 it might be subtle. You're hampering your analysis with the small sample size. ent is typically run against an 11 MB data set to get a target Chi of about 250.

One methodology I find useful is to draw a picture of the data. Load your data file into a pixel editor like GIMP as raw data and create a square image. Subtle patterns will show up if you sit and stare at it for a few minutes.

There are two questions you must consider. One, have you cocked up your randomness extraction algorithm and it's something you can eventually fix? Two more worryingly, is are you totally, utterly and willing to stake your puppy's life on it convinced that the original source of your numbers is really random?

Supplemental:

bit boundary waves

I don't see dips in your histogram. I see waves. The black line identifies at least to me, two halves of the histogram. Eight less strong ones (pink line), then 16 (blue line) and so on in powers of 2. That kinda corresponds to bit positions. It seems fairly regular. Does that mean anything to you? I think that your seeing a strobe effect between threads and your timer /counter with some jitter overlaid. I think that the strobe effect is probably totally uniform. I think the jitter is the source of your randomness, and I think that it's true randomness. Congratulations.

If you're interested in pursuing the random generator thing, ent is naff at measuring entropy. Take the file you generated for the histogram, and compress it as hard as you can. I suggest the program fp8, but zipping will be a good start. The resultant file will be a very good measure of how many truly random bytes you're generated.

See, printing out an image (in whatever form) is useful.

(Help Centre will be angry with us for having this discussion).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.