# Number of random bits necessary to approximate an arbitrary distribution

Given a discrete distribution $$X$$ and $$\varepsilon\in(0,1)$$, consider the minimal $$m\in\mathbb{N}$$ such that $$\mathbf{SD}(f(U^m),X)\leq\varepsilon$$, for some (the best, possibly inefficient) deterministic function $$f$$. Here $$\mathbf{SD}$$ represents the statistical variation distance between two distributions, and $$U^m$$ denotes a uniform sample from $$\{0,1\}^m$$. What is the best upper bound for $$m$$, in terms of $$H(X)$$ and $$\varepsilon$$?

It is not too hard to see that $$m\leq \log \left|\text{Supp}(X)\right|+\log(1/\varepsilon)$$, however, it seems plausible that a better bound exists, such as $$H(X)+\log(1/\varepsilon)$$ for the entropy function $$H$$. Yet, I was only able to show that roughly $$H(X)/\varepsilon$$ bits are sufficient.

It seems like a fundamental problem so I guess it was studied already, but I didn't find an appropriate match. Would appreciate your help.

There is no $$H(X)+\log(1/\epsilon)$$ bound. I think your $$H(X)/\varepsilon$$ bound is tight.

Example 1. Suppose $$X$$ is uniformly distributed on $$\{1,2,\dots,2^n\}$$. Then the optimal encoding has something like $$m \approx n$$ [1].

Example 2. Suppose now that $$X$$ takes the value 0 with probability $$1-\varepsilon$$, and otherwise is uniformly distributed on $$\{1,2,\dots,2^n\}$$. Then the optimal encoding has something like $$m \approx n + \lg (1/\varepsilon)$$ [2]. Also $$H(X) \approx \varepsilon n - \varepsilon \log(\epsilon)$$.

We can see that Example 2 violates the hypothetical $$H(X)+\log(1/\epsilon)$$ bound.

Also, in Example 2, $$m \approx H(x)/\varepsilon + \lg(1/\varepsilon)$$. This shows that your upper bound of something like $$H(X)/\varepsilon$$ is tight (assuming it is a correct upper bound, which I did not attempt to prove or check).

Footnote [1]: Why? Well, for each $$i$$, $$f(U^m)$$ must put non-zero probability on at most $$2^m$$ values of $$i$$. Every other $$i$$ has probability 0 under $$f(U^m)$$, incurring error $$1/2^n$$; if there are too many of such $$i$$, the total error will be too large. Therefore, the number of such $$i$$, namely $$2^n-2^m$$, must be pretty small, so we must have $$m \ge n - \text{a little}$$. A more precise estimate is something like $$m \approx n + \lg(1-\varepsilon/2)$$, but let's ignore the dependence on $$\epsilon$$ for simplicity.

Footnote [2]: Why? Again, if $$f(U^m)$$ puts probability 0 on too many values $$i$$, then the total error will be too large. So it must put probability at least $$1/2^m$$ on most of $$1,2,\dots,2^n$$, and we need $$1/2^m$$ to be close to $$\epsilon/2^n$$. I think a more precise estimate is something like $$m \approx n + \lg(1-\varepsilon/2) + \lg(1/\varepsilon)$$, but I haven't checked that.

• Thank you for your answer. In Example $2$ you can approximate $X$ within SD $\varepsilon$ by outputting $0$, but we can choose $\varepsilon'=\varepsilon/2$. So following your example I think you can simply look at $1/2,2^{-(n+1)},\dots,2^{-(n+1)}$, then $H(X)=n/2+1$, and you are allowed to miss at most $\varepsilon\cdot2^{n+1}$ elements, so you need at least $1+2^n\cdot(1-2\varepsilon)$, which may be much larger than $2^H/\varepsilon=2^{n/2+1}/\varepsilon$. Re upper bound, you can show the $2^{H/\varepsilon}$ most likely elements have pr. at least $1-\varepsilon$, then use the image bound. Jan 14 at 18:33
• @Nathan, Good point. A simple revision: let $X$ take value 0 with probability ever so slightly smaller than $1-\varepsilon$, say with probability $1-2\varepsilon$. Then you can't approximate within SD $\varepsilon$ by outputting 0. Don't you get a bigger gap by using a large probability close to $1-\varepsilon$ for 0, rather than 1/2?
– D.W.
Jan 15 at 0:40
• True, you get a bigger gap by using a larger probability, which is useful for the tightness of $H/\varepsilon+\log(1/\varepsilon)$. Jan 15 at 1:54