0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.