Name
Abstract | ||
|---|---|---|
Consider a distribution as an abstract data type that represents a probability distribution f on a finite set and supports a generate operation, which returns a random value distributed according to f and independent of the values returned by previous calls. We study the implementation of dynamic distributions, which additionally support changes to the probability distribution through update operations, and show how to realize distributions on {1,..., n} with constant expected generate time, constant update time, O(n) space, and O(n) initialization time. We also consider generalized distributions, whose values need not sum to 1, and obtain similar results. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/3-540-56939-1_77 | international colloquium on automata, languages and programming |
Keywords | DocType | ISBN |
maintaining discrete probability distributions | Conference | 3-540-56939-1 |
Citations | PageRank | References |
9 | 1.01 | 5 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Torben Hagerup | 1 | 1208 | 123.57 |
| Kurt Mehlhorn | 2 | 5314 | 853.36 |
| J. Ian Munro | 3 | 3010 | 462.97 |
| andrzej lingas | 4 | 9 | 1.01 |
| r karlsson | 5 | 9 | 1.01 |
| Svante Carlsson | 6 | 764 | 90.17 |