Simulating a coin with irrational bias using rational arithmetic
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2020
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916546122612736 |
|---|---|
| author | Mendo, Luis |
| author_facet | Mendo, Luis |
| contents | An algorithm is presented that, taking a sequence of independent Bernoulli random variables with parameter $1/2$ as inputs and using only rational arithmetic, simulates a Bernoulli random variable with possibly irrational parameter $τ$. It requires a series representation of $τ$ with positive, rational terms, and a rational bound on its truncation error that converges to $0$. The number of required inputs has an exponentially bounded tail, and its mean is at most $3$. The number of arithmetic operations has a tail that can be bounded in terms of the sequence of truncation error bounds. The algorithm is applied to two specific values of $τ$, including Euler's constant, for which obtaining a simple simulation algorithm was an open problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2010_14901 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Simulating a coin with irrational bias using rational arithmetic Mendo, Luis Probability Computation 65C10, 65C50 An algorithm is presented that, taking a sequence of independent Bernoulli random variables with parameter $1/2$ as inputs and using only rational arithmetic, simulates a Bernoulli random variable with possibly irrational parameter $τ$. It requires a series representation of $τ$ with positive, rational terms, and a rational bound on its truncation error that converges to $0$. The number of required inputs has an exponentially bounded tail, and its mean is at most $3$. The number of arithmetic operations has a tail that can be bounded in terms of the sequence of truncation error bounds. The algorithm is applied to two specific values of $τ$, including Euler's constant, for which obtaining a simple simulation algorithm was an open problem. |
| title | Simulating a coin with irrational bias using rational arithmetic |
| topic | Probability Computation 65C10, 65C50 |
| url | https://arxiv.org/abs/2010.14901 |