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

[probsys]

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

[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.