How to arrange a set of number?

Mathematical Puzzles: How can someone pick a number with uniform probability from a large set of numbers, given a small random number generator? [note: see details]

• Given  a large set of numbers S={1,⋯,n}S={1,⋯,n}S =\left \{ 1, \cdots , n  \right \} and a uniform random generator that picks numbers from a  smaller set {1,⋯,m}{1,⋯,m}\{ 1, \cdots , m \}, where m≪nm≪nm \ll n  ; is there a method to pick a number from S with uniform probability  without repetition? For repetition i mean: i can simulate a large dice with a coin (or a generator that picks numbers from set {1,2}{1,2}\{ 1,2 \}  ) via binary numbers. I throw the coin k times to create a binary  number of k digits, but with k digits my "virtual" dice can represent  2k2k2^k numbers and can be true that 2k>n2k>n2^k>n, so  if the process simulate a number that is greater than n, i must repeat  it. This is an evolution of this question: http://math.stackexchange.com/questions/273052/pick-a-card-from-a-set-with-the-help-of-a-dice

• Answer:

  Suppose a∗n=mka∗n=mka*n = m^k for some integers aaa and kkk. Then a/mk=1/na/mk=1/na/m^k = 1/n, so you can generate k rolls and interpret it as a base-m number. If it is less than a, choose 1. If it is less than 2*a, choose 2. Etc. That solves the case where n eventually divides m^k. This happens exactly if every prime factor of n is also a prime factor of m. If this isn't the case, you're out of luck: every scheme involves generating some number of rolls and splitting them up in some way, so we can only achieve probabilities with a power of m in the denominator. But 1/n cannot be written in this way. You can always get arbitrarily close to uniform, though.