Abstract
Abstract. We derive explicit upper bounds for thed-distance between a chain of infinite order and its canonical k-steps Markov approximation. Our proof is entirely constructive and involves a "coupling from the past" argument. The new method covers non necessarily continuous probability kernels, and chains with null transition probabilities. These results imply in particular the Bernoulli property for these processes.
INTRODUCTION
Chains of infinite order are random processes that are specified by probability kernels (conditional probabilities), which may depend on the whole past. They provide a flexible model that is very useful in different areas of applied probability and statistics, from bioinformatics Bejerano & Yona (2001) ; Busch et al. (2009) to linguistics Galves et al. (2010 Galves et al. ( , 2009 . They are also models of considerable theoretical interest in ergodic theory Coelho & Quas (1998) ; Hulse (1991) ; Quas (1996) ; Walters (2007) and in the general theory of stochastic process Bramson & Kalikow (1993) ; Comets et al. (2002) ; Fernández & Maillard (2005) . A natural approach to study chains of infinite order is to approximate the original process by Markov chains of growing orders. In this article, we derive new upperbounds on thed-distance between a chain and its canonical k-steps Markov approximation.
INTRODUCTION
Introduced by Ornstein (1974) to study the isomorphism problem for Bernoulli shifts, thed-metric is of fundamental importance in ergodic theory where chains of infinite order are also known as g-measures. Thed-distance between two processes can be informally described as the minimal proportion of times we have to change a typical realization of one process in order to obtain a typical realization of the other. Ornstein (1974) showed that the set of processes which are measure theoretic isomorphic to Bernoulli shifts isd-closed. Ergodic Markov chains are examples of processes that are isomorphic to Bernoulli shifts. Therefore, if a process can be approximated arbitrary well under thed-metric by a sequence of ergodic Markov chains, then this process has the Bernoulli property. In this article we prove the existence of Markov approximation schemes for classes of chains of infinite order with non-necessary continuous and with possibly null transition probabilities. Some of these processes were not considered before. For example, Coelho & Quas (1998) , Fernández & Galves (2002) , and Johansson et al. (2010) required the continuity of the probability kernels. Our results show that these new examples are isomorphic to Bernoulli shifts and provide explicit upper bounds for the Markov approximation in several important cases, giving therefore information on how good these approximations are.
INTRODUCTION
Besides ergodic theory, thed-distance is useful in statistics and information theory. Rissanen (1983) proposed to model data as realizations of stochastic chains, and proved that these data can be optimally compressed using the (unknown) probability kernel of the chain. The statistical problem is then to recover this probability kernel from the observation of typical data. Since the number of parameters to estimate is infinite, this task is impossible in general. A possible strategy to overcome this problem is the following. (1) Couple the original chain with a Markov approximation and (2) work with the approximating Markov chain. Thed-distance between the chain and its Markov approximation controls the error made in step (1). The idea is that, if this control is good enough, the good properties of the approximating Markov chain proved in step (2) can be used to study the original chain. For instance, Duarte et al. (2006) and Csiszár & Talata (2010) derived consistency results for chains of infinite order from the consistency of BIC estimators for Markov chains proved in Csiszár & Talata (2006) . This "two steps" procedure was also used in Collet et al. (2005) to obtain a bootstrap central limit theorem for chains of infinite order from the renewal property of the approximating Markov chains.
INTRODUCTION
Our main results derive from coupling arguments. We first introduce a flexible class of Coupling from the past algorithms (CFTP algorithms, see Section 2.3). CFTP algorithms constitute an important class of perfect simulation algorithms popularized by Propp & Wilson (1996) . Our main assumption on the chain is that the original chain of infinite order can be perfectly simulated via such CFTP algorithms. We state a technical result, Lemma 4.1, which provides an abstract upper bound for thed-distance with the canonical Markov approximation. This bound is then made explicit under various extra assumptions on the process used in the study of the CFTP algorithms of (Comets et al., 2002; De Santis & Piccioni, 2010; Gallo, 2011; Gallo & Garcia, 2011) .
INTRODUCTION
To our knowledge, Fernández & Galves (2002) provide the best explicit bounds in the literature for thed-distance between a chain of infinite order and its canonical Markov approximation, depending only on the continuity rate of the probability kernels. Their result applies to weakly non-null chains having summable continuity rates. Our method recovers the same bounds, substituting weak non-nullness by a weaker assumption, see Theorem 4.1. Assuming weak non-nullness, we also obtain explicit upper bounds in some non-summable continuity regimes and other not even necessarily continuous, but satisfying certain types of localized continuity, as introduced in De Santis & Piccioni (2010), Gallo (2011) and Gallo & Garcia (2011) . This is the content of Theorems 4.2 and 4.3 which provide, as far as we know, the first results for non-continuous chains. Our results should also be compared with the results in Johansson et al. (2010) , where they prove the Bernoulli property for square summable continuity regime assuming strong non-nullness, although they don't provide an explicit upper bound for the approximations.
INTRODUCTION
The paper is organized as follows. In Section 2, we introduce the notation and basic definitions used all along the paper. In Section 3, we construct the coupling between the original chain and its canonical Markov approximation and we introduce the class of CFTP algorithms perfectly simulating the chains. Our main results are stated in Section 4. We postpone the proofs to Section 5. For convenience of the reader, we leave in Appendix some extensions and technical results on the "house of cards" processes that are useful in our applications and are of independent interest.
NOTATION, DEFINITIONS AND BACKGROUND
2.1. Notation. We use the conventions that N * = N \ { 0 }, N = N * ∪ { ∞ }. Let A be the set { 1, 2, . . . , N } for some N ∈ N. Given two integers m ≤ n, let a n m be the string a m . . . a n of symbols in A. For any m ≤ n, the length of the string a n m is denoted by |a n m | and defined by n − m + 1. Let ∅ denote the empty string, of length |∅| = 0. For any n ∈ Z, we will use the convention that a n n+1 = ∅, and naturally |a n n+1 | = 0. Given two strings v and v , we denote by vv the string of length |v| + |v | obtained by concatenating the two strings. If v = ∅, then v∅ = ∅v = v. The concatenation of strings is also extended to the case where v = . . . a −2 a −1 is a semi-infinite sequence of symbols. If n ∈ N * and v is a finite string of symbols in A, v n = v . . . v is the concatenation of n times the string v. In the case where n = 0, v 0 is the empty string ∅. Let
NOTATION, DEFINITIONS AND BACKGROUND
be, respectively, the set of all infinite strings of past symbols and the set of all finite strings of past symbols. The case j = 0 corresponds to the empty string ∅. Finally, we denote by a = . . . a −2 a −1 the elements of A −N .
NOTATION, DEFINITIONS AND BACKGROUND
2.2. Kernels, chains and coupling.
NOTATION, DEFINITIONS AND BACKGROUND
Definition 2.1. A family of transition probabilities, or kernel, on an alphabet A is a function
NOTATION, DEFINITIONS AND BACKGROUND
P is called a Markov kernel if there exists k such that P (a|x) = P (a|y) when
NOTATION, DEFINITIONS AND BACKGROUND
−k . In the present paper we are mostly interested in non-Markov kernels, in which P (a|x) may depend on the whole past x. Definition 2.2. A stationary stochastic chain X = {X n } n∈Z with distribution µ on A Z is said to be compatible with a family of transition probabilities P if the later is a regular version of the conditional probabilities of the former, that is
NOTATION, DEFINITIONS AND BACKGROUND
for every a ∈ A and µ-a.e. x in A −N .
NOTATION, DEFINITIONS AND BACKGROUND
If P is non-Markov, it may be hard to prove the existence of a stationary chain X compatible with it. In order to solve this issue, we assume the existence of coupling from the past algorithms for the chain (see Section 2.3). This "constructive argument" garantees the existence and uniqueness of X.
NOTATION, DEFINITIONS AND BACKGROUND
Definition 2.3 (Canonical k-steps Markov approximation). Assume that X is a stationary chain with distribution µ. The canonical k-steps Markov approximation of X is the stationary k-step Markov chain X [k] compatible with the kernel P
NOTATION, DEFINITIONS AND BACKGROUND
[k]
NOTATION, DEFINITIONS AND BACKGROUND
µ defined as
NOTATION, DEFINITIONS AND BACKGROUND
Since µ is uniquely determined by P , we will not mention any more the subscript µ in P [k] µ , it will be understood that
NOTATION, DEFINITIONS AND BACKGROUND
µ . Let us recall that a coupling between two chains X and Y taking values in the same alphabet A is a stochastic chain Z = {Z n } n∈Z = {(X n ,Ȳ n )} n∈Z on (A × A) Z such thatX has the same distribution as X andȲ has the same distribution as Y. For any pair of stationary chains X and Y, let C(X, Y) be the set of couplings between X and Y. Definition 2.4 (d-distance). Thed-distance between two stationary chains X and Y is defined byd (X, Y) = inf
NOTATION, DEFINITIONS AND BACKGROUND
For the class of ergodic processes, this distance has another interpretation which is more intuitive: it is the minimal proportion of sites we have to change in a typical realization of X in order to obtain a typical realization of Y. Formally,
NOTATION, DEFINITIONS AND BACKGROUND
2.3. Coupling from the past algorithm (CFTP). Our CFTP algorithm constructs a sample of the stationary chain compatible with a given kernel P , using a sequence U = {U n } n∈Z of i.i.d. random variables uniformly distributed in [0, 1[. We denote by (Ω, F, P) the probability space associated to U. The CFTP is completely determined by its update function F : A −N ∪ A × [0, 1[→ A which satisfies that, for any a ∈ A −N and for any a ∈ A, P(F (a, U 0 ) = a) = P (a|a). Using this function, we define the set of coalescence times Θ and the reconstruction function Φ associated to F . For any pair of integers m, n such that −∞ < m ≤ n < +∞, let F {m,n} (a, U n m ) ∈ A n−m+1 be the sample obtained by applying recursively F on the fixed past a, i.e, let F {m,m} (a, U m ) := F (a, U m ) and
NOTATION, DEFINITIONS AND BACKGROUND
is called the set of coalescence times for the time index n. Finally, the reconstruction function of time n is defined by (1) For any k ∈ N, the Lebesgue measure or length |I k (a|a 
NOTATION, DEFINITIONS AND BACKGROUND
. . . Figure 1 . Illustration of a range partition related to some infinite past a. The upper partition is the one used for the original kernel P , whereas the one below is used for the approximating kernel P [k] .
NOTATION, DEFINITIONS AND BACKGROUND
Definition 3.1. We call range partitions the partitions of [0, 1[ satisfying (1), (2) and (3) for some kernel P .
NOTATION, DEFINITIONS AND BACKGROUND
The following lemma is proved in Section 5.1. Lemma 3.1. A set of range partitions satisfies, for any a and a ∈ A,
NOTATION, DEFINITIONS AND BACKGROUND
Given a range partition I(a), the following F is an update function, due to property (2).
NOTATION, DEFINITIONS AND BACKGROUND
This function F explains the name "range partition": for a given past a, when the uniform r.v. U 0 belongs to a∈A
NOTATION, DEFINITIONS AND BACKGROUND
L associates to a past a and a real number u ∈ [0, 1[ the length of the suffix of a that F needs in order to construct the next symbol when U 0 = u. Using these functions, define, as in Section 2.3, the related coalescence sets Θ[i], i ∈ Z, and the reconstruction function Φ(U), which is distributed according to the unique stationary distribution compatible with P whenever Θ[0] is a.s. non-empty.
NOTATION, DEFINITIONS AND BACKGROUND
Let us now define the functions F [k] and L [k] that we will use for the construction of X [k] . Observe that, on the one hand, by definition of the canonical k-steps Markov approximation we have for any a ∈ A and a
NOTATION, DEFINITIONS AND BACKGROUND
On the other hand, by Lemma 3.1, inf z P (a|a
NOTATION, DEFINITIONS AND BACKGROUND
Thus we can define, for any a
NOTATION, DEFINITIONS AND BACKGROUND
−k )| and disposed as in Figure 1 . The functions F [k] and L [k] are defined as follows
NOTATION, DEFINITIONS AND BACKGROUND
and
NOTATION, DEFINITIONS AND BACKGROUND
Using these functions, define, as in Section 2.3, the related coalescence sets
NOTATION, DEFINITIONS AND BACKGROUND
and the reconstruction function Φ [k] (U), which is distributed according to the unique stationary distribution compatible with
NOTATION, DEFINITIONS AND BACKGROUND
Using the same sequence of uniforms U and assuming that Θ[0] and
NOTATION, DEFINITIONS AND BACKGROUND
) is a coupling between both chains. Hence, we have constructed a CFTP algorithm for perfect simulation of the coupled chains.
STATEMENTS OF THE RESULTS

4.1.
A key lemma. Let us first state a technical lemma that is central in the proof of our main results.
4.1.
Lemma 4.1. Assume that there exists a set of range partitions {I(a)} a such that the sets of coalescence times
4.1.
where
4.1.
Examples of range partitions satisfying the conditions of this theorem have already been built, for example in Comets et al. (2002) , Gallo (2011) , Gallo & Garcia (2011) and De Santis & Piccioni (2010) . These works assume some regularity conditions on P and some non-nullness hypothesis which are presented in Sections 4.2, 4.3, 4.4. In these sections, we derive explicit upper bounds for (9) under the respective assumptions. Before that, let us give an interesting remark on Bernoullicity.
4.1.
Observation 4.1 (A remark on Bernoullicity). In the conditions of each works cited above, we will exhibit θ[0] ∈ Θ[0] which belongs to Θ [k] [0] for any sufficiently large k's, and we will prove that
4.1.
It follows, by Lemma 4.1, that
4.1.
We also have, for any sufficiently large k's, that X [k] is an ergodic Markov chain since
4.1.
is non-empty. Now, by thed-closure of the set of processes isomorphic to a Bernoulli shift (see for example Shields (1996) Theorem IV.2.10, p.228) and the fact that ergodic Markov processes have the Bernoulli property (Shields (1996) Theorem IV.2.10, p.227), we conclude that the processes considered in Comets et al. (2002) , Gallo (2011) , Gallo & Garcia (2011) and De Santis & Piccioni (2010) have the Bernoulli property.
4.1.
4.2. Kernels with summable continuity rate. Let us first define continuity.
4.1.
Definition 4.1 (Continuity points and continuous kernels). For any k ∈ N, a and a
4.1.
A past a is called a continuity point for P or P is said to be continuous in a if
4.1.
We say that P is continuous when
4.1.
We say that P has summable continuity rate when k≥0 (1 − α k ) < ∞.
4.1.
Let us also define weak non-nullness.
4.1.
Definition 4.2. We say that a kernel P is weakly non-null if α 0 > 0, where α 0 := a∈A α 0 (a|∅). De Santis & Piccioni (2010) have introduced a more general assumption that we call very weak non-nullness, see Definition 5.2. We postpone this definition to Section 5.3 in order to avoid technicality at this stage.
4.1.
Theorem 4.1. Assume that P has summable continuity rate and is very weakly non-null. Then, there exists a constant C < +∞ such that, for any sufficiently large k,
4.1.
Remark 4.1. This upper bound is new since we do not assume weak non-nullness. Fernández & Galves (2002) showed, under weak non-nullness, that for any sufficiently large k, there exists a positive constant C such that
4.1.
This later quantity is related to α k through the inequalities 1−α k ≥ |A| 2 β k and 1−α k ≤ Dβ k for some D > 1 and sufficiently larges k's. Moreover, 1 − α k = β k for binary alphabets. Thus, Theorem 4.1 extends the bound in Fernández & Galves (2002) . 
4.1.
Theorem 4.2. If X has a kernel that satisfies
4.1.
. In order to illustrate the interest of this result, let us give two simple examples. Other examples can be found in De Santis & Piccioni (2010) and Gallo & Garcia (2011) .
4.1.
Summable continuity regime with weak non-nullness. Theorem 4.2 allows to recover the result of Theorem 4.1 in the weakly non-null case. To see this, it is enough to observe that, for any U
4.1.
is bounded away from zero, hence, its inverse has finite expectation. Hence, Theorem 4.2 applies and givesd (X,
4.1.
A simple discontinuous kernel on A = {1, 2}. Let ∈ (0, 1/2) and let {p i } i≥0 be any sequence such that, ≤ p i < 1 − for any i ≥ 0. Let t(a) := inf{i ≥ 0 : a −i−1 = 2} letP be the following kernel:
4.1.
The existence of a unique stationary chain compatible with this kernel is proven in Gallo (2011) for instance. This chain is the renewal sequence, that is, a concatenation of blocks of the form 1 . . . 12 having random length with finite expectation. It is clearly weakly non-null, however, it is not necessarily continuous. In fact, a simple calculation shows that α k = 1 − sup l,m≥k |p l − p m |, which needs not to go to 1. Nevertheless, if we assume Santis & Piccioni (2010) . We now want to derive an upper bound for
4.1.
Observation 4.2. The preceding theorems yield explicit upper bounds. However, they hold under restrictions we would like to surpass. First, in the continuous regime, we have assumed that k≥0 (1 − α k ) < +∞. Nevertheless, CFTP are known to exist with the weaker assumption k≥1 k−1 i=0 α i = +∞, and it is known thatd(X, X [k] ) goes to zero in this case. We will be interested in upper bounds for the rate of convergence to zero under these weak conditions. Second, in Theorem 4.2, the assumption
4.1.
< ∞ is generally difficult to check: this is particularly clear for the example ofP where it requires the (not necessary) extra-assumption sup k≥0 α k > 1 − 2α(1)α(2).
4.1.
The next section will solve part of these objections.
4.4.
A simple upper bound under weak non-nullness. Hereafter, we assume that P is weakly non-null. Let Θ [0] be the following subset of Θ[0]:
4.4.
We have the following theorem in which a priori nothing is assumed on the continuity.
4.4.
Theorem 4.3. Assume that P is weakly non-null and that we can construct a set of range partitions {I(a)} a for which
4.4.
In order to illustrate this result, let us consider the examples of continuous kernels and of the kernelP . Gallo & Garcia (2011) proposed a unified framework, including these examples and several other cases, which provides more examples of applications of this theorem. This is postponed to Appendix A in order to avoid technicality.
4.4.
Application to the continuity regime. Let us first introduce the following range partition.
4.4.
Definition 4.3. Let {I (1) (a)} a be the range partition such that, for any a and a ∀k ≥ 0, I
4.4.
(1)
4.4.
(1)
4.4.
with the convention α −1 (a|∅) = 0.
4.4.
Let F (1) and L (1) be the associated functions defined in (5) and (6). Let
4.4.
, the set defined by (13) using F (1) and L (1) . Moreover, Comets et al. (2002) proved that, if k≥1 k−1 i=0 α i = +∞ (that is, under weak non-nullnes but not necessarily summable continuity)
4.4.
which goes to 0. This upper bound is not very satisfactory since it is difficult to handle in general. Nevertheless, Propositions B.1 and B.2, given in Appendix B, shed light on the behavior of this vanishing sequence. In particular, under the summable continuity assumption k≥0 (1 − α k ) < +∞, Proposition B.1 states that (15) essentially recovers the rates of Theorems 4.1 and 4.2. Also, if there exists a constant r ∈ (0, 1) and a summable sequence (s k ) k≥1 such that, ∀k ≥ 1, 1 − α k = r k + s k , then, from Proposition B.2, there exists a positive constant C such that
4.4.
Application to the kernelP . As a second direct application of Theorem 4.3, let us consider the kernelP defined in (12). Let {I (2) (a)} a be the set of range partitions, such that |I (2) (2|∅)| = α(2), |I (2) (1|∅)| = α(1) and I
4.4.
(2)
4.4.
is defined by (13) with the functions F (2) and L (2) obtained from the set of range partitions {I (2) (a)} a ). Therefore,
4.4.
independently of the value sup k≥0 α k . For this simple example, Theorem 4.3 is then less restrictive than Theorem 4.2.
PROOFS OF THE RESULTS
5.1. Proof of Lemma 3.1. Assume that for some k ≥ 0 we have
PROOFS OF THE RESULTS
This is a contradiction with the second properties of the partition. This concludes the proof.
PROOFS OF THE RESULTS
5.2. Proofs of Lemma 4.1. We assume that Θ[0] ∩ Θ [k] [0] is P-a.s. non-empty, and we therefore have a coupling (Φ(U), Φ [k] (U)) of both chains. By definitions of F [k] and L [k] , we observe that when
5.3.
Proof of Theorem 4.1. This section is divided in three parts. First, as mentioned before the statement of the theorem, we define very weak non-nullness. Then, we prove some technical lemmas allowing to apply Lemma 4.1. Finally, we prove the theorem.
5.3.
5.3.1. Definition of very weak non-nullness. Consider the set of range partitions {I (1) (a)} a of Definition 4.3. As observed by De Santis & Piccioni (2010) , in the continuous case, since {α k } k≥0 increases monotonically to 1, there exists k ≥ 0 such that α k > 0. Let k be the smallest of these integers and let F be the following update function
5.3.
In the case where k = 0, F is simply defined as
5.3.
Definition 5.1 (Coalescence set). For m ≥ k + 1, let E m , the coalescence set (different from the set of coalescence times), be defined as the set of all u 0 −m+1 ∈ A m such that
5.3.
When k = 0 and m = 1, we have E 1 := ∪ a∈A I 0 (a|∅).
5.3.
Definition 5.2. We say that P is very weakly non-null if
5.3.
Weak non-nullness corresponds to P(U 0 ∈ E 1 ) > 0, hence, it implies very weak nonnullness.
Technical lemmas. Let Θ (1)
[0] be the set of coalescence times defined by (3) for the function F (1) . In a first part of the proof, we define a random time θ[0] (see (20)) and we show that it belongs to Θ (1) [0] and that it has finite expectation whenever k≥k (1−α k ) < +∞. This random variable is defined in the proof of Theorem 2 in De Santis & Piccioni (2010).
Technical lemmas. Let Θ (1)
Recall that, by construction of the range partition {I (1) (a)} a , for any a, L(a, U i ) = k whenever α k−1 ≤ U i < α k . This means that the sequence of ranges forms a sequence {L i } i∈Z := {L(a, U i )} i∈Z of i.i.d. N-valued r.v.'s. We now introduce two sequences of random times in the past, which are represented on Figure 2 , in the particular case where k = 2. Let W 1 := sup{m ≤ 0 : U j < α j−m+k , j = m, . . . , 0}, and for any i ≥ 1
Consider now the random variable
(see Definition 5.1 for E m ) and put
Consider now the random variable
We consider a realization of L 0 −∞ in the particular case k = 2, that is, the arrows, which represent the length function at each time index, have length larger or equal to 2.
Consider now the random variable
. . , k, it follows that
Consider now the random variable
is independent of b.
Consider now the random variable
By definition of the random times W i , all the symbols in times { W Q , . . . , 0 } can then be built using those in times { W Q − k , . . . , W Q − 1 } since none of the arrows from time W Q until 0 go further time W Q − k , see the Figure 2 . Therefore, the construction of the symbol at times 0 does not depend on the symbols before
Consider now the random variable
Proof. Lettingᾱ l−k = α l for any l ≥ k , we have
Consider now the random variable
Thus W 1 is defined exactly as τ [0] of display (4.2) in Comets et al. (2002) , substituting their a k 's by ourᾱ k 's. They proved (see display (4.6) and item (ii) Proposition 5.1 therein) that E|τ [0]| < +∞ whenever k≥0 (1 −ᾱ k ) < +∞. It follows that E|W 1 | < +∞ whenever 
Consider now the random variable
We finally need the following lemma. [k] and L (1), [k] satisfy (18). This implies that, in the interval {Y Q , . . . , W Q − 1}, coalescence occurs as well for
Consider now the random variable
. Both constructed chains are equals until the first time F (1) uses a range larger than k. But at this moment, due to the definition of the W i 's, we have already perfectly simulated at least k symbols of both chains, and therefore, we can continue constructing until time 0 because the ranges of F (1), [k] are smaller of equal to k. It follows that Y Q is a coalescence time for F (1), [k] , and therefore, θ[0] ∈ Θ (1), [k] [0] for any k ≥ k . 5.3.3. Proof of Theorem 4.1. By definition of F (1) and L (1) , we have for any sufficiently large k,
Consider now the random variable
By Lemmas 5.1 and 5.4, Lemma 4.1 applies and gives, for sufficiently large k's
Consider now the random variable
where we used the Markov inequality for the last inequality. Using the fact that θ[0] is a stopping time in the past for the sequence U i , i ≤ 0, and that it has finite expectation by Lemma 5.3, we can apply the Wald's equality to obtain
Consider now the random variable
5.4. Proof of Theorem 4.2. We divide this proof into two parts. First, we prove technical lemmas allowing to use Lemma 4.1. Then, we prove the theorem. 
Consider now the random variable
Proof. For any U −1 −k , the way the sets of strings {zF
Consider now the random variable
−k ) are defined ensure that the former is included in the later. It follows that, for any U
Consider now the random variable
As the inequality A 0 ≤ a∈A inf z P (a|z) is also true, we deduce that, for any k ≥ 0, any 
Consider now the random variable
We now have the following sequence of inclusions
Consider now the random variable
This concludes the proof of the lemma.
Consider now the random variable
Recall the definition (13) of Θ [0] for generic range partitions of a weakly non-null kernel P . We will need the following lemma. 
Consider now the random variable
for any k ≥ 0. Thus we can apply Lemma 4.1, and obtain, using Lemma 5.5
Consider now the random variable
Consider the σ-algebra F k generated by U 0 −k , k ≥ 0. Then, (U 0 −∞ ) is a stopping time with respect to F k and, by definition, so is θ[0]. Moreover, (U i −∞ ) is independent of U 0 i+1 by independence of the U j 's. Finally, by stationarity,
Consider now the random variable
has finite expectation, hence we can use Wald equality to obtain
Consider now the random variable
This concludes the proof of Theorem 4.2. 
Consider now the random variable
By Lemma 5.6, any θ[0] ∈ Θ [0] also belongs to Θ [k] [0] for any k ≥ 0. We can thus apply Lemma 4.1 and conclude the proof of the theorem.
Consider now the random variable
with countable alphabets, and discontinuities in more complicated set of pasts. To begin, we need the following definition.
Consider now the random variable
Definition A.1 (Local continuity with respect to the past 1). We say that a kernel P on {1, 2} is locally continuous with respect to the past 1 if ∀i ≥ 0, inf
Consider now the random variable
converges to 1 as k diverges. We distinguish two particular situations of interest.
Consider now the random variable
• We say that P is strongly locally continuous with respect to 1 if there exists an integer function : N → N such that ∀i ≥ 0, inf
Consider now the random variable
for any k ≥ (i), and • we say that P is uniformly locally continuous with respect to 1 if
Consider now the random variable
converges to 1 as k diverges.
Consider now the random variable
Strongly locally continuous kernels are known as probabilistic context trees, a model that have been introduced by Rissanen (1983) as a universal data compression model. It was first consider, from the "CFTP point of view", by Gallo (2011) . The kernelP is a simple example which is strongly and uniformly locally continuous with respect to 1.
Consider now the random variable
Assumption 1: P is strongly locally continuous with respect to 1.
Consider now the random variable
Assumption 2: P is uniformly locally continuous with respect to 1. Notation A.1. Let us introduce the following notation.
Consider now the random variable
• Stationary chains compatible with kernels satisfying Assumptions i=1 and 2 are denoted X (i) , and the corresponding canonical k-steps Markov approximations are denoted X (i), [k] .
Consider now the random variable
• We use the notations r (i) 0 := α 0 for i=1 and 2, and for k ≥ 1, r (2)) where and α 1 k are the parameters of the kernels under assumptions 1 and 2 respectively.
Consider now the random variable
• For i=1 and 2
Consider now the random variable
where −1 l=0 := 1.
Consider now the random variable
• And finally, for any k ≥ 0, let
Consider now the random variable
It is well-known that this sequence goes exponentially fast to 0 (see Kallenberg (2002) for instance). An explicit upper bound is derived in Appendix C.
Consider now the random variable
Corollary A.1. Under the weak non-nullness assumption, we have for i=1 and 2 that, if
Consider now the random variable
The quantity defined on display (26) is related to the house of card process presented in Section B (see equation (30)). We provide in Propositions B.1 and B.2 explicit upperbounds on the term (26) that can be plugged in (28). The term (27) is studied in Corollary C.1. It follows in particular from these propositions that, whenever r (i) k is not exponentially decreasing, the leading term in (28) is v (i) k , and therefore, we obtain for some constant C > 1 and any sufficiently large k
Consider now the random variable
For instance, Proposition B.2, states that, if 1 − r
Consider now the random variable
with r ∈ (0, 1) and {s k } k≥1 is any summable sequence, we obtain for some constant C > 1
Consider now the random variable
Proof. Under Assumptions 1 and 2 with weak non-nullness, Gallo & Garcia (2011) 
Consider now the random variable
kα(2)/2 (where {u
Consider now the random variable
k } k≥1 has been defined by (27) ). This is in fact stated in the proof of item (ii) of Theorem 5.2 therein.
Consider now the random variable
By Theorem 4.3, these upper bounds are therefore upper bounds for thed-distancē d(X, X [k] ).
Appendix B. Some results on the House of Cards Markov chain
Fix a non-decreasing sequence {r k } k≥0 of [0, 1]-valued real numbers converging to 1. The house of Cards Markov chain H = {H n } n≥0 related to this sequence is the N-valued Markov chain starting from state 0 and having transition matrix Q = {Q(i, j)} i≥0, j≥0 where Q(i, j) := r i 1{j = i + 1} + (1 − r i )1{j = 0}. Let us denote v k := Pr(H k = 0), the probability that the house of cards is at state 0 at time k. We want to derive explicit rates of convergence to 0 of this sequence when H is not positive recurrent. These results will be used in the next section in order to obtain explicit upper bounds ford(X, X [k] ) under several types of assumptions. Decomposing the event { H k = 0 } into the possible come back of the process {H } =0,...,k to 0 yields, for any n ≥ 1
Appendix B. Some results on the House of Cards Markov chain
where −1 l=0 := 1. Although explicit, this bound cannot be used directly and has to be simplified. As a first insight, we borrow the following Proposition of Bressaud et al. (1999) .
Appendix B. Some results on the House of Cards Markov chain
) ≤ 1 (iv) v k goes to zero exponentially fast if 1 − r k decreases exponentially.
Appendix B. Some results on the House of Cards Markov chain
As observe in Bressaud et al. (1999) , the conditions of item (iii) are satisfied if, for example, 1 − r (i) k ∼ (log k) η k −ζ for some ζ > 1, and for any η. However, this is one of the only cases in which this proposition yields explicit rates. In the present paper, we will prove the following proposition.
Appendix B. Some results on the House of Cards Markov chain
Proposition B.2. We have the following explicit upper bounds.
Appendix B. Some results on the House of Cards Markov chain
(i) A non summable case: if 1 − r k = r k + s k , k ≥ 1 where r ∈ (0, 1) and {s n } n≥1 is a summable sequence, there exists a constant C > 0 such that
Appendix B. Some results on the House of Cards Markov chain
(ii) Generic summable case: if t ∞ := k≥0 r k > 0, then
Appendix B. Some results on the House of Cards Markov chain
(iii) Exponential case: if 1 − r k ≤ C r r k , k ≥ 1, for some r ∈ (0, 1) and a constant C r ∈ (0, log
Appendix B. Some results on the House of Cards Markov chain
B.1. Proof of Proposition B.2. Before we come into the proofs of each item of this proposition, let us collect some simple remarks on the House of Cards Markov chain. Let {T k } k≥0 be a sequence of the stopping times defined as T 0 := 0 and, recursively, for any k ≥ 1, T k := inf { l ≥ T k−1 + 1 s.t. H l = 0 }. The Markov property ensures that the random variables I k := T k+1 − T k are i.i.d., valued in N * and it is easy to check that
Appendix B. Some results on the House of Cards Markov chain
where −1 l=0 := 1. We have, for any n ≥ 0,
Appendix B. Some results on the House of Cards Markov chain
We write T k = k−1 l=0 I l . As all the I l ≥ 1, we have Pr (T k = n) = 0 for all k > n. Therefore, for all K ∈ [1, n],
Appendix B. Some results on the House of Cards Markov chain
In order to control K k=0 Pr (T k = n) = Pr (∃k = 0, . . . , K, T k = n), we can simply remark that, if there exists k ∈ 1, . . . K such that k i=1 I l = n, there exists necessarily i ∈ [1, K] and r ∈ [1, . . . , K] such that I i = n/r. This implies that
Appendix B. Some results on the House of Cards Markov chain
We have obtain the following result.
Appendix B. Some results on the House of Cards Markov chain
Restricting our attention to the summable case (that is, when k≥0 (1 − r k ) < +∞), the following fact is fundamental. Its proof is immediate.
Appendix B. Some results on the House of Cards Markov chain
Using Facts B.1, B.2 and B.3, we are ready to prove items (i) and (ii) of Proposition B.2.
Appendix B. Some results on the House of Cards Markov chain
Proof of Item (i) of Proposition B.2. As far as we know, all the results on the house of card process hold in the summable case. When k∈N (1 − r k ) = ∞, it is only known that n∈N Pr (H n = 0) = ∞. It is interesting to notice that we can still obtain some rate of convergence for Pr (H n = 0) from our elementary facts, at least in the following example. Let us assume that there exists r < 1 and a summable sequence s n such that, for all n ≥ 1, 1 − r n = r n + s n . In this case, we have n∈N (1 − r n ) = ∞, therefore t ∞ = 0. Nevertheless,
Appendix B. Some results on the House of Cards Markov chain
Therefore t n ≤ Cn −(1+r) . Moreover, using the inequality (1 − u) ≥ e −u−u 2 , valid for all u < 1/8, we see that t n ≥ cn −(1+r) . Therefore, ν n = k≥n t k ≥ cn −r . It follows from Fact B.1 that, for large K and n,
Appendix B. Some results on the House of Cards Markov chain
Using Fact B.1, we also have
Appendix B. Some results on the House of Cards Markov chain
We deduce then from (31) that, for all K ∈ [0, n],
Appendix B. Some results on the House of Cards Markov chain
For K = 2n r ln n, we obtain Pr (H n = 0) ≤ C (ln n) 3+r n 1−2r−r 2 = C (ln n) 3+r n 2−(1+r) 2 . If 0 < r < 1, we have 2−(1+r) 2 > 0. This bound may not be optimal, but it is interesting to see that we still can derive rates of convergence from our basic remarks even in this pathological example.
Appendix B. Some results on the House of Cards Markov chain
Proof of Item (ii) of Proposition B.2. We deduce from Facts B.1 and B.3 that, in the summable case
Appendix B. Some results on the House of Cards Markov chain
Therefore, from Facts B.2 and B.3,
Appendix B. Some results on the House of Cards Markov chain
Proof of Item (iii) of Proposition B.2. In this section, we assume that, for all k, 1 − r k ≤ C r r k , for some r ∈ (0, 1) and a constant C r > 0. In that case, for all k, we have, by independence,
Appendix B. Some results on the House of Cards Markov chain
Let us evaluate the numbers p k,n = i 1 +...+i k =n 1. We have p 1,n = 1 and
Appendix B. Some results on the House of Cards Markov chain
Let us then assume that, for some k, we have, for all n ≥ k − 1,
Appendix B. Some results on the House of Cards Markov chain
Notice that this is the case for k = 2, then, for all n ≥ k,
Appendix B. Some results on the House of Cards Markov chain
We deduce that Pr (T k = n) ≤ 1 C r (e Cr r) n .
Appendix B. Some results on the House of Cards Markov chain
Hence, when C r < ln(1/r), e Cr r < 1 and Pr (H n = 0) decreases exponentially fast.
Appendix B. Some results on the House of Cards Markov chain
Appendix C. Concentration of geometric random variables Let ξ, ξ 1:n be i.i.d. geometric random variables with parameter α, i.e., ∀k ≥ 1, P ( ξ = k ) = (1 − α) k−1 α. We obtain in this section the following upper bounds. 
Appendix B. Some results on the House of Cards Markov chain
As a corollary of this result, we obtain the following bound when n = kα/2 and x = 1/α. Corollary C.1. Let k ∈ N * , α ∈ (0, 1), n = kα/2 , x = k/(2n) ≥ 1/α, ξ 1:n be i.i.d. random variables with parameters α, and C.1. Chernov's bound. Let Y, Y 1:n be i.i.d. random variables such that ∀a < λ < b, E e λY < ∞, then,
Appendix B. Some results on the House of Cards Markov chain
Proof. We have, by independence of the Y i and Markov's inequality, for all na < λ < nb,
Appendix B. Some results on the House of Cards Markov chain
C.2. Exponential moments of geometric random variables. Let ξ be a geometric random variable with parameter α, then ∀λ < − ln(1 − α), E e λξ ≤ αe λ 1 − (1 − α)e λ ,
Appendix B. Some results on the House of Cards Markov chain
∀λ > ln(1 − α), E e λ(−ξ) ≤ αe −λ 1 − (1 − α)e −λ .
Appendix B. Some results on the House of Cards Markov chain
Proof. By definition, we have, ∀λ < − ln(1 − α), (35), we obtain, for all λ < −n ln(1 − α), (35), we obtain, for all λ > n ln(1 − α), 

{'paper_id': '54647479', 'title': 'Markov Approximations of chains of infinite order in the $\\bar{d}$-metric', 's2_url': 'https://api.semanticscholar.org/CorpusID:54647479', 'source': 'S2ORC'}