<p>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.</p>

<p>Let $$a_0=0, ~~~~a_{k+1}=a_k+{n \choose k} \cdot 2^{-n} ~~~~(k \in \{0,1,\cdots,n\}).$$ We can sample <i>exactly</i> 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}.$$</p>

<p>We will sample <i>approximately</i> 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.</p>

CC BY-SA 3.0
2014-05-15T06:17:58.217Z
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?
user22935
CC BY-SA 3.0
2014-05-15T06:29:09.117Z
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.
Thomas Steinke
CC BY-SA 3.0
2014-05-15T06:59:51.090Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-05-15T03:55:42.457Z
2014-05-15T03:55:42.457Z
Thomas Steinke
<p>Using the <a href="https://en.wikipedia.org/wiki/Alias_method" rel="nofollow">alias method</a> you can make do with $\lceil \log_2 (k+1) \rceil + 2$ bits <em>on average</em>. 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)$.</p>

CC BY-SA 3.0
2014-05-20T16:07:05.663Z
2014-05-20T16:07:05.663Z
Yuval Filmus
<p>This is a basic question that I can't answer (it's not a homework assignment).  A reference would be perfectly acceptable.</p>

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

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

<p>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. </p>

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

<probabilistic-computation>
Sampling from the binomial distribution with limited randomness and time
user22935
# Sampling from the binomial distribution with limited randomness and time

(Asked by: username_0 on 2014-05-15)

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)?

**Tags:** probabilistic-computation

---

## 2 answers

### Answer by username_1 on 2014-05-15. Score: 6

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_2**: 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.  

---

### Answer by username_3 on 2014-05-20. Score: 2

Using the [alias method](https://en.wikipedia.org/wiki/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)$.


---

