Math.random() unsatisfactory

Question

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

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 !

Does this answer your question? [Secure random numbers in javascript?](https://stackoverflow.com/questions/4083204/secure-random-numbers-in-javascript) — Justinas, Aug 01 '22 at 13:11
`Math.random()` gives you pseudo-randomness. But what exactly is your question? Why `Math.random()` gives not even/random results? — Justinas, Aug 01 '22 at 13:12
`Is it from Math.random() ? I think so` `Math.random` even though pseudo should still be given you an even distribution, certainly not 2x difference, there is something else wrong here. — Keith, Aug 01 '22 at 13:16
https://stackoverflow.com/questions/1062902/how-random-is-javascripts-math-random — epascarello, Aug 01 '22 at 13:20

score 4 · Accepted Answer · answered Aug 01 '22 at 13:21

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?

Math.random() unsatisfactory

1 Answers1