Search code examples
algorithmprobabilityprobability-distribution

Fastest way to count the number of times each face of a N-sided dice appears for M rolls

Given M rolls of an N sided dice I want to generate an N array which stores the count for the number of times each face of the dice appears.

For example, for a 6 sided dice, for 10 rolls you might get:

[2, 3, 2, 1, 1, 1]

AKA 2 1's, 3 2's, 2 3's, 1 4, 1 5, 1 6.

The obvious first solution is to just generate M random numbers and count them:

Random r = new Random();
int[] counts = new int[6] { 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < 10; i++) ++counts[(int)Math.Round(r.NextDouble() * 5)];

I was wondering if there was anything faster. A thought I had was to start from the expected counts and apply some random "shuffling":

For 60 rolls of a 6 sided dice, you expect a count of:

[10, 10, 10, 10, 10, 10]

You could then randomly select 2 indexes and add 1 and subtract 1:

[11, 10, 9, 10, 10, 10]

Then repeat this X times. The problem with this is it doesn't actually give you a proper count, it just gives you a convincing one at large M. Plus, how would you pick X?

Another thought was to imagine a line of length M and pick N splits in it to generate your groups:

9 rolls:

0 1 2 3 4 5 6 7 8 9
|-----------------|
|   | |   | |     |
1   2 3   4 5     6

[2-0, 3-2, 5-3, 6-5, 9-6, 9-9]
[ 2 ,  1 ,  2 ,  1 ,  3 ,  0 ]

The problem with this method is it doesn't properly represent the probability created by dice rolls. For example, the configuration [3, 0, 0, 1, 1, 1] from 6 dice rolls created by this method has a different probability of showing up than you actually rolling 3 1's, 0 2's, 0 3's, 1 4, 1 5 and 1 6.

Maybe it's just not possible to do this any faster than just performing the rolls and counting.

Solution

  • Thanks to Robert Dodier for pointing out I can just use a multinomial distribution!

    In python others can look at https://numpy.org/doc/stable/reference/random/generated/numpy.random.multinomial.html

    np.random.multinomial(20, [1/6.]*6, size=1)

    There is various literature on how to implement this if you cannot use numpy, but for me the numpy library is enough and it runs blazing fast.

    Here are some links though for those that want to look into implementation: