4

0〜32の範囲で6つの乱数を追加し、結果にモジュラスを実行すると、高い数値が優先されますか？

例：9 +10 +11 +18 +25 +28 +32 = 133％20 = 13

4

5 に答える 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回生成し、それらを合計することによって特定の合計を取得する可能性に関心があります。

これは、多項式の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を見ています。

ここで、6乗の係数を計算し、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 に答える