  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
$O\left(\log\log{r_{max}}/{r_{min}}\right)$ 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.
