While trying to find a solution for it, I found few interesting ideas and in this article I put them down.
I see generating a set of five numbers by running the given random function five times and summing them will give me a number range [5,25]. There are 21 numbers {5, 6, .. 24, 25} in this range and we can group them in 7 groups – like {5,6,7} {8,9,10} { 11,12,13} and so on. Since all we want a function to generate numbers in the range [1,7] with equal probability, we need to group the numbers in such a way that probability of occurrence of each group is same. We can then map each group with a number {1, 2.., 7} and return the associated numbers when a group occurs. Thus we can achieve a random number generator of the range [1,7]
To calculate occurrences of each group we can calculate occurrence of each element in the group and add each elements occurrence group wise. Now we need a way to find out occurrences of each number from [5,25] when we run our given random generator 5 times.
This is same as finding co-efficient of each terms in the expansion (x^1+x^2+...+x^5) ^5.
Extending this idea we see that each group needs not to have equal elements as long as each group has same value of occurrence. In our case, to generate 7 numbers with uniform pdf (probability density function), all we need is Sg1=Sg2=...=Sg7, no matter how many elements each group has. Sg1 denotes occurrences of group one = sum of occurrences of each elements in group one. Similarly Sg2 identifies for group 2 and so on.
Moreover, since Sg1=Sg2=...=Sg7, sum of all groups (∑Sg) is a multiple of 7, which means:
[sum (coefficient of each element)] mod 7 =0 [divisible by 7]
This is a necessary property but not enough alone. We can use this property to improve our algorithms.
In general, if we run the random function with range [1,5] for k times, we get a sum of range [1.k, 5.k]. We can group all the sums in 7 groups such that Sg1=Sg2=...=Sg7 to ensure no of occurrence of each group is same. If each group maps a number from {1, 2, .. 6, 7} the probability of getting a number from [1,7] will be equal as well.
Thus the problem translates into
1. Finding the coefficients of the expansion (x^1+x^2+...+x^n) ^k where n=5 in our case and k is an integer such that no of terms in the expansion is more than N (in our case N=7) i.e. (n.k) ≥ N
2. For a specific k, group the coefficients into N groups such that sum of coefficients in each group is same.
3. If this is not possible take a new value of K where K = K +1 and repeat steps 1-2.
4. Once we find a group of N satisfying the equal sum property (i.e. equi-probable) we number each group by [1,N].
5. Whenever a number obtained by summing the numbers obtained by k execution of original random function belongs to a group, we return the group’s number. Since the probability that a number (sum of k trials/execution) belongs to one of the group is equal; the probability that we return a group number from [1,N] is equal. So we achieved a random function of range [1,N] from another random function [1,n] where n ≤ N
Sample trial: n=5, N=7, k=5
(x^1+x^2+x^3+x^4+x^5) ^5
=x^5 + 5.x^6 + 15.x^7 + 35.x^8 + 70.x^9 + 121.x^10 + 185.x^11 + 255.x^12 + 320.x^13 + 365.x^14 + 379.x^15 + 363.x^16 + 318.x^17 + 253.x^18 + 183.x^19 + 121.x^20 + 70.x^21 + 35.x^22 + 15.x^23 + 5.x^24 + x^25
Observe that ∑Sg = ∑ Coefficients =
(1+5+15+35+70+121+185+255+320+365+379+363+318+253+183+121+70+35+15+5+1)
=3115
∑Sg mod N = 3115 mod 7 = 0 -- implies we may get 7 groups with sg1=sg2=…=sg7
But when I tried to create 7 groups I found that its not possible to have 7 groups such that each goups sum is 445 (=3115/7) . I still tried to get the best grouping I can and is as follows
| Group # | Elements in Group(co-eff. in the expansion) | Sum of coefficients in a group | Probability of a group |
|---|---|---|---|
| 1 | 8, 15, 21 | 449 | 14.414 % |
| 2 | 7, 9, 14 | 450 | 14.446 % |
| 3 | 16, 21, 24 | 448 | 14.382 % |
| 4 | 5, 10, 13 | 442 | 14.189 % |
| 5 | 17, 20, 25 | 440 | 14.125 % |
| 6 | 6, 12, 19 | 443 | 14.222 % |
| 7 | 11, 18, 24 | 443 | 14.222 % |
| ∑=3115 |
This means if we try our original random generator for n=5 times, we obtain a set of n values; say 4, 2, 2, 3 and 1. The sum of these values is 12. Since the coefficient of x^12 belongs to group 6, we return 6.
Even when we have almost equi-probable groups, they are not perfectly same. Thus we should try with another value of k, say k=6
