假设我们要从以下分布中生成平局:
但是有两个限制:
(a) 抽签必须基于外部事件。
(b) 与 (a) 相关,抽签必须可由第三方核实。换句话说,第三方应该能够验证我的平局实际上是(比如说)。
Qn 1:可以设计这样的系统吗?如果可以,如何设计?
问题 2:系统能否扩展到具有超过 2 个可能结果的离散变量(如掷骰子)?
Qn 3:同样,它可以扩展到连续变量(例如,正态)吗?
假设我们要从以下分布中生成平局:
但是有两个限制:
(a) 抽签必须基于外部事件。
(b) 与 (a) 相关,抽签必须可由第三方核实。换句话说,第三方应该能够验证我的平局实际上是(比如说)。
Qn 1:可以设计这样的系统吗?如果可以,如何设计?
问题 2:系统能否扩展到具有超过 2 个可能结果的离散变量(如掷骰子)?
Qn 3:同样,它可以扩展到连续变量(例如,正态)吗?
正如另一个可验证的随机性来源:random.org 从大气噪声中生成随机数。他们发布随机位的每日文件(大多数天);每天档案的第一个数字可能证明对您的当事人来说是可适当核实的。
2013-11-12 更新:对这些文件的访问现在受到限制,但看起来您可以通过电子邮件发送 random.org 的操作员以获得访问权限:
注意:由于带宽考虑,目前对预生成文件的访问受到限制。如果您需要访问权限,请告诉我们 (contact@random.org)。
许多国家都有定期审核的国家彩票,其结果在网上公布:例如英国国家彩票。您只需要构建一个适当的函数,将这个输出空间映射到您想要的输出。
连续分布会更棘手,但您可以获得离散近似值:在英国的情况下= 601 304 088 个同样可能的结果,根据上下文,可以提供足够的粒度。
这让我想起了很久以前算法课上的一个问题。让外部事件是一个(最好是连续的)随机变量. 生成一个值, 取两个独立的观察值然后让是如果第一次观察大于第二个,让它成为如果第二个大于第一个,如果有平局,则重复实验。显然,如果是连续的。如果只有硬币翻转可用作生成器,则可以将看到尾巴之前的连续正面数量设为随机变量. (我相信,作业问题是如何将有偏见的硬币翻转变成无偏见的硬币翻转。作业的一部分是证明该过程将终止......)
这显然也可以扩展到离散情况,尽管在联系方面可能会遇到更多困难。如果你有可能的结果, 拿一些这样划分然后分区可能的排序观察来自进入等价类.
编辑:根据@srikant 的评论,一个可能的生成器示例:(正如@andyW 所预料的那样)让是给定来源在固定时间段内报告的给定高流动性 ETF 交易的股票数量,明确索引为. 让其中正切函数由固定标准库计算(在固定版本的 R 中,例如,在固定平台上)。对我来说是伪随机的。其他发电机如果它们相对于.
我不太明白您所说的“基于外部事件”是什么意思。但是您当然可以以远程用户可以加密验证的方式掷硬币。
考虑这个算法:
有了这个算法,没有对方的配合,任何一方都不能作弊。如果任何一方公平竞争,输出将是一个统一的随机布尔值。
(编辑)我现在理解这个问题意味着你根本没有内部的不确定性来源,所以所有的随机性都必须来自外部来源,并且算法必须是确定性的。在这种情况下,我们仍然可以使用密码学来提供帮助。
每天取《纽约时报》PDF版的SHA-256,或者道琼斯工业平均指数中所有股票的成交量和收盘价的SHA-256,按股票代码的字母顺序,或者真的是可以相互观察并且您无法影响的任何内容的安全哈希。如果您只需要一点,请使用 SHA-256 的第一位。
如果你想要一个正态分布,你可以把整个事情分成两部分(128 位,然后是 128 位)作为两个均匀偏差,并使用 Box-Muller 变换得到两个正态偏差。