4

Note: this is an assignment question

Let $X$ be a discrete random variable with values in $\{1,...,n\}$. $P$ denotes the distribution on $\{1,...,n\}$ when $X$ ~ $bin(n,p)$ and Q denotes the distribution on $\{1,...,n\}$ when $X$ ~ $bin(n,q)$ for $p,q \in (0,1)$. Compute the Kullback-Leibler-distance $D(P || Q)$. We write $X$ ~ $bin(n,p)$ if it is Binomial-distributed with parameters $n,p$, that is

$$P[X=k]=\binom{n}{k} p^k (1-p)^{n-k}$$

I have started to write down the definition of the KL divergence which is :

$$D(P||Q)=\sum_{x \in X}{p(x)*log_2 \frac{p(x)}{q(x)}}.$$

After inserting my values this is:

$$D(P||Q)=\sum_{x \in X}{ \binom{n}{x}p^x(1-p)^{n-x} *log_2 \frac{\binom{n}{x}p^x(1-p)^{n-x}}{\binom{n}{x}q^x(1-q)^{n-x}}}.$$

from which I can factor out $\binom{n}{x}$ in the fraction:

$$D(P||Q)=\sum_{x \in X}{ \binom{n}{x}p^x(1-p)^{n-x} *log_2 \frac{p^x(1-p)^{n-x}}{q^x(1-q)^{n-x}}}.$$

I don't see how I can further simplify this term, can someone give me a hint?

Community
  • 1
Marco
  • 69

1 Answers1

9

As you have pointed out, $$ D(P\ \|\ Q) = \sum_{i=0}^n \left\{\binom{n}{i} p^i(1-p)^{n-i}\log\left(\frac{p^i(1-p)^{n-i}}{q^i(1-q)^{n-i}}\right)\right\} $$ Observing that $$ \log\left(\frac{p^i(1-p)^{n-i}}{q^i(1-q)^{n-i}}\right) = i\log\left(\frac{p}{q}\right) + (n-i)\log\left(\frac{1-p}{1-q}\right) $$ we have \begin{align} D(P\ \|\ Q) &= \sum_{i=0}^{n}\left\{\binom{n}{i} p^i(1-p)^{n-i}\left(i\log\left(\frac{p}{q}\right) + (n-i)\log\left(\frac{1-p}{1-q}\right)\right)\right\} \\ &= \sum_{i=0}^{n}\left\{\binom{n}{i} p^i(1-p)^{n-i}i\log\left(\frac{p}{q}\right)\right\} + \sum_{i=0}^{n}\left\{\binom{n}{i} p^i(1-p)^{n-i}(n-i)\log\left(\frac{1-p}{1-q}\right)\right\} \\ &= \log\left(\frac{p}{q}\right)\sum_{i=0}^n\left\{i\binom{n}{i} p^i(1-p)^{n-i}\right\} + \log\left(\frac{1-p}{1-q}\right)\sum_{i=0}^{n}\left\{(n-i)\binom{n}{i} p^i(1-p)^{n-i}\right\} \\ &= \log\left(\frac{p}{q}\right)np + \log\left(\frac{1-p}{1-q}\right)n(1-p) \end{align} where the last equality comes from the fact that $$ \sum_{i=0}^n\left\{i\binom{n}{i} p^i(1-p)^{n-i}\right\} $$ is the expectation of $\mathsf{bin}(n, p)$ and $$ \sum_{i=0}^{n}\left\{(n-i)\binom{n}{i} p^i(1-p)^{n-i}\right\} $$ is the expectation of $\mathsf{bin}(n, 1 - p)$.

PSPACEhard
  • 10,283