It’s complex to measure complexity!

I have started to read The New Turing Omnibus - a book that offers 66 concise, brilliantly written articles on the major points of interest in computer science theory, technology and applications.

From time to time, I will write a blog post presenting a chapter of this book.

omnibus

Today, I am glad to present an interactive version of Chapter 6 about the generation of random numbers.

Algorithms for generating random numbers

Generating a sequence from seed an next

generateSequence = (n, seed, next)  => {
  let seq = new Array(n);
  seq[0] = seed;
  for(let i=1; i< n; i++) {
    seq[i] = next(seq[i-1])
  }
  return seq
}

Linear Congruency

linearCong = (k, c, m) => (prev) => (k*prev + c) % m
linearCong(19, 51, 101)(231)
linearCongRandomSeq = ({size, seed, k,c,m}) => generateSequence(size, seed, linearCong(k,c,m))
linearCongRandomSeq({size: 10, seed: 22, k: 19, c: 3, m:54})

Logistic Formula

regression = (r) => (prev) => r*prev*(1-prev)
generateSequence(5, 0.5, regression(3.57))
logisiticRandomSeq = ({size, seed, r, max}) => generateSequence(size, seed, regression(r)).map(x => Math.round(max*x))
logisiticRandomSeq({size: 10, seed: 0.5, r: 3.57, max: 1e9})

Javascript Math.random

rand = (max) => Math.round(max*Math.random())
mathRandomSeq = ({size, max}) => generateSequence(size, rand(max), () => rand(max))
mathRandomSeq({size: 10, max: 1e9})

How to measure complexity?

Period

period = (seq) => (new Set(seq)).size
period(linearCongRandomSeq({size: 100, seed: 22, k: 19, c: 3, m:54}))
period(mathRandomSeq({size: 1e4, max: 1e9}))
period(logisiticRandomSeq({size: 1e4, seed: 0.5, r: 3.57, max: 1e9}))

Distribution of the values mod n

The problem

The sequence of integer numbers never repeats and distributes uniformly

Kolmogorov Complexity

Paradox

Most of the sequences are random but no sequence can be proved to be random

Logistic Formula

Measure randomness

How do we measure the randomness of a sequence of numbers? By looking at the repartition of the values mod m?

measureRandomness = (seq) => R.map(x => 100*x/seq.length,
                                   R.countBy(x => x % 10)(seq))
visualizeRandomness = (seq, name) => ({
  dataTable: [["n", "%"], ...Object.entries(measureRandomness(seq) )],
  options: {
    showRowNumber: true,
    width: '100%', 
    height: '100%',
    title: `The repartition of the elements of a sequence created by ${name}`,
    vAxis: {
      title: 'percentage',
      viewWindow : {
        min: 0,
      }
    },
    hAxis: {
      title: 'bin'
    }
  }, 
  chartType: "ColumnChart"
})

visualizeRandomness(linearCongRandomSeq({size: 10, seed: 22, k: 19, c: 3, m:54}), 'Linear Congruency')

visualizeRandomness(logisiticRandomSeq({size: 10, seed: 0.5, r: 3.57, max: 1e9}), 'Logistic Regression') 

visualizeRandomness(mathRandomSeq({size: 1e6, max: 1e9}), 'Math.random()')