# Joint typicality of sequences

I know that for two i.i.d distributions $$P$$ and $$Q$$ the probability that $$Q$$ will produce a length $$n$$ sequence that is $$\epsilon$$-typical according to $$P$$ is bounded by $$Q(T_{P,\epsilon})\leq e^{-nD(P||Q)-n|\mathcal{X}|\epsilon}$$ where $$D(P||Q)$$ is the KL-dvergence and $$T_{P,\epsilon}$$ is the (strong) $$\epsilon$$-typical set of the distribution $$P$$, i.e. sequences with empirical distribution that is $$\epsilon$$-close to $$P$$.

Will this bound hold for $$Q$$ that is not i.i.d? For example, a Markov source? That is, will I have $$Q^n(T_{P^n,\epsilon})\leq e^{-D(P^n||Q^n)-n|\mathcal{X}|\epsilon}$$ where $$Q^n$$ is the distribution on sequences of length $$n$$?

Essentially, yes, although it is ambiguous the way you stated it (so it is not clear to me what $$T_{P^n}$$ really means). The general statement is that you have a LDP for the empirical process $$n^{-1}\sum \delta_{\theta^i X}$$ where $$X$$ is the infinite sequence and $$\theta$$ is the (left shift), in the product topology (ie, you can look at any types of $$k$$ successive letters, with $$k$$ fixed but arbitrary) and the rate function is the specific entropy $$\lim_{m\to\infty} \frac1m D(P_m|Q_m)$$ where $$P_m$$ is the restriction to $$m$$ letters of $$P$$ (assuming $$P$$ is stationary, otherwise the rate is infinity). If $$Q$$ is Markov and you are interested in types of length $$k$$ then you can restrict in the above formula $$m$$ to be equal $$k+1$$. For this and related statements look at $$$$LDP for empirical processes" in large deviations books, or look at the original Donsker-Varadhan papers.