Dynamic sampling from a discrete probability distribution with a known distribution of rates

DOI10.1007/S00180-021-01159-3zbMATH Open1505.62113arXiv1802.02379OpenAlexW3205026904MaRDI QIDQ2155015FDOQ2155015

Hans L. Bodlaender, Federico D'Ambrosio, G. T. Barkema

Publication date: 15 July 2022

Published in: Computational Statistics (Search for Journal in Brave)

Abstract: In this paper, we consider several efficient data structures for the problem of sampling from a dynamically changing discrete probability distribution, where some prior information is known on the distribution of the rates, in particular the maximum and minimum rate, and where the number of possible outcomes N is large. We consider three basic data structures, the Acceptance-Rejection method, the Complete Binary Tree and the Alias method. These can be used as building blocks in a multi-level data structure, where at each of the levels, one of the basic data structures can be used, with the top level selecting a group of events, and the bottom level selecting an element from a group. Depending on assumptions on the distribution of the rates of outcomes, different combinations of the basic structures can be used. We prove that for particular data structures the expected time of sampling and update is constant when the rate distribution follows certain conditions. We show that for any distribution, combining a tree structure with the Acceptance-Rejection method, we have an expected time of sampling and update of $Oleft(loglog{r}_{max}/r_{min}ight)$ is possible, where $r_{max}$ is the maximum rate and $r_{min}$ the minimum rate. We also discuss an implementation of a Two Levels Acceptance-Rejection data structure, that allows expected constant time for sampling, and amortized constant time for updates, assuming that $r_{max}$ and $r_{min}$ are known and the number of events is sufficiently large. We also present an experimental verification, highlighting the limits given by the constraints of a real-life setting.

Full work available at URL: https://arxiv.org/abs/1802.02379

Recommendations

• Efficient sampling methods for discrete distributions
• Maintaining discrete probability distributions optimally
• Succinct sampling from discrete distributions
• Efficient sampling methods for discrete distributions
• Dynamic generation of discrete random variates

zbMATH Keywords

dynamic samplingconstant time algorithmdiscrete random variates

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08)

Cites Work

• Dynamic generation of discrete random variates
• Introduction to algorithms
• Title not available (Why is that?)
• An Efficient Method for Generating Discrete Random Variables with General Distributions
• Maintaining discrete probability distributions optimally
• An Efficient Method for Weighted Sampling without Replacement
• Fast algorithms for generating discrete random variates with changing distributions
• Generating discrete random variables in a computer

Cited In (6)

• Sampling at a random time with a heavy-tailed distribution
• Title not available (Why is that?)
• Title not available (Why is that?)
• Continuous and discrete dynamical sampling
• Succinct sampling from discrete distributions
• Dynamic generation of discrete random variates

This page was built for publication: Dynamic sampling from a discrete probability distribution with a known distribution of rates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155015)