Include an example for finding optimal weights to reach a divergence goal

[peteroupc]

Include an example for finding the smallest set of weights (that is, the "precision" or the smallest sum of weights) that approximate a target probability distribution to a maximum tolerable divergence. Without an example, this is not exactly trivial to do because of the lack of documentation.

• Input: Target distribution; maximum divergence tolerable (e.g., 2^-64); kind of divergence; option to limit the sum of weights to a power of 2. The target distribution can be a list of ratios, but it would be preferred if it can also be a probability mass function that supports mpmath numbers (but I admit that mpmath numbers are ultimately ratios too).
• Output: Optimal probabilities in the form of integer weights.

EDIT: Clarification.

[fsaad]

@peteroupc Thanks for the ticket. If I understand correctly, the algorithm will keep increasing the precision until the optimal achievable error is below the specified maximum tolerable divergence, is that right?

[peteroupc]

Correct; precision in the sense of the sum of weights.

[fsaad]

OK, and are you interested in the least such precision that satisfies the maximum tolerable divergence? (is that what you meant by "smallest set of weights"?)

[peteroupc]

Yes that is what I mean.

[fsaad]

@peteroupc I sketched this example for you:
https://github.com/probcomp/optimal-approximate-sampling/blob/c269d6831bcedcae8ae11c5b719a8d97afe3b194/examples/maxerror.py

Let me know if it makes sense and implements the behavior your are interested. I specified the target distribution using Python floats---mpmath or Fraction instances should also fine.

[fsaad]

If you are allowing the precision to vary and are interested in an exact (zero-error) sampler, then you can consider the fast loaded dice roller, which finds zero-error and near-entropy optimal samplers for both integer and floating-point weights.

[peteroupc]

The interest here is approximating probability mass functions—

• that have non-integer powers,
• that have transcendental functions, such as the Poisson distribution or most cases of the geometric distribution, or
• that would have huge integer weights if represented exactly, such as factorials.

[peteroupc]

The example works well, so closing.