Discrete low-discrepancy sequences

Authors Omer Angel, A. E. Holroyd, James Martin, James Propp

Publication date 6 October 2009

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite abelian groups (20K01) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Abstract: 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.

This page was built for publication: Discrete low-discrepancy sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6215763)