gnu /
make /
9251546bac031db325da80c4a8429db67c5578f7 Fix biased shuffle by avoiding already "struck" elements
Artem Klimov noticed that current shuffle implementation suffers from
probability bias due to a typical bug in the shuffling implementation.
When we consider already shuffled element we slightly bias their
propability.
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
suggests shuffling each "struck" element only once.
Before the change probabilities of 4-element array to land from `i`
index to `j` index are:
0 1 2 3
_____ _____ _____ _____
0 | 25.00 29.30 24.60 21.10
1 | 25.00 22.25 28.13 24.63
2 | 25.00 23.44 22.26 29.30
3 | 25.00 25.01 25.01 24.98
Note that `0->1` probability is almost 29% while `0->3` os only 21%.
After the change probabilities are not as biased:
0 1 2 3
_____ _____ _____ _____
0 | 24.99 24.99 25.01 25.01
1 | 24.99 25.04 24.99 24.99
2 | 25.01 25.00 25.00 24.99
3 | 25.01 24.98 25.00 25.01
* src/shuffle.c (random_shuffle_array): Fix biased shuffle by avoiding
already "struck" elements.
1 file changed
