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



Joint typicality of sequences
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.


