Joint typicality of sequences

Question

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

Answer 1

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.