patternMinor
Fast sampling from discrete space
Viewed 0 times
fastspacesamplingdiscretefrom
Problem
Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=x_i) =p_i$.
More specifically, I assume $A$ can generate a uniformly distributed real number in the interval $[0,1]$ in a constant time, and try to characterize the distributions $P$ which can be sampled in $o(|X|)$ time.
For example, if $P$ is the uniform distribution, I can assign to each element of $X$ a string from $\{0,1\}^{\log(n)}$, then sample each bit uniformly (toss of a coin) and independently, which means I can sample in $O(\log(n))$ time. Are there distributions such that any algorithm requires $\Omega(|X|)$ time? Are there known results in this direction?
More specifically, I assume $A$ can generate a uniformly distributed real number in the interval $[0,1]$ in a constant time, and try to characterize the distributions $P$ which can be sampled in $o(|X|)$ time.
For example, if $P$ is the uniform distribution, I can assign to each element of $X$ a string from $\{0,1\}^{\log(n)}$, then sample each bit uniformly (toss of a coin) and independently, which means I can sample in $O(\log(n))$ time. Are there distributions such that any algorithm requires $\Omega(|X|)$ time? Are there known results in this direction?
Solution
The Alias Method provides a means of sampling from a discrete distribution in $O(1)$ time, with $O(n)$ space and $O(n)$ pre-processing time.
Context
StackExchange Computer Science Q#96134, answer score: 2
Revisions (0)
No revisions yet.