Random bias?

[skandragon]

From the code:

export function randomChar(prng) {
    let rand = Math.floor(prng() * ENCODING_LEN);
    if (rand === ENCODING_LEN) {
        rand = ENCODING_LEN - 1;
    }
    return ENCODING.charAt(rand);
}

I believe this biases the final character in the ENCODING array, which has two different random values it can be created from.

I believe what you want is to do is select a new random number in this case, since while it is difficult to get this value (a 1 in 256 chance) that is still an increase in bias.

While the increase is small, it feels like using a strong prng only to add unnecessary bias should be addressed.

[darrelfrancis]

Hi @j0pgrm

Your if statement is there to cover the possbility that your PRNG will generate the number 1.
In general, PRNGs produce values from 0 to less than 1, i.e. from the range 0 (inclusive) to 1 (exclusive). This is because when they generate an N-bit binary fraction, the highest value (all 1s) will be just a tiny bit smaller than 1.

Your Math.floor correctly rounds downward, so that rand will be in the range 0 (inclusive) to ENCODING_LEN - 1 (inclusive).
So the if will never be triggered.

If, for some reason, you in future switch to a prng that somehow can generate a 1, for example because it has an idiosyncratic desire to cover a range of 0 (exclusive) to 1 (inclusive), then:

• the chance of this is extremely small (1 in 2^N, not 1 in 2^8)
• the PRNG will have lost the ability to generate 0
• your random character generator would have a micrscopically smaller chance of generating the first encoding character, and have a microscopic chance of trying to pick the non-existent character at #ENCODING_LEN.

A neat solution for you is to simply wrap round that exactly-1 PRNG value back to 0, most conveniently A simple way to achieve this is to modulo the rand by ENCODING_LEN.

I will do a PR for this.

Thank you for an excellent library.

[skandragon]

A neat solution for you is to simply wrap round that exactly-1 PRNG value back to 0, most conveniently A simple way to achieve this is to modulo the rand by ENCODING_LEN.

No, you specifically do not want to do this with random values. This adds bias in that there are multiple ways to get the same final value.

For example, if you had 0, 1, 2, 3, 4, 5, 6 as possible values from your random source, and you modulo them down to 4 possibilities, you end up with 0, 1, 2, 3, but 0, 1, and 2 have two ways to get there, and 3 only has one choice. You want to either scale or drop out-of-bounds inputs such that all the remaining values coming in will consistently be matched to the same number of outputs.

[darrelfrancis]

Hi @skandragon,

Yes that is correct if there is more than one way to get to the same final value.

However, PRNGs generate numbers between 0 (inclusive) and 1 (exclusive), so there is only one way to get to 0 after a modulo, namely from the PRNG generating 0.

If a future PRNG swivels its output range to end at exactly 1 (rather than before it), it will simultaneously lose the ability to generate 0. This is a theoretical possibility, and not the case for current PRNGs.
And even in that theoretical possbliity, there will still only be one way of getting a final answer of 0, namely the PRNG generating exactly 1.

The example you quote of 0 1 2 3 4 5 6 is not relevant to the PRNGs we are using which produce binary fractions between 0 and 0.9999999etc.