# How can I determine the statistical randomness of a binary string?

How can I determine the statistical randomness of a binary string?

Ergo, how can I code my own test, and return a single value that corresponds to the statistical randomness, a value between 0 and 1.0 (0 being not random, 1.0 being random)?

The test would need to work on binary strings of any size.

When you do it with pen and paper, you might explore strings like this:
0 (arbitrary randomness, the only other choice is 1)
00 (not random, its a repeat and matches the size)
01 (better, two different values)
010 (less random, palindrome)
011 (less random, more 1's, still acceptable)
0101 (less random, pattern)
0100 (better, less ones, but any other distribution causes patterns)

Case examples:

Size: 1, Possibilities: 2
0: 1.0 (random)
1: 1.0 (random)

Size: 2, P:4
00: ?
01: 1.0 (random)
10: 1.0 (random)
11: ?

S:3, P:8
000: ? non-random
001: 1.0 (random)
010: ? less random
011: 1.0 (random)
100: 1.0 (random)
101: ? less random
110 1.0 (random)
111: ? non-random

And so on.

I feel that this may play a lot into breaking the string into all possible substrings and comparing frequencies, but it seems like this sort of groundwork should already have been done in the early days of computer science.

-
any single binary string can be viewed as being random! You need to have a sample space in which to compare it... –  Mitch Wheat Jun 22 '10 at 23:43
what are you actually tring to do? –  Mitch Wheat Jun 22 '10 at 23:45
Just that: read in an arbitrary binary string, and note its statistical randomness. For instance, 0101010101010101 has a balanced number of 1's and 0's, but is hardly random. One could say that: [00000000 has a randomness of 0] [01010101 has a randomness of 0.01] [00000101 has a randomness of 0.05] [01001011 has a randomness of 1.0] –  Tim Jun 22 '10 at 23:50
You're asking a harder question than you anticipate. Did you have any particular randomness tests in mind to implement? The Wikipedia page for Statistical Randomness lists some of the simpler tests. You might have to go to journal articles for more interesting ones. What are you using this test for? That might influence which tests are relevant. What do you actually want to measure? Maybe: the probability that the observed string was generated from a truly random generator? –  Karmastan Jun 22 '10 at 23:51
Hah! Your Case exmaples is really good comedy. In a random byte string, any of them will appear just as often as the other!! –  u0b34a0f6ae Jun 23 '10 at 11:43

This will give you an entropy count from 0 to 1.0:

You might want to try looking into the Shannon Entropy, which is a measure of entropy as applied to data and information. In fact, it is actually almost a direct analogue of Physical formula for entropy as defined by the most accepted interpretations of Thermodynamics.

More specifically, in your case, with a binary string, you can see the Binary Entropy Function, which is a special case involving randomness in binary bits of data.

This is calculated by

``````H(p) = -p*log(p) - (1-p)*log(1-p)
``````

(logarithms in base 2; assume `0*log(0)` is 0)

Where `p` is your percentage of 1's (or of 0's; the graph is symmetrical, so your answer is the same either way)

Here is what the function yields:

As you can see, if `p` is 0.5 (same amount of 1's as 0's), your entropy is at the maximum (1.0). If `p` is 0 or 1.0, the entropy is 0.

This appears to be just what you want, right?

The only exception is your Size 1 cases, which could just be put as an exception. However, 100% 0's and 100% 1's don't seem too entropic to me. But implement them as you'd like.

Also, this does not take into account any "ordering" of the bits. Only the sum total of them. So, repetition/palindromes won't get any boost. You might want to add an extra heuristic for this.

Here are your other case examples:

```00:   -0*log(0) - (1-0)*log(1-0)               = 0.0
01:   -0.5*log(0.5) - (1-0.5)*log(1-0.5)       = 1.0
010:  -(1/3)*log(1/3) - (2/3)*log(2/3)         = 0.92
0100: -0.25*log(0.25) - (1-0.25)*log(1-0.25)   = 0.81
```
-

