7
$\begingroup$

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?

$\endgroup$
6
  • 3
    $\begingroup$ For starters, people tend to avoid too much repetition whereas coin tosses do not. $\endgroup$
    – Servaes
    Commented Jun 13, 2016 at 11:33
  • $\begingroup$ 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 ... $\endgroup$
    – Peter
    Commented Jun 13, 2016 at 12:32
  • $\begingroup$ A bit ironic. People with difficulties to concentrate, or people tending to forget, should have better chances to produce a "random" sequence. $\endgroup$
    – Peter
    Commented Jun 13, 2016 at 12:37
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Commented Jun 13, 2016 at 12:41
  • $\begingroup$ 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". $\endgroup$
    – Peter
    Commented Jun 13, 2016 at 12:48

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .