search

giuliomorina / LinearBF

0 stars 0 forks source link

Some comments on Bernoulli Factories #1

Closed peteroupc closed 1 year ago

peteroupc commented 3 years ago

I have some comments on this GitHub repository.

  1. I should note that multiplying a polynomial's Bernstein coefficients by a constant multiplies the polynomial itself by that constant. Thus, the Nacu--Peres envelopes can be extended to general linear functions as suggested in the remark after that paper's Theorem 1.

  2. An intriguing suggestion from Thomas and Blanchet (2012) is to use multiple pairs of polynomial sequences that converge to a factory function f(λ), where each pair is optimized for particular ranges of λ: first flip the input coin several times to get a rough estimate of λ, then choose the pair that's optimized for the estimated λ, and run one of the algorithms for general factory functions on that pair. Unfortunately, the paper uses an approach that requires computing an intersection of a curve with an approximating polynomial, which gets very inefficient as the polynomial's degree gets large. Thus, what I would like to see is formulas to compute sequences of this kind more efficiently, such as a formula akin to those given in a Stack Exchange question. (This suggestion applies not just to linear functions, but to any factory function, particularly functions that are not C2 continuous.)

  3. For the benefit of those with no access to the dissertation, consider describing your improved polynomial envelopes for the Flegal--Herbei curve, which is not yet explained in the vignette for this package.

giuliomorina commented 3 years ago

Thanks a lot for the comments and feedback!

  1. The package only provides an implementation that makes use of the Nacu-Peres envelops for the function min(2p,1-eps). You are correct in saying that it is possible to adapt the proof by Nacu-Peres to derive envelopes for general linear functions min(Cp,1-eps) (as they point out in their remark), although I do not think it is as straightforward as multiplying Bernstein's polynomials by a constant. One would probably have to calculate all the constants involved in the algorithm as a function of C, which may prove not an easy task. It is arguably easier to implement the Bernoulli Factory for Cp they propose in Proposition 15, although this version is not available in the package either and is significantly less efficient than the algorithm proposed by Huber.
  2. Thanks for pointing this out. Thomas and Blanchet (2012) do indeed improve on the algorithm proposed by Flegal and Herbei (2012) and admittedly their Cascade Bernoulli Factory is not implemented in the package. The idea of estimating the true value of λ and then optimizing the algorithm accordingly is fascinating, although this would clearly only be applicable if the value of λ is fixed and does not change with different runs of the algorithm. I would also love to see generic formulas to compute such Bernstein's kind of sequences, but I do believe it is an impossible task for generic functions and extra hypothesis must be made, e.g. for the function to be Lipschitz or C2 continuous (Proposition 10 of Nacu-Peres).
  3. I am sorry about this, the package is indeed thought of as a companion to the dissertation. The thesis is currently on the brink of getting submitted and it will be freely available online in the coming months. You should be able to find it at http://wrap.warwick.ac.uk/index.html.
peteroupc commented 3 years ago

Thanks a lot for the comments and feedback!

  1. The package only provides an implementation that makes use of the Nacu-Peres envelops for the function min(2p,1-eps). You are correct in saying that it is possible to adapt the proof by Nacu-Peres to derive envelopes for general linear functions min(Cp,1-eps) (as they point out in their remark), although I do not think it is as straightforward as multiplying Bernstein's polynomials by a constant. One would probably have to calculate all the constants involved in the algorithm as a function of C, which may prove not an easy task. It is arguably easier to implement the Bernoulli Factory for Cp they propose in Proposition 15, although this version is not available in the package either and is significantly less efficient than the algorithm proposed by Huber.

In fact I have come up with an algorithm of my own to simulate min(λ, 1/2), but it's probably not as efficient as the Huber linear algorithms either, since it has a non-negligible chance of building polynomials of extremely high degree (see this section beginning with "My own algorithm...").

[2.] I would also love to see generic formulas to compute such Bernstein's kind of sequences, but I do believe it is an impossible task for generic functions and extra hypothesis must be made, e.g. for the function to be Lipschitz or C2 continuous (Proposition 10 of Nacu-Peres).

Indeed; I was thinking of specific classes of factory functions (rather than all factory functions in general), such as functions of the form min(λ, c); piecewise linear functions; piecewise linear functions with only one discontinuity; unimodal functions; symmetric unimodal functions; monotonic functions; convex functions; concave functions; polynomials; C2 functions belonging to one of the above classes; etc.