Concentration conjecture for empirical relative entropy

Let Vn,k,PV_{n,k,P} denote the empirical relative entropy statistic for a multinomial distribution with sample size nn, alphabet size kk, and distribution PP. For θ0\theta\geq 0, write

θ=ε.\theta=\varepsilon.

Concentration conjecture. There are positive constants c1c_1 and c2c_2 such that for every nn, kk, PP, and ε0\varepsilon\geq 0,

Pr{Vn,k,PE[Vn,k,P]ε}c1exp{c2min{n2ε2k1,nε}}.\Pr\left\{\left|V_{n,k,P}-\mathbb{E}[V_{n,k,P}]\right|\geq\varepsilon\right\}\leq c_1\exp\left\{-c_2\min\left\{\frac{n^2\varepsilon^2}{k-1},n\varepsilon\right\}\right\}.

This conjecture would give finite-sample two-sided concentration of empirical relative entropy around its mean, improving bounds that focus only on deviations above zero. It was posed in the cited work and remains unresolved here.

Sources & referencesView supporting material

Primary source

Rohit Agrawal, “Finite-sample concentration of the empirical relative entropy around its mean”, arXiv:2203.00800 (2022).

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.