{'fraction_non_alphanumeric': 0.06158652540070633, 'fraction_numerical': 0.008312958435207823, 'mean_word_length': 4.042602739726028, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Typical support and Sanov large deviations of correlated states

Discrete stationary classical processes as well as quantum lattice states are asymptotically confined to their respective typical support, the exponential growth rate of which is given by the (maximal ergodic) entropy. In the iid case the distinguishability of typical supports can be asymptotically specified by means of the relative entropy, according to Sanov's theorem. We give an extension to the correlated case, referring to the newly introduced class of HP-states.


Introduction
A relevant notion on the interface of classical discrete probability theory and information theory is that of typical subsets. For the quantum extensions of these fields there is a corresponding notion: typical subspaces.
The general picture is that a stationary process (state in the case of quantum lattice systems) is asymptotically -i.e. observing a large finite interval-more and more confined to its typical support. The size of this support has an exponential growth rate (possibly zero) given by the essential supremum of the entropies of the ergodic components. In the classical situation this is the content of the Shannon-McMillan theorem. It clarifies the importance of Shannon entropy for several fields, from data transmission and compression to statistical mechanics or complexity theory.
Under the much stronger condition of complete independence Sanov's theorem (see [22] or [7]) specifies the exponential rate of this confinement of a classical iid process to its own typical set, or equivalently, the rate of avoidance of the supports of all other iid processes' typical sets. This large deviations result is usually seen as a result on empirical distributions, as in its formulation a particular instance of typical set appears: typical for an iid process are realizations with an empirical distribution close to the probability distribution underlying this very process, see ch. 3.2 in Deuschel and Stroock [9].
In the iid case Sanov's theorem significantly extends the assertion of the Shannon-McMillan theorem. In fact, taking the equidistribution as reference measure, it follows from Sanov's theorem that there is a universal typical set sequence of approximate size e nh for all iid processes with (base e) entropy less than h. It is well-known in the classical situation that this extends to the general ergodic case (since there exist universal compression schemes like the Lempel-Ziv algorithm). This universality result was generalized to the quantum case by Kaltchenko and Yang [14], using a nice 'rotation technique' and the quantum Shannon-McMillan theorem [1].
From the point of view of statistical hypothesis testing Sanov's theorem asserts that there is a universally typical set sequence for any set of iid probability distributions (null hypothesis), separating it optimally from any other set of iid processes (alternative hypothesis) at a rate arbitrarily close to the infimum of the relative entropies between probability measures from the two hypotheses. So in the classical case Sanov's theorem expresses a twofold universality in the choice of the typical sets.
The special case of Sanov's theorem with both hypotheses consisting of only one probability distribution each, is usually called Stein's lemma.
As already emphasized in [2], when passing from the classical to the quantum case, the universality mentioned above gets partially lost: there exists no longer a sequence of typical subspaces (of the underlying finite dimensional Hilbert spaces for the n-blocks of the system), which would work universally, whatever the reference states are. Consequently, speaking in the hypothesis testing terminology, for the alternative hypothesis only one process/state is admitted here. Universality with respect to the null hypothesis states is maintained, however. Also, in the quantum situation it is no longer possible to originate Sanov's theorem on the concept of empirical distributions (states), see [2], chapter 4.
We mention here that the main techniques needed to generalize Sanov's theorem to the iid quantum case were already presented in Hayashi [10] (1997), and in Hayashi [11] (2002) an equivalent result is shown. The authors of the present paper regrettably were not aware of this part of Hayashi's work during the preparation of [2].
It is the aim of this paper as a continuation of [2] to extend the assertion of Sanov's theorem in several directions. This concerns the classical case, too, but the main focus is on the quantum situation.
First, the restriction to the uncorrelated case is substantially alleviated: No condition besides stationarity is imposed to the processes/states P of the null hypothesis. As for the alternative hypothesis (reference measure/state) Q, even stationarity is not assumed. The only requirements are the existence of relative entropy rates h(W, Q) ≤ +∞ for the ergodic components W occurring in the null hypothesis set, and the validity of the upper bound (achievability part ) in Stein's lemma concerning W and Q (see Theorems 11 resp. 13 in the classical situation). These are, in a sense, minimal requirements, since Stein's lemma is a trivial consequence of Sanov's theorem obtained by forgetting about universality.
As an application of this general result we consider the case that a certain (admittedly very strong) mixing condition holds for the reference process Q. Observe that the very existence of the relative entropy rate for correlated processes can only be guaranteed in terms of mixing conditions, if the reference process is particulary strong mixing. Shields [24] gives an example where the reference process is even maximally mixing in the sense of Dynamical Systems theory (B-process, i.e. isomorphic to an iid process), but nonetheless there exists no asymptotic rate of the relative entropy. Though the mixing condition upon the reference processes is very strong ( * -mixing, cf. [4], or [5], where it is called ψ-mixing), the class of aperiodic irreducible Markov processes on a finite state space is covered. In this Markov case aperiodicity is necessary and sufficient for mixing, but not needed for Sanov's theorem, showing that * -mixing is far from being a necessary condition for a Sanov type theorem. In fact, in the classical case a kind of average-mixing would yield the result, cf. condition ( U) on page 86 of [9].
We also mention, that in the classical case a usual mixing condition to derive large deviation results is hypermixing, cf. chapter 5.4 in [9].
Secondly, we generalize the classical Sanov's theorem to the (correlated) quantum situation (in Hayashi [11] and later in [2] the quantum iid case was considered). In fact, since the classical assertion is a special case of the quantum theorem, we only prove the latter. Again, the reference state only needs to fulfil the two minimal conditions mentioned above. We refer to those as HP-condition. The states forming the null hypothesis have to be stationary only.
It would be interesting to specify the set of all states which fulfil the HPcondition with respect to any ergodic (null hypothesis) state. We call these states HP-states. As already said, this set comprises all * -mixing states, but can be expected to be much larger.
In the classical situation we remind the reader of an interesting example by Xu [25]: There exists a B-process (i.e. again maximally mixing in the sense of Dynamical Systems) Q which has the property that the relative entropy rate h(P, Q) exists and is zero for any stationary process P . So this process cannot be separated at exponential speed from an arbitrary other stationary process.
It would be interesting to find conditions weaker than * -mixing ensuring exponential separability in the case that the relative entropy rate is positive.
In the presented form, the quantum Sanov's theorem comprises and extends several earlier results on typical subspaces and their connection with the von Neumann entropy and relative entropy.
In particular, the result [2] of the present authors (which was preceeded by Hayashi [11]) is extended to the correlated case. The quantum Shannon-McMillan theorem [1] is covered and extended from the ergodic to the general stationary situation. The universality result of Kaltchenko and Yang [14] is covered, too, by using the tracial state as reference state in Theorem 11. In fact this Kaltchenko-Yang universality is a main ingredient in our proof. The quantum Stein's lemma (see [19], [20], chapter 1.1 for the iid case, [3] for the case of ergodic null hypothesis states) is covered and extended to the case of correlated reference states. Results of Hiai and Petz [12], [13] are completed in the sense that their bound is shown to be sharp, which means that it is asymptotically optimal, and the condition of complete ergodicity concerning the null hypothesis is dropped. In particular, the case of irreducible aperiodic algebraic (reference) states on a quasi-local algebra over a finite-dimensional C * -algebra A (also called finitely correlated states) considered in [13] is covered by * -mixing. We mention, that Hiai and Petz emphasize in [13] that they derive almost all assertions using * -mixing, only.
As already emphasized, the quantum Sanov' theorem is a special type of quantum large deviations result. We refer the reader to some other work in this direction, see Lebowitz, Lenci and Spohn [15], Lenci and Rey-Bellet [16], Netočný and Redig [18], De Roeck, Maes and Netočný [8].
We give a short account of the principal steps to prove the main result. In chapter 3 we show that 'one half' of Stein's lemma, namely the assumed achievability of the relative entropy rate as separation rate, already implies Sanov's theorem.
First it is shown that the optimality of the relative entropy rate (as separation rate) is a consequence of its achievability. In fact, for two states Ψ, Φ such that s(Ψ, Φ) and s(Ψ) exist, the quantity −n(s(Ψ, Φ)+ s(Ψ)) is the asymptotic average of the logarithmic eigenvalues of D Φ (n) , which denotes the density operator of the local state Φ (n) on the disrete interval of length n, with respect to the probability measure generated on the corresponding eigenvectors by the operator D Ψ (n) . On the other hand, the achievability part of Stein's lemma implies that −n(s(Ψ, Φ) + s(Ψ)) is also an essential upper bound for these logarithmic eigenvalues. The key tool to show the latter is Lemma 8. Now, roughly speaking, with the asymptotic average being the asymptotic upper bound, it must be an asymptotic lower bound, too. This observation yields a relative AEP (asymptotic equipartition property) for the logarithmic eigenvalues of D Φ (n) : the vast majority of them (with respect to the considered probability distribution) is close to −n(s(Ψ, Φ) + s(Ψ)). Because for ergodic Ψ by the quantum Shannon-McMillan theorem the relevant dimension of the corresponding subspace of eigenvectors of D Φ (n) is close to e ns(Ψ) , it easily follows now (applying Lemma 8 once again) that the optimally separating subspaces can essentially be described as those which are close to the span of the mentioned eigenvectors of D Φ (n) fulfilling the relative AEP: the Φ (n) -expectation is close to e ns(Ψ) · e −n(s(Ψ,Φ)+s(Ψ)) = e −ns(Ψ,Φ) .
Next we make use of the proven relative AEP, combined with Kaltchenko and Yangs universality result to show Sanov's theorem: We subdivide the null hypothesis set into small slices of almost constant value of the 'mixed' term (aka cross-entropy) s mix := s(Ψ, Φ) + s(Ψ) = − lim 1 n TrD Ψ (n) log D Φ (n) , and within these slices the entropy rate is bounded from above by s mix −inf Ψ s(Ψ, Φ). Then, by Kaltchenko-Yang universality, there exists a common support of dimension ≈ e n(smix−infΨ s(Ψ,Φ)) which by the relative AEP can be chosen to consist of eigenvectors of D Φ (n) with eigenvalues close to e −nsmix . So this common support has an asymptotic Φ (n) -expectation close to e n(smix−infΨ s(Ψ,Φ)) · e −nsmix = e −n infΨ s(Ψ,Φ) .
This essentially proves Sanov's theorem under the HP-condition.
In chapter 4 we prove that * -mixing implies the HP-condition, hence the quantum Sanov's theorem. The idea is borrowed from [13]: under * -mixing, the reference state Φ is sufficiently close to some block-iid state, so that we may apply the techniques developed in [12] and [3] in order to prove the achievability part of Stein's lemma.
In chapter 5 we use the ergodic decomposition of stationary states to extend our results to the case where the null hypothesis states are only assumed stationary.

Basic settings and notations
As announced in the introduction, we address both the classical and the quantum situation. Let us first consider the classical case. Let a finite set A of symbols be given. We deal with processes P on [A Z , A Z ], where A Z denotes the σ-field over A Z which is generated by finite dimensional cylinders. We denote the set of all processes by P(A Z ). Let P (n) denote the marginal of a process P , restricted to the positive (time) indices {0, 1, ..., n − 1} ⊂ Z.
The relative entropy rate between two processes P, Q is defined as h(P, Q) := lim n→∞ 1 n H(P (n) , Q (n) ) whenever this limit exists in R + = R + ∪{+∞}. Here H(·, ·) denotes the relative entropy of two probability measures given on a finite set. If Q ∈ P(A Z ), Ω ⊆ P(A Z ) and h(P, Q) exists for each P ∈ Ω we write h(Ω, Q) for inf P ∈Ω h(P, Q).
The following very strong mixing property of Q was introduced by Blum, Hanson and Koopmans [4] (referred to as ψ-mixing in the survey paper [5]), which implies the existence of the relative entropy rate h(P, Q) for any stationary P (see [13], where the more general quantum case is treated): Here A T , T ⊂ Z, denotes the sub-σ-field of A Z concerning only times t ∈ T . Observe that irreducible and aperiodic (i.e. weakly mixing) Markov chains are automatically * -mixing, even with α = α(l) tending to 1 exponentially fast as l → ∞. In the general situation, even strong mixing (α-mixing in the terminology of [5]) does not imply * -mixing, because rare events may still deviate much from independence.
We note that in the following we use the seemingly weaker condition, that (1) is fulfilled for some α > 0 and some l. (The same was emphasized for most of the results in [13].) But, in fact, in the stationary classical situation this is already equivalent to full * -mixing, see [5], Theorem 4.1.
Let P stat (A Z ), P erg (A Z ) resp. P * (A Z ) denote the set of stationary, of ergodic resp. stationary * -mixing processes with state space A.
We briefly introduce now the corresponding quantum set-up. Consider a finite-dimensional C * -algebra A. The classical case is covered choosing A is abelian.
It is well-known, that A can always be represented as a finite direct sum of matrix algebras where M k is the algebra of complex k × k matrices. The abelian case is covered if all k i are 1, meaning that A is simply the commutative algebra of complex functions over a finite set A = {1, 2, ..., m}. A state ψ on A is a positive functional on A with the property ψ(1) = 1, where 1 is the unity. The set of all states on A is denoted by S(A). This is the set of probability measures on A in the abelian case. Any state ψ on the finite-dimensional algebra A is uniquely given by its density operator D ψ ∈ A, which is a positive trace-one operator fulfilling Here Tr A denotes the canonical trace in A which is nothing but the sum of the matrix traces in the above representation (2).
The quantum generalization of a stochastic process is usually constructed as follows (and in correspondence to the definition of a process by its compatible finite-dimensional distributions via Kolmogorov's extension theorem): For each finite subset T ⊂ Z consider the C * -algebra A T := t∈T A. Then for any With respect to this identification consider the algebra A is not norm-complete. We denote the completion by A Z . It is a C * -algebra and is called the quasilocal algebra constructed from A. Again, a state Ψ on A Z is a positive functional on A Z with the property Ψ(1) = 1. If A is abelian, there is a one-to-one correspondence between states on A Z and stochastic processes with alphabet A: The restrictions Ψ (T ) := Ψ ↾ A T of Ψ to the local algebras A T correspond to the marginals P (T ) of the stochastic process P on the cylinder σalgebras A T . This comes from the fact that any compatible family of local states Ψ (T ) has a unique extension to A Z just as any compatible family of marginals can be extended to a stochastic process.
There is a canonically defined shift operator τ on A Z (mapping in particular The set of stationary states S stat (A Z ) is the subset of states in S(A Z ) which are invariant with respect to τ . This is a Choquet simplex, the extremal points are called ergodic states S erg (A Z ). The notions coincide with the classical ones in the abelian case.
We complete the picture by defining a mixing property (cf. [13]) as above: .
We denote the set of stationary * -mixing states by S * (A Z ). Next we introduce the quantum version of the relative entropy rate. Let ψ, ϕ ∈ S(A). The relative entropy is defined as Here supp(D) is the smallest projection p ∈ A fulfilling pDp = D (with D ∈ A self-adjoint). Now, for Ψ, Φ ∈ S(A Z ), we define the relative entropy rate , Ω ⊆ S(A Z ) and s(Ψ, Φ) exists for each Ψ ∈ Ω we write s(Ω, Φ) for inf Ψ∈Ω s(Ψ, Φ).
This condition was first proved to be fulfilled by Hiai and Petz in [12] for the special case that Ψ is completely ergodic and Φ is a stationary product state (i.e. an iid state) and later in [13] for completely ergodic Ψ and * -mixing states Φ.

Definition 4 We say that
As it turns out, the statement in Sanov's theorem is equivalent to the HPcondition: Theorem 5 Let Φ be a state on A Z and Θ ⊆ S erg (A Z ). Then following statements are equivalent: 1. For each Ψ ∈ Θ the pair (Ψ, Φ) satisfies the HP-condition.
2. The quantity s(Ψ, Φ) ≤ +∞ exists for each Ψ ∈ Θ, and to each subset Ω ⊆ Θ and any η > 0 there exists a sequence {p n } n∈N of projections otherwise limsup Hence −s(Ω, Φ) is the lower limit of all achievable separation exponents. 2. If Φ is stationary and, moreover, * -mixing, statement 1. of the Theorem is fulfilled with Θ = S erg (A Z ). This will be seen in section 4.
The implication 2. ⇒ 1. is trivial. The proof of the converse implication is carried out in subsection 3.2.
As an immediate consequence, we have the following assertion for the classical case: Let the maximally separating exponents for two processes P, Q ∈ P(A Z ) be defined by for ε ∈ (0, 1). Byβ ε (P, Q) we denote limsup n→∞ 1 n β ε,n (P, Q), and if the limit exists in −R + , we denote it by β ε (P, Q).
Theorem 7 Let Q ∈ P(A Z ), Θ ⊆ P erg (A Z ) and suppose that the relative entropy rate h(P, Q) exists for all P ∈ Θ. Then following statements are equivalent: and limsup Moreover, for each sequence of subsets { M n } fulfilling (6) we have Hence −h(Ω, Q) is the lower limit of all achievable separation exponents.

A quantum relative AEP and achievability in Stein's lemma
We start with a useful lemma which allows to translate some standard techniques and estimates used in classical information theory into the quantum setting.
Lemma 8 Let p, q be arbitrary projections and τ be a state on A. Suppose that u is a projection commuting with D τ . Then we have Let c > 0. If D τ u ≤ cu then Proof. The first inequality in (7) is trivial. The second follows applying the Cauchy-Schwarz inequality for the Hilbert-Schmidt inner product: In the last inequality the assumption [u, D τ ] = 0 has been used. Finally observe that u ≥ 1 c D τ u and Tr(pq) = Tr(qpq) = Tr(qpqu) + Tr(qpq(1 − u)) ≥ 1 c Tr(qpqD τ u).
where spec λ (·) denotes the eigen-projection of its argument's density operator (here D Φ (n) ) corresponding to the eigenvalue λ. We extend this definition to the case s = ∞ by setting Now we have Proposition 9 Let Ψ be ergodic and let Φ be an arbitrary state on A Z . If the pair (Ψ, Φ) fulfills the HP-condition then: for each ε ∈ (0, 1).
• Moreover, for all ε > 0 it holds that and for each sequence {p n } of projections fulfilling there is a sequence ε n ց 0 such that with u n := u εn Remark. The quantum Shannon-McMillan theorem [1] guarantees the existence of a sequence of projections {p n } with the properties assumed in (11). We refer to such sequences as entropy-typical w.r.t. Ψ. Roughly speaking, the above proposition shows that one obtains a sequence of maximally seperating projections as an 'intersection' of Ψ-entropy-typical projections with appropriate eigen-projections of the reference state Φ.
In fact, suppose on the contrary that for some ε > 0 we have limsup n→∞ Ψ(p n,ε ) > 0.
Fix some α ∈ (0, 1), δ > 0. Let p nj := p nj ,ε , q nj := arg min β α,nj (Ψ, Φ) and u nj := u δ Ψ (n j ) (s(Ψ)). Then D Ψ (n j ) u nj ≤ cu nj for c = e −nj(s(Ψ)−δ) and by Lemma 8 and the quantum Shannon-McMillan theorem we arrive at and if j is large enough and if 2 √ α + δ < γ. Now, observe that D Φ (n j ) and p nj commute and that consequently we have D Φ (n j ) ≥ e −nj(s(Ψ)+s(Ψ,Φ)−ε) p nj by definition of p nj . Thus we obtain After applying trace to both sides of this inequality, taking logarithms, dividing by n j , taking limit superior and using (12) we are led tō which contradicts the assumed HP-condition provided that δ < ε.
In the case s(Ψ, Φ) = ∞ everything can be done in the same way, we just have to substitute the definition of p n,ε by and obtainβ α ≥ − 1 ε + s(Ψ) − δ, again in contradiction toβ α (Ψ, Φ) = −∞, hence again the projectors p n,ε have asymptotically vanishing expectation with respect to Ψ for each positive ε.
Using the quantum Shannon-McMillan theorem and again Lemma 8, this time applied to the density operator of Ψ (n) and with u := λ<e −n(s(Ψ)−δ) spec λ (Ψ (n) ), for arbitrary δ > 0 and n large enough we have Trp n q n ≥ e n(s(Ψ)−δ) a for some 0 < a < 1 independent of n. Hence we get for any ε, δ > 0 for n large enough. Therefore, the quantity β α (Ψ, Φ) exists for any α ∈ (0, 1) and coincides with −s(Ψ, Φ), where we used again the HP-condition. In the case s(Ψ, Φ) = ∞ this assertion is a trivial consequence ofβ α (Ψ, Φ) = −∞. 4. Let {p n } be a sequence of projections p n ∈ A (n) with lim n→∞ Ψ (n) (p n ) = 1 and lim n→∞ 1 n log Tr(p n ) = s(Ψ). Fix some ε > 0. Let us write u n instead of u ε Φ (n) (s(Ψ) + s(Ψ, Φ)) for short. From (14) and Lemma 8 we infer that Ψ (n) (u n p n u n ) → n→∞ 1. Now u n p n u n is a positive operator being upper bounded by its support projection supp(u n p n u n ) which proves Ψ (n) (supp(u n p n u n )) → n→∞ 1. From this we easily conclude that we may even substitute the ε in the definition of u n = u ε Φ (n) (s(Ψ) + s(Ψ, Φ)) by a suitable sequence ε n → 0 and still have Ψ (n) (supp(u n p n u n )) → n→∞ 1.
On the other hand, we have supp(u n p n u n ) ≤ u n as well as Tr(supp(u n p n u n )) ≤ Tr(p n ). Hence we get in the case s(Ψ, This together with the fact we proved that no sequence of Ψ -typical projections has a better lower limit of the separation rate than −s(Ψ, Φ) shows now that We proved all assertions of the proposition.

Stein's Lemma implies Sanov's Theorem
With the preliminaries given in the last subsection, it is now easy to complete the proof of Theorem 5: Proof. Let and lim n→∞ Ψ (n) (p n,i ) = 1 (16) for each ergodic state with s(Ψ) < s i + η). In addition, set p n,m+1 := p n,m . We may choose the sequence of these projections to be ascending, i.e.
since otherwise we may define p n,i := i j=1 p n,j .
Finally, the fact that a better separation exponent than −s(Ω, Φ) is not achievable immediately follows from Proposition 9.

* -mixing implies the HP-condition
We start with a proposition extending the result in [13] to the case of only ergodic (instead of completely ergodic) Ψ.
Recall that S * (A Z ) denotes the set of stationary * -mixing states, see Definition 2.
2. Fix some l ∈ N, another integer m (which in the sequel has to be chosen large enough) and represent the quasilocal C * -algebra A Z as C * -algebra (A ⊗l ⊗ A ⊗m ) Z , i.e. partition the integers into blocks of length l + m, where each block consists of a starting part of length l and the remaining part of length m. Clearly, the entropy rate s (l+m) (Ψ, Φ) with respect to this new partitioning exists, and we have s (l+m) (Ψ, Φ) = (l + m)s(Ψ, Φ). With respect to the canonical shift operator τ l,m := τ l+m acting in (A ⊗l ⊗ A ⊗m ) Z , the state Ψ is still stationary, but may fail to be ergodic. Anyway, it has a finite ergodic decomposition where some of the ergodic components may coincide, and all Ψ (r,l+m) have the same entropy rate s (l+m) (Ψ (r,l+m) ) ≡ s (l+m) (Ψ) = (l + m)s(Ψ), [1]. The ergodic components also have the same relative entropy rate s (l+m) (Ψ (r,l+m) , Φ) := s (l+m) (Ψ, Φ) = (l + m)s(Ψ, Φ). Observe that this was shown in [3] for the case of stationary product states Φ. However as the proof only makes use of the existence of the relative entropy rates s (l+m) (Ψ (r,l+m) , Φ), which is guaranteed in our situation (see 1.), the monotonicity of the relative entropy and the affinity of the relative entropy rate with respect to its first argument the relation extends to * -mixing reference states.
Next, denote by I the trivial subalgebra of A generated by the unit element 1 A and consider the C * -subalgebra I ⊗l ⊗ A ⊗m of A ⊗l ⊗ A ⊗m . Then (I ⊗l ⊗ A ⊗m ) Z is a C * -subalgebra of the quasi-local algebra (A ⊗l ⊗ A ⊗m ) Z , and by [6], Theorem 4.3.17, the restrictions Ψ (r,l,m) of the ergodic components Ψ (r,l+m) to (I ⊗l ⊗ A ⊗m ) Z are ergodic, too. They are the ergodic components of Ψ (l,m) := Ψ ↾ (I ⊗l ⊗A ⊗m ) Z .
We introduce the (τ l,m -)stationary product state Φ (l+m) on (A ⊗l ⊗ A ⊗m ) Z which is uniquely defined by its one-site marginals Φ ↾ A ⊗l ⊗A ⊗m , and consider its restriction Φ (l,m) to the C * -algebra (I ⊗l ⊗ A ⊗m ) Z , which is a (τ l,m -)stationary product state, too.
3. In the following we have to take into account whether s(Ψ, Φ) is finite or infinite. Let us first treat the case s(Ψ, Φ) < +∞.
Define for two states ψ, ϕ on a C * -algebra A, : q i projections with q i = I (cf. [12]). Consider the relative entropies S( Ψ (l,m) ), then we get by the subadditivity of entropy and by the fact that the rates of the quantities S and S co coincide (Hiai and Petz [12]) ).
From the definition of S co and * -mixing we obtain now This is the same technique as used by Hiai and Petz in [13]. Again from the definition of S co we get (r,l+m) , Φ (k(l+m)) ), and from the relation S co ≤ S (see [12]), which is a consequence of the monotonicity of the relative entropy, we arrive at This upper bound may be utilized to derive an essential lower bound. For an arbitrarily chosen η > 0, define The convexity of the relative entropy in its first argument together with (19) yields Fixing l and letting m → ∞, the expression 1 l+m S(Ψ (m) , Φ (m) ) tends to s(Ψ, Φ). This immediately leads to the conclusion that For each r ∈ A c l,m,η , the relative entropy rate fulfills too, since Φ (l,m) is a τ l+m -stationary product state. 4. Hence we are in the situation treated in [3]. The main assertion of [3] is the quantum Stein's lemma saying that for any given ε > 0 it is possible to construct projections p r,n,ε ∈ (I ⊗l ⊗ A ⊗m ) ⊗n which are ε-typical with respect to Ψ (r,l,m) (i.e. Ψ for each minimal projection p ≤ p r,n,ε . For our purpose we need a bit more information about the construction of these maximally separating projections. In the course of the proof of Theorem 2 in [3] the projections p r,n,ε are constructed in the following way: a) A super-block length L is chosen, where the only requirement about L is that it is large enough to ensure some appropriate entropy approximation (any larger L will do, too).
b) The projections p r,nL,ε are constructed as certain sub-projections of the projection c) The remaining projections p r,nL+k,ε for 1 ≤ k < L are constructed as p r,nL,ε ⊗ (I A ⊗(l+m) ) ⊗k .
For given l and m we may choose one and the same super-block length L for the different r ∈ {0, 1, ..., l + m − 1} and define our separating projections first for the multiples of L(l + m) by q nL(l+m),ε := r∈A c l,m,ε p r,nL,ε .
In view of (23) we get, using (22) Next, observe that by the subadditivity of the entropy we have for each r s (l+m) ( Ψ (r,l,m) ) = lim From * -mixing we get now the desired separation order On the other hand, Ψ-typicality is guaranteed by the last inequality being valid for large n. We may continue for m large enough (by (21)). Now (in the usual way) we may interpolate the q nL(l+m),ε in order to define the projections q n,ε also for n ∈ N which are not multiples of L(l + m). We derived the existence of a sequence of projections being asymptotically ε-typical for Ψ and fulfilling Φ (n) (q n,ε ) ≤ e −n(s(Ψ,Φ)−ε) for large n. This proves that, for any α ∈ (0, 1) the separation exponent fulfils β α (Ψ, Φ) ≤ −s(Ψ, Φ) for finite s(Ψ, Φ) . 5. Now assume s(Ψ, Φ) = +∞. Observe that in that case the estimates in (20) and hence (21) are not valid. But (21) becomes true if we replace the definition of A l,m,η most appropriately by due to [1]. The states Ψ (r,M) = Ψ (0,M) • τ −r are τ M -ergodic. In view of the (joint) convexity of the relative entropy we conclude that at least one of the r fulfils S(Ψ (M) (r,M ) , Φ (M) ) > η −1 M . We may assume without any loss of generality that this is true for r = 0, i.e. S(Ψ (M) (0,M ) , Φ (M) ) > η −1 M . The τ M -ergodic state Ψ (0,M) again has an ergodic decomposition with respect to τ 2M and, applying once again the convexity argument we find that we may assume In view of the monotonicity of the relative entropy we get now for r ≥ l S(( Ψ (r,l,2M−l) ) (2M) , Φ ↾ I ⊗l ⊗A ⊗m ) > η −1 M. (21) is fulfilled for M sufficiently large. We conclude that asymptotically for the overwhelming part of the r in {0, 1, ..., l + m − 1} the expression 1 l+m s (l+m) ( Ψ (r,l,m) , Φ (l,m) ) is arbitrary large (i.e. > 1 2 η −1 or even infinite) for large m. Now we may proceed essentially as in 4., employing the results of [3]. We find projections p r,nL,η , separately for each r in A c l,m,η , which distinguish between Ψ (r,l,m) and Φ (l,m) exponentially well at a rate at least 1 3 η −1 , and we may join these projections to find Ψ-typical projections q nL(l+m),η . This is possible due to the properties a) and b) above, where now b) is modified to b') The projections p r,nL,η are constructed as certain sub-projections of the projection

