**
**

**Bringmann, Karl and Panagiotou, Konstantinos (2017): Efficient Sampling Methods for Discrete Distributions. In: Algorithmica, Vol. 79, No. 2: pp. 484-508**

**Full text not available from 'Open Access LMU'.**

## 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 p(1,)...,p(n) First, we consider the problem of sampling from the distribution where the i-th event has probability proportional to p(i). Second, we study the problem of sampling a subset which includes the i-th event independently with probability . For both problems we present on two different classes of inputs-sorted and general probabilities-efficient data structures consisting of a preprocessing and a query algorithm. Varying the allotted preprocessing time yields a trade-off between preprocessing and query time, which we prove to be asymptotically optimal everywhere.

Item Type: | Journal article |
---|---|

Faculties: | Mathematics, Computer Science and Statistics > Mathematics |

Subjects: | 500 Science > 510 Mathematics |

ISSN: | 0178-4617 |

Language: | English |

Item ID: | 53483 |

Date Deposited: | 14. Jun 2018, 09:53 |

Last Modified: | 04. Nov 2020, 13:32 |