# Tag Info

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}...