5
$\begingroup$

This is a basic question that I can't answer (it's not a homework assignment). A reference would be perfectly acceptable.

Consider a $[0,k]$ valued random variable X distributed binomially so that:

$$\text{Pr}[X=i]=\binom{k}{i}/2^k$$

It's clear that we can sample from $X$ in poly($k$) time using $k$ random bits. The basic question is if it's possible to do better if I'm only interested in approximate sampling.

For example, if I'm interested in sampling from any $Y$ so that $|X-Y|<\epsilon$ (in statistical distance), can I do this in randomized time poly($1/\epsilon$) (i.e., with $1/\epsilon$ random bits)?

$\endgroup$
6
$\begingroup$

To exactly sample from the binomial distribution on $\{0,1,\cdots,n\}$ requires $n$ random bits. However, we can approximately sample with $O(\log(n/\varepsilon))$ bits, where $\varepsilon$ is the statistical distance from binomial we allow.

Let $$a_0=0, ~~~~a_{k+1}=a_k+{n \choose k} \cdot 2^{-n} ~~~~(k \in \{0,1,\cdots,n\}).$$ We can sample exactly from the binomial distribution by sampling $x \in [0,1)$ uniformly and then picking $k$ such that $x \in [a_k,a_{k+1})$. The probability of picking any given $k$ is thus $$\mathrm{Pr}_x[k]=\mathrm{Pr}_x[x\in[a_k,a_{k+1})] = a_{k+1}-a_k = {n \choose k} \cdot 2^{-n}.$$

We will sample approximately by sampling $\tilde{x} \in \{ 0, 1/m, 2/m, \cdots, (m-1)/m \}$ uniformly and then picking $k$ such that $\tilde{x} \in [a_k,a_{k+1})$. This requires $O(\log m)$ bits of randomness. We have $$\mathrm{Pr}_\tilde{x}[k]=\mathrm{Pr}_\tilde{x}[\tilde{x}\in[a_k,a_{k+1})]=\frac{\lceil m a_{k+1} \rceil - \lceil m a_k \rceil}{m}=a_{k+1}-a_k \pm \frac{1}{m} =\mathrm{Pr}_x[k] \pm \frac{1}{m}.$$ So the difference between the probability of $k$ under exact sampling and under approximate sampling is at most $1/m$. Summing over all $k$, we have that the statistical distance is at most $(n+1)/m$. Setting $m=O(n/\varepsilon)$ ensures that the approximate sampling is $\varepsilon$ statistically close to binomial.

$\endgroup$
  • $\begingroup$ Thanks! This achieves the right amount of randomness, but is it clear how to implement the "picking the k such that $\tilde{x}\in[a_k,a_{k+1}]$ step" in poly($\log (n/\epsilon)$) time? $\endgroup$ – user22935 May 15 '14 at 6:17
  • $\begingroup$ Unfortunately, I think it would take poly(n) time to evaluate this. Maybe, if we approximate the binomial coefficients, rather than compute them exactly, it can be made more efficient. I'll think about it. $\endgroup$ – Thomas supports Monica May 15 '14 at 6:29
  • $\begingroup$ But if you preprocess the lookups (since $\tilde{x}$ is drawn from a fixed set) you can find the $k$ in essentially constant time via hashing. Or at least it shouldn't take more than $\log m$ time. $\endgroup$ – Suresh Venkat May 15 '14 at 6:59
2
$\begingroup$

Using the alias method you can make do with $\lceil \log_2 (k+1) \rceil + 2$ bits on average. In preprocessing you prepare a table of length $k+1$ in which each cell is partitioned into two parts by some threshold $\theta_i \in [0,1]$, and the "lower" and "upper" parts are labelled by outcomes. To sample, you first choose a uniformly random cell $i$, and then you sample (mentally) a uniformly random real in $[0,1]$, and compare it to the threshold, choosing either the lower label or the upper label accordingly. If you sample the real bit by bit, then at every point you have a chance of 1/2 to have determined whether you're above or below the threshold, so the total number of bits used is $\lceil \log_2 (k+1) \rceil + G(1/2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.