Будет ли использование модуля благоприятствовать большим числам?

Question

Будет ли добавление 6 случайных уникальных чисел в диапазоне 0-32 и использование модуля для результата в пользу большого числа?

Пример: 9 +10 +11 +18 +25 +28 +32 = 133% 20 = 13

Answer 1

Как интересно, существует мощный метод, который можно использовать, чтобы выяснить это вручную или очень быстро (вместо использования грубой силы) на компьютере, используя концепцию Генерация функций .

(Внимание: длинный пост)

Вы работаете в диапазоне от 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) * х ^ 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.

Фактически, мы могли бы сделать это вручную, используя некоторую алгебру с комплексными числами, и / или доказать утверждения о распределении вероятностей с убеждением.

Answer 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

Answer 3

Вот небольшая программа на 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

т.е. высокие цифры действительно немного более вероятны, но различия очень малы.

Answer 4

Нет. Его даже, или, по крайней мере, перекос не превышает 0,05%.

Несмотря на то, что диапазон возможных чисел не соответствует моду (192% 20 = 12), диапазон распределения намного больше, чем мод, поэтому он работает самостоятельно. Вот мой пробег 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

Answer 5

Контрпримеры:

9 +10 +11 +18 +25 +28 +32 = 133 % 2 = 1

9 +10 +11 +18 +25 +28 +32 = 133 % 200 = 133

Что, возможно, говорит о том, что вы могли бы с пользой уточнить или обострить ваш вопрос.