# KL Divergence between an i.i.d sequence and non i.i.d sequence

I have two sequences of probability density functions $Q=\prod_{i=1}^{n} q(x_i)$ (independent and identically distributed, i.i.d )$P=p(x_1,\cdots,x_n)$ (non i.i.d). How can I calculate the KL divergence between them?

The standard way is to use the general formula

$$D(P||Q)= \int P(x_1,\cdots,x_n) \log{\frac{P(x_1,\cdots,x_n)}{Q(x_1)\cdots Q(x_n)}}d x_1 \cdots dx_n$$

If $P$ is also i.i.d, then it becomes really nice. I was wondering if I could find a nice representation given $Q$ is non-iid and $n$ is large.

Please let me know any ideas for simplifications, calculations, etc.

• Did you mean "if $P$ is also i.i.d.?" What kind of simplification are you seeking if you don't have an explicit form for either $P,Q$? – Alex R. Jun 25 '16 at 23:59
• When you say "non i.i.d.", do you know further about the structure of $P$? Say, does it have a Markov structure? – wij Jun 26 '16 at 12:26
• @wij Yes, it is output of a queue with exponential service times, given we know the input – Sus20200 Jul 13 '16 at 11:35