Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Low Discrepancy Sequences
Probability Distribution
Random Sequence
Subscribe
Academic
Publications
Discrete lowdiscrepancy sequences
Discrete lowdiscrepancy sequences,Omer Angel,Alexander E. Holroyd,James B. Martin,James Propp
Edit
Discrete lowdiscrepancy sequences
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Omer Angel
,
Alexander E. Holroyd
,
James B. Martin
,
James 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.
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.
(
arxiv.org
)
(
www.math.ubc.ca
)
Citation Context
(1)
...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. Holroyd
,
et al.
Rotor Walks and Markov Chains
References
(15)
Deterministic random walks on regular trees
(
Citations: 10
)
Joshua N. Cooper
,
Benjamin Doerr
,
Tobias Friedrich
,
Joel Spencer
Journal:
Computing Research Repository  CORR
, vol. abs/1006.1, pp. 766772, 2008
Deterministic random walks on the integers
(
Citations: 19
)
Joshua Cooper
,
Benjamin Doerr
,
Joel H. Spencer
,
Gábor Tardos
Journal:
European Journal of Combinatorics  EJC
, vol. 28, no. 8, pp. 20722090, 2007
Simulating a Random Walk with Constant Error
(
Citations: 37
)
Joshua N. Cooper
,
Joel Spencer
Journal:
Combinatorics, Probability & Computing  CPC
, vol. 15, no. 6, pp. 815822, 2006
Deterministic Random Walks on the TwoDimensional Grid
(
Citations: 15
)
Benjamin Doerr
,
Tobias Friedrich
Journal:
Combinatorics, Probability & Computing  CPC
, vol. 18, no. 12, pp. 123144, 2009
The rotorrouter model on regular trees
(
Citations: 10
)
Itamar Landau
,
Lionel Levine
Journal:
Journal of Combinatorial Theory  JCT
, vol. 116, no. 2, pp. 421433, 2009
Sort by:
Citations
(1)
Rotor Walks and Markov Chains
(
Citations: 5
)
Alexander E. Holroyd
,
James Propp
Published in 2009.