patternMinor
Complexity of generating non-uniform random variates
Viewed 0 times
randomnonuniformgeneratingvariatescomplexity
Problem
What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) hypergeometric variates in (expected) constant time (i.e. independent of the distribution parameters)?
There is quite a bunch of literature; however, it’s hard to understand a lot of the papers. Moreover, I found some statements that seem contradictory to me (probably due to wrong understanding).
For example, Stadlober (or similar here) mentions a "generalization [of the ratio-of-uniforms approach] to any unimodal discrete distribution". The ratio-of-uniforms approach has been called uniformly fast, which is a synonym for constant time, I suppose (?). That would mean that we can generate random variates for each discrete distribution in (expected) constant time.
However, in another paper, I found the following theorem: On a RAM with word size $w$, any algorithm sampling a geometric random variate $Geo(p)$ with parameter $p \in (0,1)$ needs at least expected runtime $\Omega(1 + \log(1/p)/w)$.
Apparently, this means that it is not possible to generate negative binomial variates in time independent of the distribution parameters.
There is quite a bunch of literature; however, it’s hard to understand a lot of the papers. Moreover, I found some statements that seem contradictory to me (probably due to wrong understanding).
For example, Stadlober (or similar here) mentions a "generalization [of the ratio-of-uniforms approach] to any unimodal discrete distribution". The ratio-of-uniforms approach has been called uniformly fast, which is a synonym for constant time, I suppose (?). That would mean that we can generate random variates for each discrete distribution in (expected) constant time.
However, in another paper, I found the following theorem: On a RAM with word size $w$, any algorithm sampling a geometric random variate $Geo(p)$ with parameter $p \in (0,1)$ needs at least expected runtime $\Omega(1 + \log(1/p)/w)$.
Apparently, this means that it is not possible to generate negative binomial variates in time independent of the distribution parameters.
Solution
The binomial, negative binomial, and hypergeometric distributions are discrete distributions. Knuth and Yao (1976) gave complexity results for discrete distributions in general. Given a stream of i.i.d. unbiased random bits, any algorithm that samples from a discrete distribution will require at least—$$b = -\sum_{x\in\Omega} \mathbb{P}(X=x)*\log_2(\mathbb{P}(X=x))$$random bits on average to sample a variate $X$ from that distribution (where $\Omega$ is the distribution's support), and they gave an algorithm that comes within 2 bits of this lower bound (and showed that coming within 2 bits is the best possible for any algorithm).
The case of continuous distributions such as the normal distribution is more complicated, but Devroye and Gravel gave complexity results for sampling a continuous variate to a desired accuracy, given a stream of i.i.d. unbiased random bits, using Wasserstein distance as the accuracy metric.
I also want to note one more thing. If the distribution of $X$ has a continuous and bounded quantile function (inverse cumulative distribution function) $F^{-1}$, I suspect that the bit complexity of sampling $X$ also depends on the modulus of continuity of $F^{-1}$, call it $\omega(h)$. In this sense, Lipschitz continuous quantile functions (where $\omega(h) = O(h)$) are the simplest cases of such functions and in that case it's simple to describe an algorithm to sample $X$ to a desired accuracy. For such functions, the algorithm uses—$$ceil(\ln(\max(1, L))-\ln(\epsilon))/\ln(\beta))$$random digits, where $L$ is the Lipschitz constant, $\epsilon$ is the desired accuracy, and $\beta$ is the digit base (such as 2 for binary). I suspect that with other moduli of continuity, the complexity will be as follows: $$ceil(-\ln(\omega^{-1}(\epsilon))/\ln(\beta)).$$
REFERENCES:
The case of continuous distributions such as the normal distribution is more complicated, but Devroye and Gravel gave complexity results for sampling a continuous variate to a desired accuracy, given a stream of i.i.d. unbiased random bits, using Wasserstein distance as the accuracy metric.
I also want to note one more thing. If the distribution of $X$ has a continuous and bounded quantile function (inverse cumulative distribution function) $F^{-1}$, I suspect that the bit complexity of sampling $X$ also depends on the modulus of continuity of $F^{-1}$, call it $\omega(h)$. In this sense, Lipschitz continuous quantile functions (where $\omega(h) = O(h)$) are the simplest cases of such functions and in that case it's simple to describe an algorithm to sample $X$ to a desired accuracy. For such functions, the algorithm uses—$$ceil(\ln(\max(1, L))-\ln(\epsilon))/\ln(\beta))$$random digits, where $L$ is the Lipschitz constant, $\epsilon$ is the desired accuracy, and $\beta$ is the digit base (such as 2 for binary). I suspect that with other moduli of continuity, the complexity will be as follows: $$ceil(-\ln(\omega^{-1}(\epsilon))/\ln(\beta)).$$
REFERENCES:
- Knuth, Donald E. And Andrew Chi-Chih Yao. "The complexity of nonuniform random number generation", in Algorithms and Complexity: New Directions and Recent Results, 1976.
- Devroye, L., Gravel, C., "Random variate generation using only finitely many unbiased, independently and identically distributed random bits", arXiv:1502.02539v6 [cs.IT], 2020.
Context
StackExchange Computer Science Q#103041, answer score: 4
Revisions (0)
No revisions yet.