Uniformly sample among reduced fractions between 0 and 1 whose denominator is less than N. For example, for N=5, we want to uniformly sample among 5 items 1/2, 1/3, 2/3, 1/4, 3/4 (excluding 2/4). At first I thought this might be difficult to do for large N, but upon further consideration, it looks easy: choose a numerator and denominator, then reject and try again if GCD not equal to 1. What is the expected number of repetitions? This is a well studied problem in number theory whose answer is related to zeta(2)=6/pi^2. To first order, failures are dominated by choosing 2 even numbers. Rarely does one need to try more than a few times.

## No comments :

Post a Comment