Markov approximations of chains of infinite order (Q1416103)

Consider a stochastic process \((X_n)\) which takes values in a finite alphabet \(\mathcal A\). Let \(x_k^n\) be the sequence \(x_k, \dots, x_n\), similarly \(y_{n+1}^m x_k^n\) the sequence \(x_k,\dots, x_n, y_{n+1}, \dots, y_m\), and \({\mathcal A}_k^n\) the set of sequences \(x_k^n\). Define the continuity rate \[ \beta(s)=\sup_n \sup_{x,y} | P_n(x_n\mid x_{-\infty}^{n-1}) - P_n(x_n\mid x_{n-s}^{n-1} y_{-\infty}^{n-s-1})|, \] where \(P_n\) is the transition probability. A system of transition probabilities is continuous if \(\beta(s)\to 0\) as \(s\to\infty\). The system is weakly non-null if \(\inf_n \sum_{y_n\in{\mathcal A}} \inf_x P_n(y_n\mid x_{-\infty}^{n-1}) >0\). A stochastic process is a chain of infinite order of type A if it is consistent with a system of transition probabilities that is continuous and weakly non-null. The canonical Markov approximation of order \(k\) of a process \((X_n)\) is the Markov chain \((X_n^{[k]})\) having transition probabilities \[ P_n^{[k]}(a\mid x_{n-k}^{n-1})= P(X_n=a\mid X_{n-k}^{n-1} = x_{n-k}^{n-1}). \] The main result of the paper is the derivation of an upper bound of Ornstein's \(\bar d\)-distance between a chain of infinite order and its canonical Markov approximation of any given order. It is shown that the \(\bar d\)-distance is at worst proportional to the continuity rate of the chain.