Support growth of the information-maximizing binomial prior
For an integer $n \ge 1$, let $\Theta \in [0,1]$ have law $\pi$ and, given $\Theta = \theta$, let $Y \sim \operatorname{Binomial}(n, \theta)$. Write $b_{n,y}(\theta) = \binom{n}{y} \theta^y (1-\theta)^{n-y}$, with $0^0 = 1$, and $q_\pi(y) = \int b_{n,y}(\theta)\, \pi(d\theta)$, and let $$I_n(\pi) = \sum_{y=0}^{n} \int_{[0,1]} b_{n,y}(\theta) \log \frac{b_{n,y}(\theta)}{q_\pi(y)}\, \pi(d\theta)$$ be the mutual information of $\Theta$ and $Y$, with natural logarithms and terms of probability zero counted as zero. Let $\pi_n^*$ be the Borel probability law on $[0,1]$ maximizing $I_n$, and $K_n$ the number of points in its support. Favano, Baniasadi, Zieder, Barletta and Dytso proved that $\pi_n^*$ is unique and discrete, symmetric about $1/2$, with $0$ and $1$ in its support, that $K_n \le 2 + \lfloor n/2 \rfloor$, that $K_n$ is at least of order $\sqrt{n \log \log n}$, and that $\max_\pi I_n(\pi) = \tfrac12 \log \tfrac{n\pi}{2e} + o(1)$. Mattingly, Transtrum, Abbott and Machta, and Abbott and Machta, conjectured from numerical and heuristic evidence that the capacity grows like $\tfrac34 \log K_n$ for smooth parametric families; for this model, Polyanskiy and Wu note, that would give $K_n$ of order $n^{2/3}$.
Problem. Is $$\lim_{n \to \infty} \frac{\log K_n}{\log n} = \frac{2}{3},$$ that is, $K_n = n^{2/3 + o(1)}$? The statement concerns the exact maximizer at every $n$; a limiting constant for $K_n / n^{2/3}$ is not asked for.
Source: Polyanskiy and Wu (2025), §13.3, for i.i.d. Bernoulli observations, as a consequence of the universality conjecture of Mattingly, Transtrum, Abbott and Machta (2018) and Abbott and Machta (2019); stated for the exponent by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- IT — Information Theory
- Secondary
- PR, ST
- Keywords
- AIM Open Applied Problems, capacity-achieving distributions, channel capacity
References
@book{polyanskiy2025,
author = {Polyanskiy, Yury and Wu, Yihong},
title = {Information Theory: From Coding to Learning},
publisher = {Cambridge University Press},
address = {Cambridge},
year = {2025},
doi = {10.1017/9781108966351},
}
@article{mattingly2018,
author = {Mattingly, Henry H. and Transtrum, Mark K. and Abbott, Michael C. and Machta, Benjamin B.},
title = {Maximizing the information learned from finite data selects a simple model},
journal = {Proc. Natl. Acad. Sci. USA},
volume = {115},
number = {8},
year = {2018},
pages = {1760--1765},
doi = {10.1073/pnas.1715306115},
eprint = {1705.01166},
archivePrefix = {arXiv},
}
@article{abbott2019,
author = {Abbott, Michael C. and Machta, Benjamin B.},
title = {A scaling law from discrete to continuous solutions of channel capacity problems in the low-noise limit},
journal = {J. Stat. Phys.},
volume = {176},
number = {1},
year = {2019},
pages = {214--227},
doi = {10.1007/s10955-019-02296-2},
eprint = {1710.09351},
archivePrefix = {arXiv},
}
@misc{favano2026,
author = {Favano, Antonino and Baniasadi, Mohammadamin and Zieder, Ian and Barletta, Luca and Dytso, Alex},
title = {The binomial channel: on capacity, optimal inputs, and beta-binomial approximation},
year = {2026},
eprint = {2607.02683},
archivePrefix = {arXiv},
note = {Version 2},
}
@misc{aim-binomial-optimal-prior-support,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Support growth of the information-maximizing binomial prior}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/495-binomial-optimal-prior-support.md},
note = {Entry 495 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00278, "Support growth of the information-maximizing binomial prior", clopen.solutions.