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.

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}))
``````

## The problem

The sequence of integer numbers never repeats and distributes uniformly

# Kolmogorov Complexity

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

# 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()')
``````