计算n面骰子在M次投掷中每个面出现次数的最快方法

Question

给定M次掷N面骰子，我想生成一个N数组，用于存储骰子每个面出现的次数。

例如，对于一个六面骰子，投掷10次，你可能会得到:

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

又名21's,32's,23's,14,15,16.

第一个明显的解决方案是生成M个随机数并计数:

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)];

我想知道是否有更快的。我的一个想法是从预期的计数开始，并应用一些随机的"洗牌":

对于掷60次6面骰子，你期望的计数是:

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

你可以随机选择2个索引，加1，减1:

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

然后重复X次。这个的问题是它实际上并没有给你一个正确的数字，它只是给了你一个令人信服的m，加上，你怎么选择X?

另一个想法是想象一条长度为M的线，并在其中选择N个分叉来生成你的组:

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 ]

这种方法的问题是它不能正确地表示掷骰子产生的概率。例如，通过此方法从6个骰子中创建的配置[3, 0, 0, 1, 1, 1]出现的概率与实际掷出31,02,03,14,15和16的概率不同。

也许这只是不可能比仅仅执行掷骰子和计数更快。

Answer 1

感谢Robert Dodier指出我可以使用多项分布!

在python中，其他人可以查看https://numpy.org/doc/stable/reference/random/generated/numpy.random.multinomial.html

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

如果你不能使用numpy，有很多关于如何实现这个的文献，但对我来说，numpy库就足够了，它运行得非常快。

这里有一些链接，但是对于那些想要了解实现的人:

• https://en.wikipedia.org/wiki/Multinomial_distribution
• https://sites.warnercnr.colostate.edu/gwhite/wp-content/uploads/sites/73/2017/04/MultinomialDistribution.pdf

Answer 2

免责声明:下面的内容目前并没有提供足够的信息来改进你最有效的解决方案，因为我不知道我需要完成它的确切数学解决方案，但我还是想把它贴出来，以防其他人可以看到讨论完成。

对于您的长度为m的解，描绘每个组相当于生成一个随机数[0,1)之间，并找到它落在二项累积分布。例如，如果你有一个3面骰子和4次投掷，你将如何决定在哪里划分组:

1. 模拟a "1"在[0,1)之间产生第一个随机数——假设你得到0.67。p=1/3, n=4时的二项累积分布为:

tbody> <<tr>124

成功次数	离散概率	累积概率
0	(1/3) ^ 0 * (2/3) ^ 4 * (4 c0)≈0.20	0.20
	(1/3) ^ 1 * (2/3) ^ 3 * (4 c1)≈0.40	0.60
	(1/3) ^ 2 * (2/3) ^ 2 * (4 c2)≈0.29	0.89
3	(1/3) ^ 3 * (2/3) ^ 1 * (4 c3)≈0.10	0.99
	(1/3) ^ 4 * (2/3) ^ 0 * (4 c4)≈0.01	1