# Relative Entropy decomposition reference

may I ask for some reference pointers? My bad as I got a classic case of losing my reference and thus unsure what I wrote was right or wrong. I tried looking my old references and internet and didn't find anything (wrong keywords probably). So I was hoping to try my luck here.

Given vector $\vec{X}$ of $n$ iid observations on finite alphabet $\mathsf{X}$ from distribution $P$ and $\hat{P}_n(a) = \frac{1}{n}\sum_{i=1}^n \mathbb{1}_{X_i=a}$.

$$E\left[D(\hat{P}_n||Q)-D(\hat{P}_n||P)\right] = D(P||Q)$$ where the expectation is under $P$ which is the same density of $\hat{P}_n$.

I hope there isn't any errors above as its from a hand-written note. Assuming if it is right, can anyone help point to where I can find the source regarding this ?

• I don't quite get what $P$ is. – leonbloy Feb 2 '15 at 20:13
• Hello! I will try the best I could from I could make out of my notes. So I might be wrong as I am guessing here. I use P to differentiate from $\hat{P}_n$ but they are actually the same. The reason is $\hat{P}_n(a) = P(a)$ but under the expectation $\hat{P}_n$ is random. To clarify, I think its $E(D(\hat{P}_n||P))=\int Pr(\vec{x})D(\hat{P}_{\vec{x}}||P)d\vec{x}$ integrate over all possible n-vectors. – shunjie Feb 2 '15 at 20:41
• $\hat{P}_n$ is random, that's ok, but $P$ should not be. YOur formula $E(D(\hat{P}_n||P))=\int Pr(\vec{x})D(\hat{P}_{\vec{x}}||P)d\vec{x}$ would make sense to me when applyied to $Q$ instead of $P$. – leonbloy Feb 2 '15 at 20:52
• Are you sure the alphabet follow distribution $Q$? All would make sense if $X_i$ come from distribution $P$ instead, and if $Q$ is some other arbitrary distribution. – leonbloy Feb 2 '15 at 20:53
• I am not sure if the alphabets comes from Q. I tend to use Q as my source distribution so I assume that is what I wrote. Therefore, may I ask if I change $X \sim P$ then the above made sense ? May I know where I can find some reference about it ? Thanks. I will update the question. – shunjie Feb 2 '15 at 20:57

In general, for any distribution $T$:

$$D(\hat{P}_n||T) = \sum_i \hat{P}_n(i) [\log \hat{P}_n(i) - \log T(i)]$$

Then

$$D(\hat{P}_n||Q)-D(\hat{P}_n||P) = \sum_i \hat{P}_n(i) \log \frac{P(i)}{Q(i)}$$

The above is random, because $\hat{P}_n$ is random. Now, I'll assume that the samples come from distribution $P$. Taking expectation over $P$ , and using $E_P(\hat{P}_n(i))=P(i)$ and linearity of expectation, we get

$$D(\hat{P}_n||Q)-D(\hat{P}_n||P) = \sum_i P(i) \log \frac{P(i)}{Q(i)} = D(P\mid\mid Q)$$