Search code examples
javascriptrandomfisher-yates-shuffle

Math.random() unsatisfactory

Let be a list containing the 26 letters of the alphabet from A to Z. We mix the list with the Fisher-Yates algorithm (see https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). We are interested in the first letter of the table :

  • In theory, each letter has the same probability of being in the first position: 1/26 ~ 3.85%.
  • In practice, this is not the case! As the distribution below shows, the probability of finding B is 5.14% against 2.89% for Z. B has 1.78x more chances than Z to be in first position (almost 2x more which is huge).

distribution

Here is the code I used:

"use strict";

// mix
const mix = array => {
    const { length: n } = array;
    for (let i = 0; i < n; i++) {
        const x = Math.floor(Math.random() * n);
        [array[i], array[x]] = [array[x], array[i]];
    }
    return array;
};

const A = 'A'.charCodeAt(0);
const NB_LETTERS = 26;

const TABLE = {};
for (let i = 0; i < NB_LETTERS; i++) TABLE[String.fromCharCode(A + i)] = 0;

for (let N = 1; ; N++) {

    // init
    const array = [];
    for (let i = 0; i < NB_LETTERS; i++) array[i] = String.fromCharCode(A + i);

    mix(array);

    TABLE[array[0]]++;

    if (N % 1000000 === 0) {
        console.log('');
        console.log("N =", N);
        console.log(
            Object.entries(TABLE)
                .map(([letter, n]) => {
                    const freq = n / N;
                    return letter + '\t' + freq.toString().replace('.', ',');
                })
                .join('\n')
        );
    }
}

Questions:

  • Do you get the same results?
  • Is it from Math.random() ? I think so ... do you know of an alternative that would give a uniform distribution?

Thanks in advance !

Solution

  • The shuffle algorithm in the function mix is not correctly implemented.

    The algorithm in the referenced Wikipedia article stipulates that the range to take a random number from should be different in each iteration, which is not the case in your implementation, hence the non-homogeneous distribution.

    Make this correction:

        const x = i + Math.floor(Math.random() * (n - i));

    Other implementations (with some optimisations) can be found at How to randomize (shuffle) a JavaScript array?