Universal tests for nonuniform distributions
Universal tests for nonuniform distributions
复制标题
非均匀分布的通用检验
DOI：
10.1007/bf00198461
复制
发表时间：
1993
影响因子：
3
通讯作者：
A. Shamir
中科院分区：
文献类型：
--
作者：
A. D. Schrift;A. Shamir
由Blum和Micali介绍的下一个比特测试被Yao证明是对无偏独立比特源的通用测试。本文的目的是为测试输出分布不一定均匀的源提供一种严格的方法。我们首先证明了下一个比特测试的自然扩展，即使在最简单的有偏独立比特的情况下，也不再是普遍的：我们构建了一个有偏比特的源，其比特显然是依赖的，但这些比特中没有一个可以预测成功的概率大于偏差。为了克服这一困难，我们为随机性来源的任意模型（可能不完美）开发了新的通用测试。这些新工具有助于对随机性来源的理论和实践研究。
The next bit test as introduced by Blum and Micali was shown by Yao to be a universal test for sources of unbiased independent bits. The aim of this paper is to provide a rigorous methodology for testing sources whose output distributions are not necessarily uniform. We first show that the natural extension of the next bit test, even in the simplest case of biased independent bits, is no longer universal: we construct a source of biased bits, whose bits are obviously dependent and yet none of these bits can be predicted with probability of success greater than the bias. To overcome this difficulty, we develop new universal tests for arbitrary models of (potentially imperfect) sources of randomness. These new tools contribute to the theoretical as well as practical study of sources of randomness.