Implications of Sublinear Relative Entropy in Product Spaces

22 Views Asked by At

Consider iid random vectors $X\in[k]^n$ with fully supported law $p\in\mathcal P([k])$ and $Y\in[k]^n$ with fully supported law $q\in\mathcal P([k])$, where $k>1$ and $[k]=\{1,\dots,k\}$. Let $D(X\|Y)$ denote the relative entropy of $X$ with respect to $Y$.

Claim: We have $\lim_{n\rightarrow\infty}\frac{1}{n}D(X\|Y)=0$ if and only if $p=q$ if and only if $X$ and $Y$ have the same law.

Proof: To see this, we only have to recall that $D(X\|Y)=\sum_iD(X_i\|Y_i)=nD(X_1\|Y_1)$ due to independence.

Now comes the tricky part. Say, we still have $X\in[k]^n$ iid with $p$, but now we consider any $Y\in[k]^n$. Clearly, the claim does not hold anymore, we may have $\lim_{n\rightarrow\infty}\frac{1}{n}D(X\|Y)=0$ although $X$ and $Y$ do not have the same law.

Question: What can we conclude from $\lim_{n\rightarrow\infty}\frac{1}{n}D(X\|Y)=0$?

For example, we can deduce that $Y$ is fully supported, otherwise the relative entropy wouldn't be finite. This yields $\mathrm d_{\mathrm{tv}}(X,Y)<1$ for the total variation distance. This does also give a coupling of $X$ and $Y$, albeit not helpful. I'm fairly sure this is not enough to obtain something like contiguity, but maybe concentration of the relative frequencies, bounds for point probabilities, maybe similarity of marginals on a bounded number of variables?

Also, what can we deduce from $\liminf_{n\rightarrow\infty}\frac{1}{n}D(X\|Y)>0$? I would also be grateful for results that use mild assumptions, say there exist absolute constants $0<c<C<1$ with $c^n\le\mathbb P(Y=y)\le C^n$.