3 ms·
No. The two methods are qualitatively equally good. In both cases, some outputs have probability floor(2^n/K)/2^n while others have probability ceil(2^n/K)/2^n.
by atq2119 5y ago
No. The two methods are qualitatively equally good. In both cases, some outputs have probability floor(2^n/K)/2^n while others have probability ceil(2^n/K)/2^n. The numbers of outputs with each probability are such that they average out to 1/K. The only difference is the distribution of which output numbers have which of these two probabilities.
- pwuille 5y agoExactly, both the modulo and the multiplicative method are equally close to uniform. In fact, under the constraint of starting from a uniform input with 2^n possibilities, both produce an output that is as close to uniform as possible. A necessary and sufficient requirement for that is the maximum and minimum number of inputs that maps to any given output differs by at most one, which is the case for both methods.