Tutorial :Will using modulus favour high numbers?



Question:

Will adding 6 random unique numbers in the range 0-32 and doing a modulus on the result favour a high number?

Example: 9 +10 +11 +18 +25 +28 +32 = 133 % 20 = 13


Solution:1

No. Its even, or at least the skew doesn't seem to be more than 0.05 %.

Even though the range of possible numbers does not evenly map to the mod ( 192 % 20 = 12 ), the range of distribution is much greater than the mod, so it works it self out. Here's my run of 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  


Solution:2

As an interesting aside, there is a powerful method which can be used to figure this out manually, or very fast (instead of using brute force) on a computer using the concept of Generating Functions.

(Warning: longish post)

You are working in the range 0 to 19, but getting that by generating numbers at random from 0-32.

If the chance of getting the number i is p(i) [Note, p(0) = p(1) = p(2) = ... = p(12) and p(13) = ..= p(19) and p(0) = 2p(13)).

Now we are interested in the chances of getting a particular sum by generating random numbers 6 times and adding them up.

This can be modelled by computing coefficients in the sixth power of the polynomial

P(x) = p(0) + p(1) * x + p(2) * x^2 + ... + p(r) * x^r + ... + p(19) * x^19

Thus we are looking at the coefficients of (P(x))^6.

For the given problem, we can ignore the 1/33 factor (in order to compare which sum is more likely) and have p(0) = 2, p(1) = 2, ..., p(19) =1.

Thus we are looking at P(x) = 2(1 + x + x^2 + ... + x^12) + x^13 + x^14 + .. + x^19.

We now just need to compute the coefficients of its sixth power, take the exponents modulo 20 and add them up. Fast polynomial multiplication algorithms like FFT can be used here.

In fact we could probably do it manually using some algebra with complex numbers and/or prove statements about the probability distribution with conviction.


Solution:3

The answer is: It depends. The following sample program will print the average values for various modulus values. Obviously it's not a mathematical proof but it should give you already a feeling how the average values behave:

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());      }  }  

Output generated:

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  


Solution:4

Here is a small python program for computing the probability distribution

# 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)))  

This gives the following result:

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  

I.e. the high numbers are indeed a little more probable, but the differences are very small.


Solution:5

Counterexamples:

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

Which perhaps suggests you could usefully clarify or sharpen your question.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »