使用自定义参数实现随机 0 1

Question

我正在尝试解决以下问题：

我有一个函数，它以相等的概率生成 0 或 1 = 0.5，我想使用前一个函数和做同样事情的基本数学运算来实现另一个函数但给定概率 p (0<=p<=1)

这不是我的作业或 smth，我只是偶然发现它，非常感谢任何提示！

Answer 1

一个在很多情况下应该可行的简单解决方案描述如下：

将 p 解释为最低限度的有理数 a / b。如果 p 只是一个介于 0 和 1 之间的浮点数，那么 b 只是 10 的幂，零的个数与小数点后的位数一样多，而a是小数点后的数字串去掉前导零后的数。
生成长度为 ceiling(log(b - 1)) 的随机位串，其中对数的底数为 2 且 ceiling 将任何非整数向上舍入为下一个整数。通过调用提供的函数并记录答案来完成此操作。
如果不包括前导零的随机位串表示0和b - 1之间的整数，包括在内，则继续；否则，如果数字大于 b，return 到步骤 2，生成随机位串，直到你得到一个有效的位串。
如果不包括前导零的随机位串表示 0 和 a - 1 之间的整数，包括端值，则 return 0；否则 return 1.

这应该return在有限的预期时间，但无界的最坏情况时间，概率为p = a / b的数字0和概率为1的数字1 p = (b - a) / b，确切地说，鉴于 p 是一个有理数（请注意，双精度数都是有理数，如步骤中所述1).

Answer 2

这实际上与 Patrick87 提出的算法大致相同，但它一次生成一个位，并在找到答案时立即停止。它本质上与 arithmetic encoding.

有关

我已经在 Python 中实现了。

>>> # Create a function which returns 0 or 1 with equal probability.
>>> from random import random
>>> f = lambda: int(random()<0.5)

>>> # Check
>>> sum(f() for i in range(1000000))
500251
>>> # Use that to create a biased function. You can use this
>>> # either with a rational number expressed as numerator, denominator
>>> # or with a value of p between 0 and 1. Python doesn't care whether
>>> # numbers are integers but other languages might.
>>> def biased(numer, denom = 1):
...    while True:
...      numer += numer
...      if numer >= denom:
...        numer -= denom
...        if f(): return 1
...      else:
...        if f(): return 0
... 
>>> sum(biased(0,19) for i in range(1900000))
0
>>> sum(biased(1,19) for i in range(1900000))
100096
>>> sum(biased(5,19) for i in range(1900000))
500255
>>> sum(biased(18,19) for i in range(1900000))
1799988
>>> sum(biased(19,19) for i in range(1900000))
1900000

实际上，循环通过将分子的当前值加倍并与分母进行比较，一次一位地构造 numerator/denominator 的二进制表示。然后它将其与延迟生成的随机二进制分数进行比较，直到它可以确定随机分数是更大还是更小。

尽管调用基函数 f 的次数在理论上是无限的，但无论 biased 的参数如何，调用 biased 的预期次数 f 都是 2 次。（这是因为随机比特流匹配 k 二进制数字的概率是 2^-k，与二进制数字的实际值无关。）

使用自定义参数实现随机 0 1

implement random 0 1 with custom parameter

algorithm

probability