Discrete low-discrepancy sequences
Discrete low-discrepancy sequences
复制标题
离散低差异序列
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
J. Propp
中科院分区：
文献类型：
--
作者：
Omer Angel;A. Holroyd;James B. Martin;J. Propp
Holroyd 和 Propp 使用霍尔婚姻定理表明，给定有限集 S 上的概率分布 pi，S 中存在无限序列 s_1,s_2,...，使得对于 S 中的所有整数 k >= 1 和所有 s，[1,k] 中 s_i = s 中 i 的数量与 k pi(s) 最多相差 1。我们使用简单的显式算法证明了该结果的推广。该算法的一个特殊情况将 Holroyd 和 Propp 的结果扩展到无限集上的离散概率分布的情况。
Holroyd and Propp used Hall's marriage theorem to show that, given a probability distribution pi on a finite set S, there exists an infinite sequence s_1,s_2,... in S such that for all integers k >= 1 and all s in S, the number of i in [1,k] with s_i = s differs from k pi(s) by at most 1. We prove a generalization of this result using a simple explicit algorithm. A special case of this algorithm yields an extension of Holroyd and Propp's result to the case of discrete probability distributions on infinite sets.