# It's complex to measure complexity

Have you ever thought how we can generate random numbers mathematically?

In this article, we are going to present simple algorithms for generating pseudo-random sequences and we will discuss about how we can measure the complexity (i.e. the randomness) of a sequence of numbers.

We will see that indeed, it is complex to measure complexity!

We will illustrate the mathematical idea of randomness by coding the algorithms and the formulas in `javascript`

.

Even if you are not 100% familiar with javascript, you should be able to enjoy this article.

As usual, all the code snippets of this article are interactive - powered by the KLIPSE plugin. Feel free to modify the code in order to get a better feeling of the concepts.

# Algorithms for generating random numbers

## Generating a sequence from seed an next

The simplest way to generate a pseudo-random sequence is to start from a seed number and to provide a `next`

function that receives a number and return the next number of the sequence.

Here is a function that generate a pseudo-random sequence of length `n`

:

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

Linear congruency formula is parametrized by:

`k`

: the coefficent`c`

: the offset`m`

: the period

Here is the code for linear congruency:

(Don’t be afraid by the fact that `linearCong`

is a function that returns a function!)

```
linearCong = (k, c, m) => (prev) => (k*prev + c) % m
```

Let’s see `linearCong`

in action:

```
linearCongExample = linearCong(19, 51, 101)
linearCongExample(231)
```

Now, we can generate a pseudo-random sequence using the linear congruency formula as our `next`

function:

(Don’t be afraid by the fact that we are using ES6 destructuring syntax!)

```
linearCongRandomSeq = ({size, seed, k, c, m}) => generateSequence(size, seed, linearCong(k,c,m))
```

Let’s see `linearCongRandomSeq`

in action:

```
linearCongRandomSeq({size: 10, seed: 22, k: 19, c: 3, m:54})
```

## Logistic Regression Formula

Logistic Regression is another possible formula for generating pseudo-random sequences:

Here is the formula (parametrized with `r`

):

```
regression = (r) => (prev) => r*prev*(1-prev)
```

As before, let’s generate a sequence using the logistic regression formula (with `r`

=3.57):

```
generateSequence(5, 0.5, regression(3.57))
```

Feel free to play with the value of `r`

The problem with logistic regression is that the values are between `0`

and `1`

.

But its’s very simple to scale the values of the sequence and transform the values to integers, by mapping each value of the sequence:

```
logisiticRandomSeq = ({size, seed, r, max}) => generateSequence(size, seed, regression(r)).map(x => Math.round(max*x))
```

Let’s see it in action:

```
logisiticRandomSeq({size: 10, seed: 0.5, r: 3.57, max: 1e9})
```

Feel free to play with all the parameters - but be careful with `size`

. If you take a value that is too bug, your browser might crash…

## Javascript random function

In `javascript`

, the language provides a `Math.random`

function for generating random numbers between `0`

and `1`

.

Here is how we can plug `Math.random`

into our random sequence generation mechanism:

```
rand = (max) => Math.round(max*Math.random())
mathRandomSeq = ({size, max}) => generateSequence(size, rand(max), () => rand(max))
```

Let’s see `mathRandomSeq`

in action:

```
mathRandomSeq({size: 10, max: 1e9})
```

Now, that we have seen how to generate pseudo-random sequences, let’s see how we can measure the complexity of the sequence. By complexity, we mean the “level of randomness” of the sequence.

# How to measure complexity?

## Period

One simple way to assess the complexity of a sequence, is to count the number of unique elements - the period - of the sequence. If the elemets repeat themselves, the period will be lower than the size of the sequence.

In `javascript`

, we have the mathematical `sets`

available in the language.

In a `set`

duplicate elements are removed.

Therefore, in order to count the number of unique elements, we can convert our sequence into a `set`

and count the number of elements in the resulting set.

```
period = (seq) => (new Set(seq)).size
```

### Period of Linear Congruency sequences

Let’s measure the period of psedo-random sequences generated using linear congruency:

```
period(linearCongRandomSeq({size: 100, seed: 22, k: 19, c: 3, m:54}))
```

Obviously, the period can never be greater than the value of `m`

!

Exercise: Can you find a good combination of `k`

, `c`

and `m`

? By good combination, we mean a combination that generate a sequence whose period is very close to `m`

.

### Period of Logistic Regression sequences

Logistic regression sequences give better results, when we chose an appropriate value for `r`

:

```
period(logisiticRandomSeq({size: 1e2, seed: 0.5, r: 3.57, max: 1e4}))
```

### Period of javascript random sequences

Sequences generated with the javascript `Math.random`

function seem to perfom even better:

```
period(mathRandomSeq({size: 1e2, max: 1e4}))
```

A more precise way of measuring complexity is by checking how much the values of the sequence share common properties. For instance, we can visualize the distribution of the values modulo `n`

. If the sequence is perfectly random, then the values modulo `n`

should be distributed uniformly.

## Distribution of the values modulo 10

Let’s write a function that calculates the distribution of a sequence modulo `10`

.

More precisely, the function receives an array of arbitrary length and return an array of length 10 where the `i`

th element of the array contains the frequency (in percentage) of the values `x`

of the sequence such that `x mod 10 = i`

.

Here is the code using `map`

and `countBy`

provided by Ramda.js:

```
measureRandomness = (seq) => R.map(x => 100*x/seq.length,
R.countBy(x => x % 10)(seq))
```

Let’s see it in action by measuring the randomness of the sequence of integers from 0 to 999:

```
measureRandomness(R.range(0, 1000))
```

Now, let’s visualize the randomness in a Column chart powered by google charts:

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

Let’s visualize the randomness of our linear congruency sequence:

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

Feel free to play with the parameters of `linearCongRandomSeq`

and see how the chart updates auto-magically.

Let’s visualize the randomness of our logistic regression sequence:

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

Feel free to play with the parameters of `logisiticRandomSeq`

and see how the chart updates auto-magically.

Let’s visualize the randomness of the javacript random sequence:

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

Feel free to play with the parameters of `mathRandomSeq`

and see how the chart updates auto-magically.