论文标题
使用有理算术模拟具有非理性偏见的硬币
Simulating a coin with irrational bias using rational arithmetic
论文作者
论文摘要
提出了一种算法，即以参数为输入$ 1/2 $的一系列独立的Bernoulli随机变量，仅使用有理算术，模拟了一个可能具有不合理参数$τ$的Bernoulli随机变量。它需要$τ$的串联表示，并具有正值，有理条件，并且对其截断误差的有理限制为$ 0 $。所需的输入的数量具有指数界的尾巴，其平均值最多为$ 3 $。算术操作的数量具有可以根据截断误差边界的序列界定的尾巴。该算法应用于$τ$的两个特定值，包括Euler的常数，为此，获得简单的仿真算法是一个开放的问题。
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.
