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 ?

  • $\begingroup$ I don't quite get what $P$ is. $\endgroup$ – leonbloy Feb 2 '15 at 20:13
  • $\begingroup$ 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. $\endgroup$ – shunjie Feb 2 '15 at 20:41
  • $\begingroup$ $\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$. $\endgroup$ – leonbloy Feb 2 '15 at 20:52
  • $\begingroup$ 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. $\endgroup$ – leonbloy Feb 2 '15 at 20:53
  • $\begingroup$ 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. $\endgroup$ – 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)] $$


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

  • $\begingroup$ Thank you for your answer. This made sense $\endgroup$ – shunjie Feb 2 '15 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.