在 0-32 范围内添加 6 个随机唯一数字并对结果进行取模有利于大数字吗？
示例：9 +10 +11 +18 +25 +28 +32 = 133 % 20 = 13
问问题
1128 次
5 回答
6
有趣的是，有一种强大的方法可用于手动计算，或者使用生成函数的概念在计算机上非常快速（而不是使用蛮力）计算出来。
（警告：过长的帖子）
您在 0 到 19 的范围内工作，但是通过从 0-32 随机生成数字来获得它。
如果得到数字 i 的机会是 p(i) [注意，p(0) = p(1) = p(2) = ... = p(12) 和 p(13) = ..= p( 19) 和 p(0) = 2p(13))。
现在我们对通过生成 6 次随机数并将它们相加来获得特定总和的机会感兴趣。
这可以通过计算多项式的六次方系数来建模
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 等快速多项式乘法算法。
事实上，我们可能可以手动使用一些具有复数的代数和/或证明关于概率分布的陈述。
于 2010-02-09T20:26:15.507 回答
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
于 2010-02-09T19:48:31.000 回答
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
即高数字确实更有可能，但差异非常小。
于 2010-02-09T21:11:43.697 回答
0
反例：
9 +10 +11 +18 +25 +28 +32 = 133 % 2 = 1
9 +10 +11 +18 +25 +28 +32 = 133 % 200 = 133
这可能表明您可以有用地澄清或尖锐化您的问题。
于 2010-02-09T19:25:54.147 回答
0
不，它是均匀的，或者至少偏差似乎不超过 0.05%。
尽管可能数字的范围没有均匀地映射到 mod ( 192 % 20 = 12 )，但分布范围比 mod 大得多，所以它可以自行解决。这是我运行的 1,000,000。
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
于 2010-02-09T22:09:45.417 回答