6
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Nathan
    Jan 14 at 18:33
  • $\begingroup$ @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? $\endgroup$
    – D.W.
    Jan 15 at 0:40
  • $\begingroup$ True, you get a bigger gap by using a larger probability, which is useful for the tightness of $H/\varepsilon+\log(1/\varepsilon)$. $\endgroup$
    – Nathan
    Jan 15 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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