Picking a random item from array with equal distribution

I want to pick a random item from an array at random.

Math.floor(Math.random() * array.length);

Is the way to go, but as far as I know this will cause a Uniform distribution to occur which means that the average is (lowbound+upperbound)/2 translated to an array with 10 elements the lower bound is the first element and the upper bound is the last element causes an average of 5, which is not random

Therefore, I looked at the frequency distribution of this way of random picking an item by having 10 elements and picking one with the code above. The element represents the index and is pushed into an array. After 10000 numbers, the frequency is counted and given.

This has the following results:

Index: Frequency
0: 1083
1: 996
2: 1022
3: 966
4: 958
5: 962
6: 1044
7: 1045
8: 972
9: 952

Ofc, this is only 1 run of 10k numbers. But it shows that index 0 has a 10.8% chance and index 9 has a 9.5% chance. This difference is 1.3% which I find quite a lot.

Are there methods that can do this better? For example, get to 0.05% difference in numbers? The ideal situation would be that they are all 10% (equally distributed).

Answer

If you can precompute the result (i.e. you need a finite number of results, not an infinite stream) and the number of results is divisible by the number of items, you can get a perfect distribution:

1. Generate an array that repeats the items until you’ve got enough, i.e. [1, 2, 3, 1, 2, 3, 1, 2, 3, ...]. The array is thus guaranteed to have exactly as many instances of each item.
2. Shuffle the array with a fair shuffle algorithm, e.g. Fisher-Yates. The array still has exactly as many instances of each item.

If you do need an infinite stream, you could use something like an “item bag” model (which, btw, is how the blocks in Tetris are chosen):

1. Fill a “bag” with your items ([1, 2, 3]). Shuffle it (as above).
2. When you need an item, pop the first one from the shuffled bag.
3. If the bag is empty, re-fill it according to step 1.

The only case where this doesn’t have a perfect distribution is if you stop “mid-bag”.