Sampling from the binomial distribution with limited randomness and time 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|&lt;\epsilon$ (in statistical distance), can I do this in randomized time poly($1/\epsilon$) (i.e., with $1/\epsilon$ random bits)?
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.