<p>There is no <span class="math-container">$H(X)+\log(1/\epsilon)$</span> bound.  I think your <span class="math-container">$H(X)/\varepsilon$</span> bound is tight.</p>
<p>Example 1. Suppose <span class="math-container">$X$</span> is uniformly distributed on <span class="math-container">$\{1,2,\dots,2^n\}$</span>.  Then the optimal encoding has something like <span class="math-container">$m \approx n$</span> [1].</p>
<p>Example 2. Suppose now that <span class="math-container">$X$</span> takes the value 0 with probability <span class="math-container">$1-\varepsilon$</span>, and otherwise is uniformly distributed on <span class="math-container">$\{1,2,\dots,2^n\}$</span>.  Then the optimal encoding has something like <span class="math-container">$m \approx n + \lg (1/\varepsilon)$</span> [2].  Also <span class="math-container">$H(X) \approx \varepsilon n - \varepsilon \log(\epsilon)$</span>.</p>
<p>We can see that Example 2 violates the hypothetical <span class="math-container">$H(X)+\log(1/\epsilon)$</span> bound.</p>
<p>Also, in Example 2, <span class="math-container">$m \approx H(x)/\varepsilon + \lg(1/\varepsilon)$</span>.  This shows that your upper bound of something like <span class="math-container">$H(X)/\varepsilon$</span> is tight (assuming it is a correct upper bound, which I did not attempt to prove or check).</p>
<hr />
<p>Footnote [1]:   Why?  Well, for each <span class="math-container">$i$</span>, <span class="math-container">$f(U^m)$</span> must put non-zero probability on at most <span class="math-container">$2^m$</span> values of <span class="math-container">$i$</span>.  Every other <span class="math-container">$i$</span> has probability 0 under <span class="math-container">$f(U^m)$</span>, incurring error <span class="math-container">$1/2^n$</span>; if there are too many of such <span class="math-container">$i$</span>, the total error will be too large.  Therefore, the number of such <span class="math-container">$i$</span>, namely <span class="math-container">$2^n-2^m$</span>, must be pretty small, so we must have <span class="math-container">$m \ge n - \text{a little}$</span>.   A more precise estimate is something like <span class="math-container">$m \approx n + \lg(1-\varepsilon/2)$</span>, but let's ignore the dependence on <span class="math-container">$\epsilon$</span> for simplicity.</p>
<p>Footnote [2]: Why?  Again, if <span class="math-container">$f(U^m)$</span> puts probability 0 on too many values <span class="math-container">$i$</span>, then the total error will be too large.  So it must put probability at least <span class="math-container">$1/2^m$</span> on most of <span class="math-container">$1,2,\dots,2^n$</span>, and we need <span class="math-container">$1/2^m$</span> to be close to <span class="math-container">$\epsilon/2^n$</span>.  I think a more precise estimate is something like <span class="math-container">$m \approx n + \lg(1-\varepsilon/2) + \lg(1/\varepsilon)$</span>, but I haven't checked that.</p>

CC BY-SA 4.0
2024-01-14T18:33:54.230Z
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.
Nathan
CC BY-SA 4.0
2024-01-15T00:40:41.520Z
@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.
CC BY-SA 4.0
2024-01-15T01:54:06.593Z
True, you get a bigger gap by using a larger probability, which is useful for the tightness of $H/\varepsilon+\log(1/\varepsilon)$.
Nathan
CC BY-SA 4.0
2024-01-14T03:58:41.850Z
2024-01-14T03:58:41.850Z
D.W.
<p>Given a discrete distribution <span class="math-container">$X$</span> and <span class="math-container">$\varepsilon\in(0,1)$</span>, consider the minimal <span class="math-container">$m\in\mathbb{N}$</span> such that <span class="math-container">$\mathbf{SD}(f(U^m),X)\leq\varepsilon$</span>, for some (the best, possibly inefficient) deterministic function <span class="math-container">$f$</span>.  Here <span class="math-container">$\mathbf{SD}$</span> represents the statistical variation distance between two distributions, and <span class="math-container">$U^m$</span> denotes a uniform sample from <span class="math-container">$\{0,1\}^m$</span>.  What is the best upper bound for <span class="math-container">$m$</span>, in terms of <span class="math-container">$H(X)$</span> and <span class="math-container">$\varepsilon$</span>?</p>
<p>It is not too hard to see that <span class="math-container">$m\leq \log \left|\text{Supp}(X)\right|+\log(1/\varepsilon)$</span>, however, it seems plausible that a better bound exists, such as <span class="math-container">$H(X)+\log(1/\varepsilon)$</span> for the entropy function <span class="math-container">$H$</span>. Yet, I was only able to show that roughly <span class="math-container">$H(X)/\varepsilon$</span> bits are sufficient.</p>
<p>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.</p>

<pr.probability><shannon-entropy><sampling>
Number of random bits necessary to approximate an arbitrary distribution
Nathan
# Number of random bits necessary to approximate an arbitrary distribution

(Asked by: username_0 on 2024-01-13)

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.

**Tags:** pr.probability, shannon-entropy, sampling


---

## 1 answers

### Answer by username_1 on 2024-01-14. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: @username_0, 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?  
> **username_0**: True, you get a bigger gap by using a larger probability, which is useful for the tightness of $H/\varepsilon+\log(1/\varepsilon)$.  

---