You seem to be asking for a way to find the Kolmogorov complexity of a binary string. Sadly, this is incomputable. The size of your string after running it through a compression algorithm will give you an idea of how random it is, in that more random strings are less compressible.

-
Indeed. Define "degree of randomness" as "ratio of compressed file to uncompressed file". That's as close as you're likely to get. –  Norman Ramsey Jun 23 '10 at 2:03
This seems to (almost) exactly be what you are looking for. Pick a compression algorithm, but unfortunately none is perfect. I'm not sure I know any compression algorithms that compress palindromes, but almost every one I know can compress repetitive sequences. –  Justin L. Jun 23 '10 at 6:00

Some time ago, I developed the a simple heuristic that worked for my purposes.

You simply calculate the "even-ness" of 0s and 1s not only in the string itself, but also on derivatives of the string. For example, the first derivative of 01010101 is 11111111, because every bit changes, and the second derivative is 00000000, because no bit in the first derivative changes. Then you simply have to weigh these "even-nesses" according to your taste.

Here is an example:

``````#include <string>
#include <algorithm>

float variance(const std::string& x)
{
int zeroes = std::count(x.begin(), x.end(), '0');
float total = x.length();
float deviation = zeroes / total - 0.5f;
return deviation * deviation;
}

void derive(std::string& x)
{
char last = *x.rbegin();
for (std::string::iterator it = x.begin(); it != x.end(); ++it)
{
char current = *it;
*it = '0' + (current != last);
last = current;
}
}

float randomness(std::string x)
{
float sum = variance(x);
float weight = 1.0f;
for (int i = 1; i < 5; ++i)
{
derive(x);
weight *= 2.0f;
sum += variance(x) * weight;
}
return 1.0f / sum;
}

int main()
{
std::cout << randomness("00000000") << std::endl;
std::cout << randomness("01010101") << std::endl;
std::cout << randomness("00000101") << std::endl;
}
``````

Your example inputs yield a "randomness" of 0.129032, 0.133333 and 3.2 respectively.

On a side note, you can get cool fractal graphics by deriving strings ;)

``````int main()
{
std::string x = "0000000000000001";
for (int i = 0; i < 16; ++i)
{
std::cout << x << std::endl;
derive(x);
}
}

0000000000000001
1000000000000001
0100000000000001
1110000000000001
0001000000000001
1001100000000001
0101010000000001
1111111000000001
0000000100000001
1000000110000001
0100000101000001
1110000111100001
0001000100010001
1001100110011001
0101010101010101
1111111111111111
``````
-
+1 for derivatives of strings, and the cool fractalness. –  Justin L. Jun 23 '10 at 1:19
I don't think this is a theoretically sound handle on Komologorov complexity, but you may be interested to note that this is in fact the rule 60 elementary cellular automaton: mathworld.wolfram.com/Rule60.html –  Nick Johnson Jun 23 '10 at 9:52
@Nick: That's pretty cool, didn't know about that :) –  FredOverflow Jun 23 '10 at 10:13

seems like you have a bunch of heuristics for randomness. Simply make something that runs through those heuristics and scores the bitstream on the average of all the heuristics?

-

You might try a compression algorithm on the string. The more repetition (less randomness) there is, the more the string can be compressed.

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://stackoverflow.com/questions/3097949/how-can-i-determine-the-statistical-randomness-of-a-binary-string", "fetch_time": 1416770044000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2014-49/segments/1416400379636.59/warc/CC-MAIN-20141119123259-00043-ip-10-235-23-156.ec2.internal.warc.gz", "warc_record_offset": 306100284, "warc_record_length": 20868, "token_count": 2134, "char_count": 7441, "score": 3.59375, "int_score": 4, "crawl": "CC-MAIN-2014-49", "snapshot_type": "latest", "language": "en", "language_score": 0.8923259377479553, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00025-of-00064.parquet"}