Let P be a distribution on a finite alphabet of size k, let hatP_n,k be its empirical distribution from n independent samples, and let D(hatP_n,k | P) denote the relative entropy. For epsilon>0, Noncentral concentration conjecture. P( D(hatP_n,k | P) ≥ epsilon ) ≤ ( 1 + frack-1n)^n 2e^-n epsilon. This conjectured bound is motivated by the behavior of the mean relative entropy and is stated as non-trivial to prove or disprove for general n and k. It would imply a threshold of order k/n when k=o(n), matching the known lower-bound order.

Noncentral concentration conjecture for empirical relative entropy

About 8 years old · traced to 2018

Let $P$ be a distribution on a finite alphabet of size $k$ , let $\hat{P}_{n,k}$ be its empirical distribution from $n$ independent samples, and let $D(\hat{P}_{n,k} \\| P)$ denote the relative entropy. For $\epsilon>0$ , Noncentral concentration conjecture.

\mathbb{P}\left( D(\hat{P}_{n,k} \\| P) \geq \epsilon \right) \leq \left( 1 + \frac{k-1}{n}\right)^n 2e^{-n\epsilon}.

This conjectured bound is motivated by the behavior of the mean relative entropy and is stated as non-trivial to prove or disprove for general $n$ and $k$ . It would imply a threshold of order $k/n$ when $k=o(n)$ , matching the known lower-bound order.

References

Primary source

Jay Mardia, Jiantao Jiao, Ervin Tánczos, Robert D. Nowak and Tsachy Weissman, “Concentration Inequalities for the Empirical Distribution”, arXiv:1809.06522 (2019).

concentration-inequalities empirical-distributions relative-entropy

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-written asymptotic argument claims the conjecture is false for a fixed five-symbol uniform distribution, but the disproof has not been independently verified.

Mardia, Jiao, Tánczos, Nowak, and Weissman stated the noncentral concentration conjecture in 2018, motivated by the mean relative entropy and its expected threshold when $k=o(n)$ .

Known results

Mardia et al. (2018) established improved method-of-types concentration bounds, but left the conjecture open for general $n$ and $k$ .
Bhatt and Pensia (2019) obtained a different moment-generating-function bound, yielding exponential decay for $\epsilon>(k-1)/n$ .
Mardia et al. (2022) proved a gamma-type centered moment-generating-function bound and concentration around $\mathbb{E}D(\hat P\|P)$ , settling a related centered conjecture rather than this noncentral one.

Posted attempt

A reader-written attempt claims a complete disproof: for $k=5$ and uniform $P$ , taking $\epsilon_n=162/n$ gives an asymptotic tail $163e^{-162}$ , exceeding the conjectured bound’s limit $2e^4e^{-162}$ . It also claims analogous failures for every odd $k\geq5$ . This attempt has not been independently verified.

Current status (as of August 2026): The exact conjecture has a posted but unverified counterexample claim; no verified proof or disproof is recorded, so the mathematical question remains open.

Sources

CounterexampleThis solution needs a summarySee full solutionHide full solution

The proposed inequality is false, even for a fixed five-symbol uniform distribution.

The exact conjectured bound is

\Pr\!\left(D(\widehat P_{n,k}\Vert P)\ge\varepsilon\right) \le 2\left(1+\frac{k-1}{n}\right)^n e^{-n\varepsilon}.

Take $k=5$ , $P=(1/5,1/5,1/5,1/5,1/5)$ , and $\varepsilon_n=162/n>0$ . The multinomial central limit theorem and Taylor expansion of relative entropy give

2nD(\widehat P_{n,5}\Vert P)\Longrightarrow\chi^2_4.

Indeed, writing $N_i$ for the cell counts,

2nD(\widehat P_{n,5}\Vert P) =\sum_{i=1}^5\frac{(N_i-n/5)^2}{n/5}+o_{\Pr}(1),

and the limiting normalized count vector is Gaussian with covariance $I_5-\frac15\mathbf1\mathbf1^{\mathsf T}$ , the orthogonal projection onto a four-dimensional subspace.

Continuity of the chi-square distribution therefore yields

\lim_{n\to\infty} \Pr\!\left(D(\widehat P_{n,5}\Vert P)\ge\frac{162}{n}\right) =\Pr(\chi_4^2\ge324) =163e^{-162}.

In contrast, the conjectured upper bound converges to

\lim_{n\to\infty}2\left(1+\frac4n\right)^n e^{-162} =2e^4e^{-162}.

Since $e<3$ ,

2e^4<2\cdot3^4=162<163.

Consequently the asserted bound fails for every sufficiently large $n$ .

More generally, for every odd alphabet size $k=2r+1\ge5$ , the same limit at $\varepsilon=c/n$ forces any hypothetical bound $\Pr(D\ge c/n)\le C_k e^{-c}$ , uniform in $n,c>0$ , to satisfy

C_k\ge\sum_{j=0}^{r-1}\frac{c^j}{j!} \quad\text{for every }c>0.

Since this polynomial is unbounded, no finite alphabet-dependent prefactor can make such an exponential bound valid uniformly.