# What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)

Consider a distribution $$\mathcal D$$ over the reals, a real parameter $$H\in\mathbb R^+$$, and an integer parameter $$k\in\mathbb N$$. The Entropy-Constrained Quantization problem asks what is the best set of quantization levels $$Q\subset \mathbb R$$, with $$|Q|\le k$$, that minimizes the expected squared distance to the closest level, under an entropy constraint $$H$$.

That is, if for all $$q\in Q$$ we denote the probability mass closest to it by $$p_q$$, then the entropy of the quantization levels set $$H_Q=-\sum_{q\in Q}p_q\log_2 p_q$$ must satisfy $$H_Q\le H$$, and the goal is to find $$\arg\min_{|Q|\le k\\H_Q\le H} \mathbb E_{X\sim \mathcal D}[\min\{(X-q)^2\mid q\in Q\}].$$

The motivation comes from encoding long vectors whose entries are i.i.d. from $$\mathcal D$$ and compressing them before sending (or storing) them. The above paper gives an algorithm for approximating the optimal quantization level set.

For example, if $$\mathcal D=\mathcal N(0,1)$$ is the normal distribution and $$k=2, H= 1$$, the optimal solution is $$Q=\{-\sqrt{2/\pi},\sqrt{2/\pi}\}$$ (as the mean of the half normal distribution is $$\sqrt{2/\pi}$$).

The expected squared error, in this case, is the variance of the half-normal, i.e.,

$$\min_{|Q|\le 2\\H_Q\le 1} \mathbb E_{X\sim \mathcal N(0,1)}[\min\{(X-q)^2\mid q\in Q\}] = \mathbb E_{X\sim \mathcal N(0,1)}\left[\min\left\{(X-q)^2\mid q\in \left\{-\sqrt{2/\pi},\sqrt{2/\pi}\right\}\right\}\right] = 1-2/\pi .$$

I am interested in distributions that are not "well compressible".

Specifically, suppose that we know that $$\mathcal D$$ has a variance of $$1$$.

What is $$\arg\max_{\mathcal D\in\Delta(\mathbb R)}\min_{|Q|\le k\\H_Q\le H} \mathbb E_{X\sim\mathcal D}[\min\{(X-q)^2\mid q\in Q\}]$$ as a function of $$k$$ and $$H$$?

If it makes things simpler, we can remove the cardinality constraint (and the parameter $$k$$).

Alternatively, assume that we have $$k=2, H=1$$. What would be the least compressible distribution with two quantization levels (and no non-trivial entropy constraint)?