Execute f 7 times, add all numbers, call that x. Then you do mod(x,7)+1, and you get a random number between 1 and 7. If the original function was unbiased, this one is going to be unbiased too.
I didn't want to go through all 5^7 possibilities for the 7-die case, but I figured it's likely enough that he's right that I'd keep my mouth shut.
r = random.Random()
def one_to_five():
return r.randint(1, 5)
def mod_seven():
return (sum(one_to_five() for x in xrange(7)) % 7) + 1
def test_dist(lst):
return [(x, lst.count(x)) for x in [1,2,3,4,5,6,7]]http://spreadsheets.google.com/ccc?key=pq4tB7LQWN03gF7ImGhIP...
edit: Oops bad addition on my part, could be uniform, but you'd have to work out the actual number exactly.
1 -> 11177
2 -> 11172
3 -> 11158
4 -> 11144
5 -> 11144
6 -> 11158
7 -> 11172
...not quite
Now use that process to get 3 binary digits. You get a random number from 0 to 7. If the random number is 0, start again... eventually you'll get a number from 1 to 7, and all numbers have the same chances.
But, if you want to uniformly map a random number from set X to set Y where (IIRC) lcm(|X|, |Y|) != |X|, it seems you need an infinite worst-case running time.
Here's an informal proof that you can't have a finite upper bound to the number of iterations. After n iterations, you have |X|^n possible outcomes. But, since lcm(|X|, |Y|) != |X|, |X|^n cannot be divided evenly by |Y| (since its factors are the same). So some outcomes in Y must be more likely than others.
(This is not nearly complete, but hopefully it's enough to show how it might be right.)
Of course, in practice it is highly unlikely that you will get past more than a couple iterations before determining an outcome.
Can you go into more detail about this part?
Here is an explanation with the new condition:
Let p be any prime factor of |Y| that |X| does not have. It follows from Euclid's First Theorem[1] that p cannot divide |X|^n for any n [2]. Since every integer (> 1) has a unique prime factorization, it follows that |X|^n can't divide |Y|, because the prime p divides |Y| but not |X|^n.
[1] http://mathworld.wolfram.com/EuclidsTheorems.html [2] We are given that p does not divide |X|^1. Suppose that p also does not divide |X|^(n-1) for some n > 1. |X|^n = |X|^(n-1) * |X|^1, so by Euclid's First Theorem, if p divides |X|^n it must divide either |X|^(n-1) or |X|^1. We know it divides neither, so p does not divide |X|^n. By induction, this is true for all n > 0.