Name
Abstract | ||
|---|---|---|
We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities p1, …, pn. We consider the problem of sampling a subset, which includes the ith event independently with probability pi, and the problem of sampling from the distribution, where the ith event has a probability proportional to pi. For both problems, we present on two different classes of inputs --- sorted and general probabilities --- efficient preprocessing algorithms that allow for asymptotically optimal querying, and prove almost matching lower bounds for their complexity. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00453-016-0205-0 | Algorithmica |
Keywords | Field | DocType |
Sampling algorithm,Subset sampling,Distribution,Proportional sampling,Data structures | Slice sampling,Sampling distribution,Discrete mathematics,Combinatorics,Importance sampling,Poisson sampling,Probability distribution,Sampling (statistics),Pseudo-random number sampling,Marginal distribution,Mathematics | Conference |
Volume | Issue | ISSN |
79 | 2 | 0178-4617 |
Citations | PageRank | References |
2 | 0.38 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Karl Bringmann | 1 | 427 | 30.13 |
| Konstantinos Panagiotou | 2 | 290 | 27.80 |