在范围0-32内添加6个随机唯一数字并对结果进行模运算，是否会偏向于较高的数字？
例如：9 + 10 + 11 + 18 + 25 + 28 + 32 = 133 % 20 = 13
使用模数运算是否有利于较大的数字？
4
- Makach
6
36个随机数之和不是均匀分布的，因此这个和的模也没有理由是均匀分布的。你真的需要有人计算产生0、1、...19的不同组合来证明更高的数字确实更受青睐吗？还是“它不均匀分布因为没有理由均匀分布”是你想要的答案？ - Pascal Cuoq
@Pascal：你能解释一下从“总和不均匀分布”到“这个总和的模也不是均匀分布的”这一步骤吗？ - Dirk Vollmar
@divo 我想表达的意思更多是“没有理由认为模数是均匀分布的，因为总和本身并不是”。如果我要确定模数确实不均匀分布，我必须枚举所有可能性，但如果 OP 只是因为它是随机的就假设它应该均匀分布，那么我宁愿避免这样做。 - Pascal Cuoq
1在计算机中，不存在所谓的随机性... :-) - Gnark
1注意，所有认为六个均匀分布数字的总和也是均匀分布的人！谁想和我打赌，我可以通过掷两个六面骰子得到7？我可以提供看起来不错的赔率！ - Pascal Cuoq
为什么不写一个快速的暴力程序来解决它呢？计算所有可能的数字组合，找到这些组合的总和，执行模运算，并查看结果。 - pjbrown88
5个回答
6
作为一个有趣的旁白，有一种强大的方法可以手动或者非常快速地（而不是使用暴力计算）在计算机上使用生成函数的概念来解决这个问题。
因此，我们正在查看P(x) = 2(1 + x + x^2 + ... + x^12) + x^13 + x^14 + .. + x^19。
现在我们只需要计算它的六次幂的系数，取模20的指数并将它们相加。 快速多项式乘法算法（如FFT）可在此处使用。
实际上，我们可能可以手动使用一些关于复数的代数或证明关于概率分布的语句来完成它。
（警告：较长的帖子）
您正在使用 0 到 19 的范围，但通过随机生成 0-32 的数字来实现。
如果获得数字 i 的概率为 p(i) [注意，p(0)=p(1)=p(2)=...=p(12)和p(13)=..=p(19)，并且p(0)=2p(13)]。
现在我们感兴趣的是通过生成随机数六次并将它们相加来获得特定总和的机会。
这可以通过计算多项式的第六个幂的系数来建模
P(x)=p(0)+p(1)*x+p(2)*x^2+...+p(r)*x^r+...+p(19)*x^19
因此，我们正在查看(P(x))^6的系数。
对于给定的问题，我们可以忽略1/33因子（为了比较哪个和更有可能），并且p(0)=2，p(1)=2，...，p(19)=1。因此，我们正在查看P(x) = 2(1 + x + x^2 + ... + x^12) + x^13 + x^14 + .. + x^19。
现在我们只需要计算它的六次幂的系数，取模20的指数并将它们相加。 快速多项式乘法算法（如FFT）可在此处使用。
实际上，我们可能可以手动使用一些关于复数的代数或证明关于概率分布的语句来完成它。
- Aryabhatta
3
你在“p(0)=2p(13)”这里就把我搞丢了。我原本以为取模应该作用于总和上，而不是单个的求和项。 - Pascal Cuoq
@Pascal：这只是针对一个数字的情况。如果你取0-32并取模20，你会得到这些概率。请注意，（x+y）模20与（（x模20）+（y模20））模20相同。 - Aryabhatta
生成函数确实是解决这类问题的好工具。由Graham、Knuth和Patashnik合著的《具体数学》一书对这个主题有很好的介绍。 - Accipitridae
2
答案是：这取决于情况。下面的示例程序将打印不同模数值的平均值。显然，这并不是一个数学证明，但它应该已经给您一种感觉，平均值的行为方式如何：
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static Random rand;
static void Main(string[] args)
{
rand = new Random();
for (int modulus = 1; modulus < 1000; modulus++)
{
calculateAverage(modulus);
}
}
public static void calculateAverage(int modulus)
{
List<int> moduloList = new List<int>(100);
for (int i = 0; i < 100; i++)
{
int sum = 0;
for (int k = 0; k < 6; k++)
{
sum += rand.Next(0, 33);
}
moduloList.Add(sum % modulus);
}
Console.WriteLine("Average for modulus {0}: {1}", modulus, moduloList.Average());
}
}
生成的输出：
Average for modulus 1: 0
Average for modulus 2: 0,49
Average for modulus 3: 1,03
Average for modulus 4: 1,47
Average for modulus 5: 1,96
Average for modulus 6: 2,55
Average for modulus 7: 3,03
Average for modulus 8: 3,42
Average for modulus 9: 4,15
Average for modulus 10: 5,06
Average for modulus 11: 4,62
Average for modulus 12: 5,9
Average for modulus 13: 5,82
Average for modulus 14: 6,8
Average for modulus 15: 7,28
Average for modulus 16: 7,8
Average for modulus 17: 8,15
Average for modulus 18: 9,34
Average for modulus 19: 9,2
Average for modulus 20: 10,36
Average for modulus 21: 9,74
Average for modulus 22: 9,41
Average for modulus 23: 11,5
Average for modulus 24: 11,51
Average for modulus 25: 11,45
Average for modulus 26: 13,05
Average for modulus 27: 12,59
Average for modulus 28: 14,92
Average for modulus 29: 13,1
Average for modulus 30: 14,1
Average for modulus 31: 15,5
Average for modulus 32: 16,46
Average for modulus 33: 16,54
Average for modulus 34: 16,38
Average for modulus 35: 19,61
Average for modulus 36: 17,26
Average for modulus 37: 15,96
Average for modulus 38: 19,44
Average for modulus 39: 17,07
Average for modulus 40: 17,73
- Dirk Vollmar
4
不错。我只点赞一次，因为你没有生成每个可能的模数选择的实际分布的3D图形 :) - Pascal Cuoq
100个样本不足以获得具有统计学意义的结果。例如，要显示结果对模数20和范围0-32的较大余数存在偏差，需要数百万个样本。 - Accipitridae
@Accipitridae：这只是一个示例。您可以根据需要调整值。 - Dirk Vollmar
当然，您可以更改样本数量。但是，在计算偏差之前，您不知道需要多少样本。如果您查看Sanjaya R的答案，那么您会发现他使用了1000000个样本，但仍然得到了错误的答案。也就是说，数字的分布存在偏差，但是使用1000000个样本无法注意到这种偏差。 - Accipitridae
1
这是一个用Python编写的小程序，用于计算概率分布。
# modulus
m = 20
# range of the random numbers 0..n-1
n = 33
# number of random numbers in sum
k = 6
# distribution of one random number
# a[i] is the probability that a random number modulo m is i.
a = [0]*m
for i in range(n): a[i % m]+= 1/n
# convolution
b = a
for i in range(1,k):
# Here b[t] is the probability that the sum of i random numbers is t.
# Compute c[t] as the probability that the sum of i+1 random numbers is t.
c = [0]*m
for i in range(m):
for j in range(m):
c[(i+j)%m] += a[i]*b[j]
b=c
# print the probability distribution of the result
for i in range(m): print(i, b[i])
# compute average
print("average", sum(i*b[i] for i in range(m)))
这将给出以下结果：
0 0.0500007971936
1 0.0499999764222
2 0.0499991633939
3 0.0499984370886
4 0.0499978679688
5 0.0499975063648
6 0.0499973824748
7 0.0499975063648
8 0.0499978679688
9 0.0499984370886
10 0.0499991633939
11 0.0499999764222
12 0.0500007971936
13 0.0500015451796
14 0.0500021452719
15 0.0500025347512
16 0.0500026702559
17 0.0500025347512
18 0.0500021452719
19 0.0500015451796
average 9.50015120662
也就是说，高数值确实可能性稍微更大一些，但差别非常小。
- Accipitridae
0
反例：
9 +10 +11 +18 +25 +28 +32 = 133 % 2 = 1
9 +10 +11 +18 +25 +28 +32 = 133 % 200 = 133
这或许表明您可以有用地澄清或深化您的问题。
- High Performance Mark
1
也许OP指的是与模数相关的“高”，即sum％modulus> modulus / 2。 - Dirk Vollmar
0
不是的。它是偶数，或者至少偏差似乎不超过0.05%。
即使可能数字的范围不能均匀地映射到模数（192％20 = 12），分布范围比模数大得多，因此可以自行解决。 这是我运行的100万次。
MOD COUNT %
0 50098 5.00980
1 49660 4.96600
2 49832 4.98320
3 50150 5.01500
4 50276 5.02760
5 49864 4.98640
6 50282 5.02820
7 49771 4.97710
8 49886 4.98860
9 49663 4.96630
10 49499 4.94990
11 49964 4.99640
12 50155 5.01550
13 50169 5.01690
14 49829 4.98290
15 50191 5.01910
16 49887 4.98870
17 50334 5.03340
18 50139 5.01390
19 50351 5.03510
- Sanjaya R
1
这甚至没有达到某个阈值。 - Dirk Vollmar
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接