Centralized concentration conjecture for empirical relative entropy

Let PP be a distribution on a finite alphabet of size kk, let P^n,k\hat{P}_{n,k} be its empirical distribution from nn independent samples, and let D(P^n,kP)D(\hat{P}_{n,k} \| P) denote the relative entropy. There exist constants g1>0g_1>0 and g2>0g_2>0 such that, for every t>0t>0, Centralized concentration conjecture.

P(D(P^n,kP)E[D(P^n,kP)]t)g1eg2min{n2t2k1,nt}.\mathbb{P}\left(\left|D(\hat{P}_{n,k} \| P)-\mathbb{E}[D(\hat{P}_{n,k} \| P)]\right| \geq t \right) \leq g_1 e^{-g_2 \min\left\{ \frac{n^2t^2}{k-1}, nt \right\}}.

This conjecture is motivated by the asymptotic chi-squared behavior of 2nD(P^n,kP)2nD(\hat{P}_{n,k}\|P) and standard concentration bounds for sub-exponential random variables. The source does not indicate that it has been proved or disproved.

Sources & referencesView supporting material

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).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.