# Determine whether a random binary sequence was generated by human or natural process

Given a binary sequence, how can I calculate the quality of the randomness?

Following the discovery that Humans cannot consciously generate random numbers sequences, I came across an interesting reference:

• "A professor of probability would have half of his class write down a list of zeros and ones from a bunch of coin tosses and the other half write down a list of zeros and ones that they would try to make look random. The professor could sort out the papers with only a glance at each paper."

What method would be suitable to replicate the professor's act, i.e. judging which sequence is likely to be generated by a random process?

A method I have in mind is: for a given sequence-length $n$, establish the frequencies of each possible sub-sequence in the population of all possible sequences and than compare these with a particular sequence.

As this very quickly becomes impractical (the number of sub-sequences grows exponentially with $n$) the method may, instead, only measure a subset of all sub-sequences, e.g. all sequences of same digit.

How good would such a method work? What are some better methods?

• For starters, people tend to avoid too much repetition whereas coin tosses do not. Jun 13 '16 at 11:33
• My personal opinion : A human fails to produce random sequences because he cannot produce the correct frequency's of subsequences. But this does not mean, that the string a human constructs must necessarily have any structure. But what I do not quite understand : If we choose ANY string randomly, we have a good chance that it exhibits good randomness. I wonder a bit why a string produced by a human is not such a string randomly chosen. Difficult stuff ... Jun 13 '16 at 12:32
• A bit ironic. People with difficulties to concentrate, or people tending to forget, should have better chances to produce a "random" sequence. Jun 13 '16 at 12:37
• Another problem I have with such randomness-tests : The more tests we apply to test whether a sequence is random, the higher the probability that a truly random sequence fails one of the tests. I think, the best method is to run several tests, and if the sequence fails , lets say , $3$ of the tests, we have a good sign that it is probably not random. Jun 13 '16 at 12:41
• The negation of the "free will" might have beeing motivated by the lack of ability of a human to produce random sequences. But this lack does not make a human "predictable". Jun 13 '16 at 12:48

In a random sequence of $n$ tosses of a fair coin,

• the expected total number of runs is $\frac{n+1}{2}$
• the expected number of runs of length $L$ or more is $\frac{n+2-L}{2^L}$ when $L \le n$
• the expected number of runs of exactly length $L$ is $\frac{n+3-L}{2^{L+1}}$ when $L \lt n$
• the expected number of runs of exactly length $n$ is $\frac{1}{2^{n-1}}$

An approximation to this is to say that:

• the total number of runs will be about half the total number of tosses
• about half the runs will be of length $1$
• the number of runs of exactly length $L$ will be about half the number of length $L-1$
• the number of runs of at least length $L$ will be about equal to the number of length $L-1$

So for example with $100$ tosses,

• the expected total number of runs is $50.5$
• the expected number of runs of length $1$ is $25.5$
• the expected number of runs of length $2$ is $12.625$
• the expected number of runs of length $3$ is $6.25$
• the expected number of runs of length $4$ or more is $6.125$

and it would not be too difficult to judge this visually

Although, I do think it might be more fitting to ask somewhere else, I will try to answer this from a mathematical perspective.

As you noted, counting subsequences can get impractical, and doesn't, in a reasonable pratical environment, give ideal results, instead a varity of other techniques can be used. These are known as randomness tests.

Your example is one of many randomness tests. Other well-known tests are (I take the liberty to reframe your question in terms of sequence, $f : \mathbb{N} \to \mathbb{Z}_n$ for some $n$),

1. The Wald–Wolfowitz runs test. Extract uniformly distributed reals on the interval $(0, 1)$. Count ascending and descending runs. We know that the mean ought to be $\frac{2 N_{+} N_{-}}{N} + 1$. It follows that the variance will ideally be $\sigma^2 = \frac{(\mu - 1)(\mu - 2)}{N - 1}$ (with $N_+$ being number of ascending runs and $N_-$ being the number of descending runs, and $N = N_+ + N_-$).

2. The overlapping sum test. Generate $n$ reals on $(0, 1)$, add sequences of $m < n$ consecutive entries. The sums should then be normally distributed with characteristic mean and variance.

3. Matrix rank test. Through the random sequence, form a matrix over $\mathbb{Z}_n$, then determine the rank of the matrix, and examine the distribution.

To make it even more effective, one can add a number of classes of bijective combining functions, $g_m: \mathbb{Z}_n \to \mathbb{Z}_n$. One can then construct a new sequence by $f'(n) = g_n(f(n))$ and perform the randomness tests on $f'$. Examples of such function classes include,

1. Adding sequent elements, $g_n(x) = x + g_{n - 1}(f(n - 1))$, with $g_0(x) = x$.

2. Constant addition, $g_n(x) = x + c$ for some $c$.

3. Multiplying by some $p$ relatively prime with the modulo, $g_n(x) = px$.

and so on.

This is used as a tool for extracting patterns (e.g. weakening the function by identifying and abusing its patterns). Since a truely random sequence is pattern-less, this can be used for "measuring" randomness.