Wednesday, October 18, 2017

[vttngych] Sampling fractions uniformly

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