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 = 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.