Discrete low-discrepancy sequences

Discrete low-discrepancy sequences,Omer Angel,Alexander E. Holroyd,James B. Martin,James Propp

Discrete low-discrepancy sequences   (Citations: 1)
BibTex | RIS | RefWorks Download
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.
Published in 2009.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Proposition 11 can in fact be extended to the case of inflnite probability vectors [2], and Theorem 12 carries over straightforwardly to this case...
    • ...(For an alternative proof of Proposition 11 that applies also to inflnite probability vectors, see [2].)...

    Alexander E. Holroydet al. Rotor Walks and Markov Chains

Sort by: