是否有一种可验证的方法来根据外部事件生成离散随机变量?

机器算法验证 随机变量
2022-03-25 06:09:39

假设我们要从以下分布中生成平局:

P(X=0)=0.5

P(X=1)=0.5

但是有两个限制:

(a) 抽签必须基于外部事件。

(b) 与 (a) 相关,抽签必须可由第三方核实。换句话说,第三方应该能够验证我的平局实际上是(比如说)。X=0

Qn 1:可以设计这样的系统吗?如果可以,如何设计?

问题 2:系统能否扩展到具有超过 2 个可能结果的离散变量(如掷骰子)?

Qn 3:同样,它可以扩展到连续变量(例如,正态)吗?

4个回答

正如另一个可验证的随机性来源:random.org 从大气噪声中生成随机数。他们发布随机位的每日文件(大多数天)每天档案的第一个数字可能证明对您的当事人来说是可适当核实的。


2013-11-12 更新:对这些文件的访问现在受到限制,但看起来您可以通过电子邮件发送 random.org 的操作员以获得访问权限:

注意:由于带宽考虑,目前对预生成文件的访问受到限制。如果您需要访问权限,请告诉我们 (contact@random.org)。

许多国家都有定期审核的国家彩票,其结果在网上公布:例如英国国家彩票您只需要构建一个适当的函数,将这个输出空间映射到您想要的输出。

连续分布会更棘手,但您可以获得离散近似值:在英国的情况下49C6×43= 601 304 088 个同样可能的结果,根据上下文,可以提供足够的粒度。

这让我想起了很久以前算法课上的一个问题。让外部事件是一个(最好是连续的)随机变量Y. 生成一个值X, 取两个独立的观察值Y然后让X1如果第一次观察Y大于第二个,让它成为0如果第二个大于第一个,如果有平局,则重复实验。显然,如果Y是连续的。如果只有硬币翻转可用作生成器,则可以将看到尾巴之前的连续正面数量设为随机变量Y. (我相信,作业问题是如何将有偏见的硬币翻转变成无偏见的硬币翻转。作业的一部分是证明该过程将终止......)

这显然也可以扩展到离散情况,尽管在联系方面可能会遇到更多困难。如果你有n可能的结果X, 拿一些k这样n划分k!然后分区k!可能的排序k观察来自Y进入等价类X.

编辑:根据@srikant 的评论,一个可能的生成器示例Y:(正如@andyW 所预料的那样)让Zi是给定来源在固定时间段内报告的给定高流动性 ETF 交易的股票数量,明确索引为i. Yi=tan(Zi),其中正切函数由固定标准库计算(在固定版本的 R 中,例如,在固定平台上)。Y对我来说是伪随机的。其他发电机Z如果它们相对于2π.

我不太明白您所说的“基于外部事件”是什么意思。但是您当然可以以远程用户可以加密验证的方式掷硬币。

考虑这个算法:

  1. Bob 选择一个统一随机的布尔值,TRUE 或 FALSE。他还选择了一个很大的随机数。他向 Alice 发送与数字连接的布尔值的 SHA-256 哈希。(例如,他发送“TRUE|12345678”的散列。)因为 Alice 不知道随机数并且散列是单向的,所以 Alice 不知道布尔值。
  2. 爱丽丝掷硬币并向鲍勃发送值 - TRUE 或 FALSE。
  3. Bob 揭示了随机数,从而揭示了他自己的布尔值。Alice 验证布尔值和随机数确实散列到她之前收到的值。
  4. 掷硬币的最终输出是 Alice 的布尔值和 Bob 的布尔值的异或。

有了这个算法,没有对方的配合,任何一方都不能作弊。如果任何一方公平竞争,输出将是一个统一的随机布尔值。

(编辑)我现在理解这个问题意味着你根本没有内部的不确定性来源,所以所有的随机性都必须来自外部来源,并且算法必须是确定性的。在这种情况下,我们仍然可以使用密码学来提供帮助。

每天取《纽约时报》PDF版的SHA-256,或者道琼斯工业平均指数中所有股票的成交量和收盘价的SHA-256,按股票代码的字母顺序,或者真的是可以相互观察并且您无法影响的任何内容的安全哈希。如果您只需要一点,请使用 SHA-256 的第一位。

如果你想要一个正态分布,你可以把整个事情分成两部分(128 位,然后是 128 位)作为两个均匀偏差,并使用 Box-Muller 变换得到两个正态偏差。