So again
But we have to take into account that [3] only treats the case of finite relative entropy rate; hence those r, for which S( Ψ Obviously, this projection fulfils ( Φ (l+m) (l,m) ) ⊗nL (spec 0 (( Φ (l+m) (l,m) ) ⊗nL )) = 0, and it is a sub-projection of p (nL) . We still have to show that spec 0 (( Φ where N n := {(j 1 , ..., j n ) : n k=1 λ j k = 0} = ((N c 1 ) n ) c . Denote by B the abelian sub-algebra of I ⊗l ⊗ A ⊗m generated by the set {v j }. Then the quasi-local algebra B Z is an abelian sub-algebra of (I ⊗l ⊗ A ⊗m ) Z and the restriction P of Ψ (r,l,m) to this sub-algebra is a classical ergodic process with K symbols (Gelfand isomorphism and Riesz representation theorem). This process fulfils

The stationary case
So far we formulated the Theorems 5 and 7 for sets of ergodic states Ψ resp. processes P to be optimally separated from a reference state or process. These results can be easily extended to the general stationary situation.
Any stationary state Ψ ∈ S stat (A Z ) can be represented as a mixture (ergodic decomposition) of ergodic states (S stat (A Z ) is a Choquet simplex, S erg (A Z ) is the corresponding set of extremal points, γ Ψ is a probability measure on the measurable space [S erg (A Z ), B(Υ A Z )], with Υ A Z denoting the weak- * -topology and B(Υ A Z ) the corresponding Borel σ-field, cf. [21]). The measure γ Ψ is unique. Now let Φ ∈ S(A Z ) be a state and Θ ⊆ S stat (A Z ) with the property that for any Ψ ∈ Θ the relative entropy rate s(Ξ, Φ) exists for γ Ψ -almost all Ξ. We define the quantity Hence −s(Ω, Φ) is the lower limit of all achievable separation exponents.

Remark 12
If Φ is stationary and, moreover, * -mixing, the assumption of the Theorem 11 is fulfilled with Θ = S stat (A Z ), according to section 4.
Proof. Let Φ again be the tracial state in S(A Z ). Apply Theorem 11 in a similar way as in the proof of Corollary 15 to the sets Ω s−η , η > 0.

Remark 18
Observe that the condition s(Ψ) < s defining Ω s cannot be replaced by s(Ψ) ≤ s.
Finally, quantum Stein's lemma [3] is extended to the case where the null hypothesis state Ψ is only assumed stationary, the reference state Φ fulfills the HP-condition with respect to almost all ergodic components of Ψ (and the relative entropy rate s(Ψ, Φ) may be infinite):
Remark 20 Note that the relative AEP does not hold in Stein's lemma in the stationary case. Again, the relevant quantity in the stationary situation is not the average relative entropy rate s(Ψ, Φ), but the essential infimum s(Ψ, Φ).

Proof.
With Ω consisting of a single state Ψ only, we may proceed in the same way as in the proof of Corollary 15.

Conclusions
The paper is devoted to a generalization of Sanov's theorem from the iid classical situation to the correlated case and, moreover, to the quantum setting. In the present form, the main result comprises and extends several earlier assertions including the (quantum and classical) Shannon-McMillan theorem, Stein's Lemma (with relative AEP), Kaltchenko and Yang's universality and, of course, a version of Sanov's theorem itself. It is a continuation of [2], where the uncorrelated case is considered. It has to be pointed out again (see [2]), that any attempt to formulate a quantisized version of Sanov's result has to face the problem that the very notion of a trajectory and its empirical distribution is problematic in quantum mechanics. Sanov's classical theorem claims that for an iid process with marginal Q the probability to produce a trajectory with the empirical distribution belonging to some set Ω of probability measures is (in general) exponentially small. The corresponding rate is specified as the minimal relative entropy between Q and the distributions in Ω. In the interesting case the measure Q is of course not an element of Ω or its topological closure. So it is a large deviation result: the typical behaviour of Q-trajectories is to have an empirical distribution close to Q. Whatever one tries to adopt as a quantum substitute for the empirical distribution, the natural choice in the case of a tensor product of vector states v ⊗ v ⊗ ... ⊗ v should be v itself. This leads into the problem that for a reference vector state w ⊗n the probability of measuring an 'empirical state' v is at least TrP w ⊗n P v ⊗n = | w|v | 2n , while the relative entropy of v wrt w is infinite, which would imply a super-exponential decay; for a more detailed exposition see [2]. In this situation it proves useful to look at Sanov's theorem as an assertion about the likelihood of observing the classical iid process given by Q far from its original support in the vicinity of the supports of other iid processes. The most natural choice for 'typical support' in the classical framework is the set of trajectories with empirical distribution close to the given probability distribution, since according to the individual ergodic theorem the empirical distribution tends to Q with probability one. So Sanov's theorem in its original form says that the probability of observing the trajectory in the typical support of other distributions, concretely specified by means of the corresponding empirical distributions, vanishes at a rate given by the minimum relative entropy. It is of course completely legitimate to insist on the point of view, that a quantum Sanov's theorem should be about empirical distributions, too (see [17], Remark 4, see also an attempt to formulate a quantum (iid) Sanov theorem made in Segre's Ph.D. thesis [23] (2004), Conjecture 7.3.1.). But, as explained, then one loses the relation to the established form of quantum relative entropy (Umegaki's relative entropy). We chose to 'sacrifice' empirical distributions in our approach but nonetheless calling it a version of Sanov's theorem: in the classical case the relative entropy is not only the rate of separation when empirical distributions as specifying typical sets are considered. It has a clear operational meaning as the optimal separation rate, whatever one considers as typical support in the sense that the probability goes to one. This perception of Sanov's theorem, closely connected with the statistical hypothesis testing aspect, appears to be natural. It allows useful generalizations to the correlated and quantum cases.