Simulating a coin with irrational bias using rational arithmetic

An arXived paper by Luis Mendo adresses the issue of simulating coins with irrational probabilities from a fair coin, somehow connected with one of the latest riddles. Where I realised only irrational coins could be simulated in a fixed and finite number of throws! The setting of the paper is however similar to the one of a Bernoulli factory in that an unlimited number of coins can be generated (but it relies on a  fair coin). And the starting point is a series representation of the irrational ζ as a sum of positive and rational terms. As well as an earlier paper by the Warwick team of Łatuszyński et al. (2011). The solution is somewhat anticlimactic in that the successive draws of the fair coin lead to a sequence of intervals with length divided by 2 at each step. And stopping when a certain condition is met, requiring some knowledge on the tail error of the series. The paper shows further that the number of inputs used by its algorithm has an exponential tail. The examples provided therein are Euler’s constant

\gamma =\frac{1}{2} + \sum_{i=1}^\infty \frac{B(i)}{2i(2i+1)(2i+2)}

where B(j) is the number of binary digits of j, and π/4 which can be written as an alternating series. An idle question that came to me while reading this paper is the influence of the series chosen to represent the irrational ζ as it seems that a faster decrease in the series should lead to fewer terms being used. However, the number of iterations is a geometric random variable with parameter 1/2, therefore the choice of the series curiously does not matter.

7 Responses to “Simulating a coin with irrational bias using rational arithmetic”

  1. Andrew Gelman Says:

    X, Luis:
    We discussed this in our paper, I think, or else we discussed it elsewhere. If Pr(heads) depends on how you start the coin, then the probability is not just a property of the coin, it’s also a property of its initial condition. Hence it does not make sense to refer to it as an “unfair coin.”

  2. Thanks for the review. Although a faster-converging series does not help in reducing the average number of inputs, it does reduces the average number of required series terms. Actually, there would be little margin to reduce the average number of inputs, because that number cannot be lower than 2 (except for the special case that the target probability is dyadic) [9, theorem 6]. The presented algorithm guarantees that number to be between 2 and 3 (in practice it is close to 2).

  3. Andrew Gelman Says:

    You can load a die but you can’t bias a coin: http://www.stat.columbia.edu/~gelman/research/published/diceRev2.pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.