1

I came across a question in StackOverflow which states the following, all is based on natural numbers:

Given the function rand5 (which produces random natural numbers 0-4), use it to generate a rand7 (which produces random natural numbers 0-7).

I came across with solution which does the following:

$convertRand(7, 5) = \left [ \sum_{1}^{7}(rand(5)) \right ] \bmod 7$

In case my latex knowledge is not good enough, what it does is add up 7 times rand5 and then get the modulus of the result. I ran tests with millions of iterations, and distribution seems quite fair (never perfect as we are talking about random numbers).

So, the generic solution would look like:

$convertRand(dest, origin) = \left [ \sum_{1}^{dest}(rand(origin)) \right ] \bmod dest$

I tried with some values (7 for dest, 13 for origin and such), and distribution still seems quite even... However, I'm not finding a way to prove why this works...

Adding the rand5 7 times produces numbers between 0 and 28, but with more liklyness in middle values (like 14) and fewer results in the edges, specially on the high edge...

However, if I add rand5 a not by 7 divisible amount of times and then apply modulus 7, the distribution is not uniform anymore.

Here's the Question with my Reply on Stackoverflow (just not to post code here):

https://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7/26405409#26405409

So, in case my specific question is too mixed into my writing... How can I prove if this generic solution is true mathematically?

Statistically I would say it is as I get even distributions on multiple runs with millions of iterations...

joriki
  • 238,052
Martin
  • 111

1 Answers1

0

The easy way to disprove it is to show a counterexample. I will modify your approach slightly to use positive integers. So let's say you can randomly generate 1's and 2's but want to randomly generate 1's, 2's, and 3's.

Under the proposed method, we would generate, say, a 1 if the sum of 3 randomly generated numbers is 0 mod 3, a 2 if the sum is 1 mod 3, and a 3 if the sum is 2 mod 3.

So what is the probability of generating a 1 under this setup? The only way to get a sum that is 0 mod 3 is by one of these two combinations: 111 or 222. But the chance of this happening is (1/8)+(1/8) = 1/4. Since this is not equal to 1/3, your method breaks down.

soakley
  • 1,572