Generalized Ordinal Patterns and the KS-Entropy

Abstract

Ordinal patterns classifying real vectors according to the order relations between their components are an interesting basic concept for determining the complexity of a measure-preserving dynamical system. In particular, as shown by C. Bandt, G. Keller and B. Pompe, the permutation entropy based on the probability distributions of such patterns is equal to Kolmogorov–Sinai entropy in simple one-dimensional systems. The general reason for this is that, roughly speaking, the system of ordinal patterns obtained for a real-valued “measuring arrangement” has high potential for separating orbits. Starting from a slightly different approach of A. Antoniouk, K. Keller and S. Maksymenko, we discuss the generalizations of ordinal patterns providing enough separation to determine the Kolmogorov–Sinai entropy. For defining these generalized ordinal patterns, the idea is to substitute the basic binary relation ≤ on the real numbers by another binary relation. Generalizing the former results of I. Stolz and K. Keller, we establish conditions that the binary relation and the dynamical system have to fulfill so that the obtained generalized ordinal patterns can be used for estimating the Kolmogorov–Sinai entropy.

1. Introduction

In 2002, Bandt and Pompe introduced so-called permutation entropy [1]. This entropy has been established in non-linear dynamical system theory and time series analysis, including applications in many fields from biomedicine to econophysics (compare with Zanin et al. [2]). It is a crucial point that permutation entropy is theoretically justified by asymptotic results relating it to Kolmogorov–Sinai entropy (KS entropy, also called metric entropy) which is the central complexity measure for dynamical systems. The important relationship of permutation entropy and KS entropy was first observed and mathematically founded for piece-wise monotone dynamical systems by Bandt et al. [3].

The (empirical) concept of permutation entropy is based upon analyzing the distribution of ordinal patterns in a time series or the underlying system. In this paper, we concentrate on a measure-preserving dynamical system $(\Omega ,\mathcal{A},\mu ,T)$, i.e., a probability space $(\Omega ,\mathcal{A},\mu )$ equipped with a measurable map $T:\Omega \to \Omega$ satisfying $\mu \left(T^{-1}\left(A\right)\right)=\mu \left(A\right)$ for all $A\in \mathcal{A}$.

Given a random variable $X:\Omega \to \mathbb{R}$, in this paper, an ordinal pattern of length$n\in \mathbb{N}$ with respect to X is considered as a subset of the state space $\Omega$. It is indicated by a permutation $\mathbf{\pi }=({\pi }_0,{\pi }_1,\dots ,{\pi }_{n-1})$ of $\{0,1,\dots ,n-1\}$ and defined by

$$P_{\mathbf{\pi }}:=\{\omega \in \Omega \mid X\left(T^{{\pi }_0}\left(\omega \right)\right)\le X\left(T^{{\pi }_1}\left(\omega \right)\right)\le \dots \le X\left(T^{{\pi }_{n-1}}\left(\omega \right)\right)\}.$$

(1)

(Usually, ordinal patterns are defined in the range of X, i.e., for the vectors $(X\left(T\left(\omega \right)\right),X\left(T^1\left(\omega \right)\right),\dots ,X\left(T^{n-1}\left(\omega \right)\right))$). The collection of ordinal patterns:

$$O{P}_{}\left(n\right):=\{P_{\mathbf{\pi }}\mid \mathbf{\pi }\mathrm{is}\mathrm{a}\mathrm{permutation}\mathrm{of}\mathrm{length}n\}$$

is a partition of $\Omega$.

In the rest of this section, we assume that X preserves enough information about the given system in a certain sense. This is particularly the case if $\Omega$ is contained in $\mathbb{R}$ and X is the identity map. A precise general description of the assumption is given when presenting the results of this paper. It was shown in [4] that, under not too restrictive further conditions, the probability distribution on the partitions $O{P}_{}\left(n\right)$ for $n\in \mathbb{N}$ can be used for determining the KS entropy of the given system. The reason is that, roughly speaking, under these conditions, $O{P}_{}\left(n\right)$ is able to separate the orbits of the system if $n\to \infty$.

In order to address the problem that this paper is concerned with, we give a description of ordinal patterns being slightly different from the above. One can determine to which ordinal pattern $P_{\mathbf{\pi }}$ of length n a point $\omega$ belongs to if, for all $(s,t)$ in:

$$E_n=\{(s,t)\in {\mathbb{N}}_0^2\mid 0\le s<t\le n-1\},$$

(2)

one knows whether $X\left(T^s\left(\omega \right)\right)\le X\left(T^t\left(\omega \right)\right)$ holds true or not. In other words, there exists a set $A\subseteq E_n$ such that:

$$\begin{array}{cc}\hfill P_{\mathbf{\pi }}=& \bigcap _{(s,t)\in A}\{\omega \in \Omega \mid (X\left(T^s\left(\omega \right)\right),X\left(T^t\left(\omega \right)\right))\in R\}\hfill \\ \hfill \cap & \bigcap _{(s,t)\in E_n\backslash A}\{\omega \in \Omega \mid (X\left(T^s\left(\omega \right)\right),X\left(T^t\left(\omega \right)\right))\in {\mathbb{R}}^2\backslash R\},\hfill \end{array}$$

(3)

where:

$$R:=\{(x,y)\in {\mathbb{R}}^2\mid x>y\}.$$

(4)

The above set contains all the points $\omega \in \Omega$ that satisfy $X\left(T^s\left(\omega \right)\right)>X\left(T^t\left(\omega \right)\right)$ for $(s,t)\in A$ and $X\left(T^s\left(\omega \right)\right)\le X\left(T^t\left(\omega \right)\right)$ for $(s,t)\in E_n\backslash A$. Note that, given some arbitrary $A\subseteq E_n$, the set on the right hand side of (3) can be empty. In the case that it is non-empty, it coincides with some ordinal pattern $P_{\mathbf{\pi }}$ of length n.

While Equation (3) might be a bit more abstract than (1), it shows a way to generalize the concept of ordinal patterns on the basis of replacing the set R in (4) by some arbitrary Borel subset R of ${\mathbb{R}}^2$, also to investigate why ordinal patterns are so successful.

Definition 1.

We call a non-empty Borel subset R of ${\mathbb{R}}^2$ discriminating relation.

The figures given in this paper show different discriminating relations R. In each case, only the part of R contained in ${[0,1[}^2$ is presented. Note that in the case that X maps $\Omega$ into $[0,1[$, the restriction of R itself to this part would not change anything. Figure 1a illustrates R as given in (4), again only on ${[0,1[}^2$. In the case of such an R, note that $tan\left(\pi \right(X-1/2\left)\right)$ mapping $[0,1[$ into $[-\infty ,\infty [$ would not make a difference to a given X for our considerations, since order relations and associated partitions are preserved.

Given some discriminating relation, generalized ordinal patterns of length n with respect to X are given as the non-empty sets defined by the right hand side of (3) for some $A\subseteq E_n$. Obviously, they also form a partition of $\Omega$. The question that arises is what a discriminating relation R should look like, such that those generalized ordinal patterns inhibit the same nice properties the original ordinal patterns had. More precisely, we ask the following question:

Main Question.

Under what conditions on a discriminating relation R the partitions given by the generalized ordinal patterns determine the KS entropy of a dynamical system?

Why is this determination of entropy, which is precisely described by formula (10) in Theorem 1 interesting? For answering this question, interpret X as an observable, $\omega$ as the initial state of the given system and $X\left(\omega \right),X\left(T\left(\omega \right)\right),X\left(T^2\left(\omega \right)\right),X\left(T^3\left(\omega \right)\right),\dots$ as the measured values at times $0,1,2,3,\dots$. Determining (generalized) ordinal patterns on the basis of those values is a symbolization, where a symbol obtained is the (generalized) ordinal pattern containing $\omega$. Generally, symbolization means a coarse-graining of the state space underlying a system, where each point is assigned one of finitely many given symbols. Instead of considering the precise development of the system, one is interested in the change of symbols in the course of time, justifying the naming of the method symbolic dynamics. Note that a symbolization is equivalent to partitioning the state space into classes of states (with the same symbol).

The reason for obtaining the full entropy from the (generalized) ordinal patterns is, roughly speaking, that the symbol system obtained has high potential for separating orbits. Such kinds of successful symbolizations are important, for example, in big data analysis, see, e.g., Smith et al. [5].

The above question was first considered in [6], where the authors basically showed that sets of the form:

$$R=\{(x,y)\in {\mathbb{R}}^2\mid g\left(x\right)\ge y\}$$

lead to generalized ordinal patterns that, under some conditions, can be used to determine the entropy if $g:\mathbb{R}\to \mathbb{R}$ is measurable and one-to-one. Such an R is shown in Figure 1b and will be discussed in Section 4 as well as another R illustrated in Figure 1.

In this paper, we consider general sets $R\subseteq {\mathbb{R}}^2$ that cannot necessarily be described by functions and inequalities and establish some conditions under which the entropy can be determined using those sets. As in [6], the discussion also includes a generalization of the sets $E_n$ given by (2) and is conducted in a multidimensional framework. In particular, the results give insights as to why the basic ordinal approach and generalizations are working.

It is instructive to discuss the partition of ${\mathbb{R}}^2$ into R and ${\mathbb{R}}^2\backslash R$ from the viewpoint of symbolic dynamics. In contrast to classical symbolization approaches with symbolizing only in the range of single “measurements” x, the symbolization of pairs $(x,y)$ via the partition $\{R,{\mathbb{R}}^2\backslash R\}$ also regards some kind of link between x and y if R lies “diagonal” in a certain sense. We will discuss this constellation, which explains the success of ordinal patterns in a wider context, more precisely in Section 5.

A completely different constellation is given for the sets R shown in Figure 2. Here, R is obtained as a half-plane from a “horizontal” division of ${\mathbb{R}}^2$. If, for example, $\Omega =[0,1[$, $\mathcal{A}$ is the Borel $\sigma$-algebra and $\mu$ the Lebesgue measure on $\Omega$, and if T is the tent map on $\Omega$, meaning that:

$$T\left(\omega \right)=\left\{\begin{array}{cc}2\omega \hfill & \mathrm{if}0\le \omega <\frac{1}{2},\hfill \\ 2-2\omega \hfill & \mathrm{if}\frac{1}{2}\le \omega <1,\hfill \end{array}\right.$$

(5)

and X is the identity map, then the location of the horizontal cut is substantial.

On the one hand, $R=\{(x,y)\in {\mathbb{R}}^2\mid x\le 2/3\}$ (Figure 2b) does not discriminate enough to obtain the KS entropy of the given system, and on the other hand, there is enough discrimination by $R=\{(x,y)\in {\mathbb{R}}^2\mid x\le 1/2\}$ (Figure 2a) due to the fact that $\left\{\right[0,\frac{1}{2}[,[\frac{1}{2},1\left[\right\}$ is a generating partition for T. In the situation considered, there is no additional information given by the measurements $(x,y)$ relative to measurement x, hence R provides nothing more than a classical symbolization. For a detailed discussion of these facts, see [6].

The rest of this paper is organized as follows. Section 2 provides the notions and concepts being necessary for formulating the main statement of this paper in Section 3. This statement is rather abstract and general and has to be considered in relation to some special cases discussed in Section 4 and making our ideas and findings transparent. Section 5 is devoted to the proof of our main statement.

2. Preliminaries

Throughout this paper, $(\Omega ,\mathcal{A},\mu ,T)$ will be a measure-preserving dynamical system.

2.1. Some Notions

We will write $\mathcal{B}=\mathcal{B}\left(\mathbb{R}\right)$ or $\mathcal{B}\left({\mathbb{R}}^d\right)$ for the Borel $\sigma$-algebra on $\mathbb{R}$ or ${\mathbb{R}}^d;d\in \mathbb{N}$, respectively. Given a random variable $X:\Omega \to \mathbb{R}$, by ${\mu }_X$ we denote the push-forward measure of $\mu$ with regard to X, i.e., ${\mu }_X\left(A\right):=\mu \left(X^{-1}\left(A\right)\right)$ for all $A\in \mathcal{B}\left(\mathbb{R}\right)$. The measure ${\mu }_X\times {\mu }_X={\mu }_X^2$ is the product measure, i.e., ${\mu }_X^2(A\times B)={\mu }_X\left(A\right){\mu }_X\left(B\right)$ for all $A,B\in \mathcal{B}\left(\mathbb{R}\right)$.

For some Borel set $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$, we define the function $f_X^R:\mathbb{R}\to [0,1]$ by

$$f_X^R\left(x\right):=\mu \left(\{\omega \in \Omega \mid (x,X\left(\omega \right))\in R\}\right).$$

(6)

If it is clear from the context which set $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$ is considered, we simply write $f_X$ instead of $f_X^R$. The function $f_X$ can be represented as the integral:

$$f_X\left(x\right)=\int 1_R(x,y)\mathrm{d}{\mu }_X\left(y\right).$$

Since $1_R$ is integrable with regard to ${\mu }_X^2$, $f_X$ is integrable and therefore, also measurable by Fubini’s Theorem.

The complement ${\mathbb{R}}^2\backslash R$ of a set $R\subseteq {\mathbb{R}}^2$ will be denoted by $R^c$. The notation $\partial R$ will be used for the boundary of a set R, i.e., the closure of R without its interior.

2.2. Entropy

The Shannon entropy of a finite partition $\mathcal{P}\subset \mathcal{A}$ of $\Omega$ is defined as

$$H\left(\mathcal{P}\right):=-\sum _{P\in \mathcal{P}}\mu \left(\mathcal{P}\right)log\left(\mu \left(\mathcal{P}\right)\right).$$

The refinement of two partitions $\mathcal{P},\mathcal{Q}\subset \mathcal{A}$ of $\Omega$ is given by

$$\mathcal{P}\vee \mathcal{Q}:=\{P\cap Q\ne \varnothing \mid P\in \mathcal{P},Q\in \mathcal{Q}\}.$$

For a finite collection of partitions ${\mathcal{P}}_i\subset \mathcal{A},i\in \{1,2,\dots ,n\}$ of $\Omega$, one analogously defines:

$$\underset{i=1}{\overset{n}{\bigvee }}{\mathcal{P}}_i:=\left\{\bigcap _{i=1}^n{P}_i\ne \varnothing \mid P_i\in {\mathcal{P}}_i\mathrm{for}\mathrm{all}i\in \{1,2,\dots ,n\}\right\}.$$

The entropy rate of a finite partition $\mathcal{P}\subset \mathcal{A}$ of $\Omega$ is defined as

$$h(T,\mathcal{P}):=\underset{n\to \infty }{lim}\frac{1}{n}H\left(\underset{t=0}{\overset{n-1}{\bigvee }}{T}^{-t}\left(\mathcal{P}\right)\right),$$

where $T^{-t}\left(\mathcal{P}\right)=\{T^{-t}\left(P\right)\mid P\in \mathcal{P}\}$. For the existence of the limit in the formula, see, e.g., [7]. We are interested in determining the Kolmogorov–Sinai entropy of a system, which is defined as

$$h\left(T\right):=\underset{\mathcal{P}}{sup}h(T,\mathcal{P}),$$

where the supremum is taken over all finite partitions of $\Omega$ in $\mathcal{A}$.

Note that the Kolmogorov–Sinai entropy serves as the central complexity measure for dynamical systems and can be considered as a reference for other complexity measures, including in data analysis. Roughly speaking, it measures the mean information obtained by each iteration step. Since the Kolmogorov–Sinai entropy is the supremum of the entropy rates of all finite partitions, its determination and its estimation in a practical context are not easy and it is of some interest to find natural finite partitions for which the entropy rate is near the Kolmogorov–Sinai entropy. This is also a motivation for considering ordinal patterns and its generalization in this paper.

2.3. $\sigma$-Algebras

Given a family of sets $A_i\in \mathcal{A},i\in I$, by $\sigma (A_i\mid i\in I)$ we denote the smallest $\sigma$-algebra containing all sets $A_i$. Analogously, for a family of partitions ${\mathcal{P}}_i\subset \mathcal{A},i\in I$ of $\Omega$, we define $\sigma ({\mathcal{P}}_i\mid i\in I)$ as the smallest $\sigma$-algebra containing all partitions ${\mathcal{P}}_i$ as subsets. Given d-dimensional random vectors $(Y_{i,1},Y_{i,2},\dots ,Y_{i,d}):\Omega \to {\mathbb{R}}^d,i\in I$, we define:

$$\sigma ((Y_{i,1},Y_{i,2},\dots ,Y_{i,d})\mid i\in I):=\sigma ({(Y_{i,1},Y_{i,2},\dots ,Y_{i,d})}^{-1}\left(B\right)\mid i\in I,B\in \mathcal{B}\left({\mathbb{R}}^d\right))$$

as the smallest $\sigma$-algebra containing all preimages of Borel sets. When comparing two $\sigma$-algebras ${\mathcal{A}}_1,{\mathcal{A}}_2\subseteq \mathcal{A}$, we ignore sets with measure 0, i.e., we write:

$${\mathcal{A}}_1{\subseteq }_{\mu }{\mathcal{A}}_2$$

if for all $A_1\in {\mathcal{A}}_1$ there exists an $A_2\in {\mathcal{A}}_2$ with $\mu ((A_1\backslash A_2)\cup (A_2\backslash A_1))=0$. In this sense, ${\mathcal{A}}_1{=}_{\mu }{\mathcal{A}}_2$ means that ${\mathcal{A}}_1{\subseteq }_{\mu }{\mathcal{A}}_2$ and ${\mathcal{A}}_2{\subseteq }_{\mu }{\mathcal{A}}_1$.

3. The Main Statement

Recall that a measure-preserving dynamical system $(\Omega ,\mathcal{A},\mu ,T)$ is ergodic if for each $B\in \mathcal{A}$ with $T^{-1}\left(B\right)=B$ it holds $\mu \left(B\right)\in \{0,1\}$, meaning that the system does not divide into proper parts.

Referring to Section 1, we give some preparation for stating our main result. Recall that for defining (generalized) ordinal patterns it was basic to know whether $(X\left(T^s\left(\omega \right)\right),X\left(T^s\left(\omega \right)\right))\in R$ or $(X\left(T^s\left(\omega \right)\right),X\left(T^s\left(\omega \right)\right))\in {\mathbb{R}}^2\backslash R$ for $\omega \in \Omega$ and a random variable X on $\Omega$, where “time” pairs $(s,t)$ were taken from the sets $E_n$ (see (2)). In order to also allow reducing the number of necessary “comparisons”, we relax the definition of the sets $E_n$ leading to the following concept.

Definition 2.

We call a sequence ${\left(E_n\right)}_{n\in \mathbb{N}}$ with $E_1\subseteq E_2\subseteq E_3\subseteq \dots \subseteq {\mathbb{N}}_0^2$ timing, if $E_n$ contains finitely many elements and if there exists a sequence ${\left(a_n\right)}_{n\in \mathbb{N}}\in {\mathbb{N}}_0^{\mathbb{N}}$ with:

$$\underset{N\to \infty }{lim\; sup}\frac{\#\left\{n\in \{1,2,\dots ,N\}\mid (a_n,a_n+n)\in {\bigcup }_{k=1}^{\infty }{E}_k\right\}}{N}=1.$$

(7)

Formula (7) roughly says that nearly each “temporal” distance is available for “comparisons”. It guarantees that enough time-pairs are considered to not have any loss of information contained in the “thinned out” generalized ordinal patterns relative to the “full” generalized ordinal patterns.

Remark 1.

In the first paper on generalized ordinal patterns ([6]), a timing ${\left(E_n\right)}_{n\in \mathbb{N}}$ was differently defined: the authors of that paper called a sequence of finite sets $E_1\subseteq E_2\subseteq E_3\subseteq \dots \subseteq {\mathbb{N}}_0^2$ timing, if there exists an increasing sequence ${\left(a_n\right)}_{n\in \mathbb{N}}$ such that for all $n\in \mathbb{N}$:

(i)

$E_n\subseteq {\{a_0,a_1,\dots ,a_n\}}^2$,

(ii)

for all $s\in \{a_0,a_1,\dots ,a_n\}$, there exists a $t\in \{a_0,a_1,\dots ,a_n\}$ with $s\ne t$ and $(s,t)\in E_n$,

(iii)

${(id,T^n)}^{-1}\left({\mathcal{R}}_i\right){\subseteq }_{\mu }\sigma \left({\bigvee }_{(s,t)\in E_k}{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\mid k\in \mathbb{N}\right)$ for all $i\in \{1,2,\dots ,d\}$

hold true. Note that the last condition does not only depend on the timing ${\left(E_n\right)}_{n\in \mathbb{N}}$ but also on T and $\mathit{X}=(X_1,X_2,\dots ,X_d)$. Instead of those three conditions, we instead simply require that almost all differences can be found in the timing.

Given a random vector $(X_1,X_2,\dots ,X_d)$ and $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$, we define the partition:

$${\mathcal{R}}_i:={(X_i,X_i)}^{-1}\left(\{R,R^c\}\right)=\{{(X_i,X_i)}^{-1}\left(R\right),{(X_i,X_i)}^{-1}\left(R^c\right)\}$$

for all $i\in \{1,2,\dots ,d\}$, which is equal to:

$$\begin{array}{cc}\hfill {\mathcal{R}}_i=\{& \{({\omega }_1,{\omega }_2)\in {\Omega }^2\mid (X_i\left({\omega }_1\right),X_i\left({\omega }_2\right))\in R\},\hfill \\ \hfill & \{({\omega }_1,{\omega }_2)\in {\Omega }^2\mid (X_i\left({\omega }_1\right),X_i\left({\omega }_2\right))\notin R\}\}.\hfill \end{array}$$

Then, for $E_n$ as given in (2) the partition ${\bigvee }_{(s,t)\in E_k}{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)$ is no more than the partition of generalized ordinal patterns with respect to $X_i$ defined in Section 1 and ${\bigvee }_{i=1}^d{\bigvee }_{(s,t)\in E_k}{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)$ can be considered as the partition of generalized ordinal patterns with respect to $(X_1,X_2,\dots ,X_d)$.

The proof of the following main theorem of the paper is given in Section 5.

Theorem 1.

Let $(\Omega ,\mathcal{A},\mu ,T)$ be an ergodic measure-preserving dynamical system, $\mathit{X}=(X_1,X_2,\dots ,X_d):\Omega \to {\mathbb{R}}^d$ be a random vector, $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$ be a discriminating relation and ${\left(E_n\right)}_{n\in \mathbb{N}}$ be a timing. Assume that the following conditions are valid:

$$\begin{array}{c}\hfill There exists a countable set C\subseteq {\mathbb{R}}^{2}with:\\ \hfill {\mu }_{X_i}^2(\partial R\backslash C)=0foralli\in \{1,2,\dots ,d\}.\end{array}$$

(8)

$$\begin{array}{c}\hfill There exists a random variable Y:\Omega \to \mathbb{R}with:\\ \hfill \#Y(\Omega )<\infty and \mathcal{A}{=}_{\mu }\sigma \left((f_{X_i}^R\circ X_i\circ T^t,Y)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right).\end{array}$$

(9)

Then:

$$h\left(T\right)=\underset{k\to \infty }{lim}h\left(T,\underset{i=1}{\overset{d}{\bigvee }}\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right).$$

(10)

holds true.

At first glance, conditions (8) and (9), being sufficient for (10), are looking very special. The considerations in the following section will, however, elucidate their role and show that they are relatively general. Roughly speaking, (8) says that the distribution of pairs of “independent measurements” with respect to $X_i$ is discrete on the boundary of R. Condition (9) is an orbit separation condition based on the involved “measurements” and the functions $f_{X_i}^R$. In general:

$$\mathcal{A}{\supseteq }_{\mu }\sigma \left((f_{X_i}^R\circ X_i\circ T^t,Y)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right)$$

holds true because all functions involved in (9) are $\mathcal{A}$ measurable. Therefore, (9) is equivalent to

$$\mathcal{A}{\subseteq }_{\mu }\sigma \left((f_{X_i}^R\circ X_i\circ T^t,Y)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right)$$

The inclusion of the random variable Y provides some further separation and allows the above inclusion to hold true for a wider class of dynamical systems than, for example, the ones considered in [6]. In the case that Y is constant, it can also be omitted. In theory, Y should be chosen to take different values on those sets on which $f_{X_i}^R\circ X_i\circ T^t$ takes the same values for $i\in \{1,2,\dots ,d\}$ and $t\in {\mathbb{N}}_0$. In practice, the fact that such a random variable Y exists is sufficient and Y does not need to be explicitly specified. An example is given in Section 4.5.

4. Special Cases

In the following, we discuss some special situations where the assumptions of Theorem 1, i.e., (8) and (9), are satisfied. Lemma 2 provides an easy-to-check condition, that of when (8) holds true. It is more difficult to see, when the condition (9) is satisfied. Roughly speaking, this condition is fulfilled if $\mathit{X}=(X_1,X_2,\dots ,X_d)$ together with Y can uniquely describe the outcomes of the whole dynamical system and applying $f_{X_i}$ to the results of $\mathit{X}$ is, in some sense, “reversible” for all $i\in \{1,2,\dots ,d\}$. In other words, $\mathit{X}=(X_1,X_2,\dots ,X_d)$ together with Y preserve the information of the system and there is no information loss for the symbolization. The first means that:

$$\mathcal{A}{=}_{\mu }\sigma \left((X_i\circ T^t,Y)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right),$$

which obviously follows from

$$\mathcal{A}{=}_{\mu }\sigma \left((f_{X_i}^R\circ X_i\circ T^t,Y)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right).$$

To describe the range of outcomes of the random variables X on a probability space $(\Omega ,\mathcal{A},\mu )$, we will use its cumulative distribution functions $F_X:\mathbb{R}\to [0,1]$ defined by

$$F_X\left(x\right):={\mu }_X\left(\right]-\infty ,x\left]\right).$$

When applying the cumulative distribution functions $F_X$ to the outcomes X of a system, we do not lose any essential information about the system, according to the following lemma. This lemma is a simple modification of Lemma A.3 in [6].

Lemma 1.

Let $(\Omega ,\mathcal{A},\mu )$ be a probability space, $X:\Omega \to \mathbb{R}$ be a random variable and $g:\mathbb{R}\to \mathbb{R}$ be a $\mathcal{B}-\mathcal{B}$ measurable function which maps Borel sets to Borel sets and satisfies the following property:

$$For all x\in \mathbb{R} it holds \mu \left(X^{-1}\left(g^{-1}(g\left(\right]-\infty ,x]\right)\right)\backslash ]-\infty ,x]\left)\right)=0$$

(11)

Then, $\sigma (g\circ X){=}_{\mu }\sigma \left(X\right)$. In particular, $\sigma (g\circ X){=}_{\mu }\sigma \left(X\right)$ if $g=F_X$ or g is injective on $X(\Omega )$.

Condition (11) in the above Lemma is a slightly weaker condition on g than injectivity. If g is injective, then $g^{-1}(g\left(\right]-\infty ,x]\left)\right)=]-\infty ,x]$ will hold true for all $x\in \mathbb{R}$ and condition (11) will be satisfied. More general, condition (11) can still be true if g is not necessarily injective but if all sets on which g is not injective, which are given by $X^{-1}\left(g^{-1}(g\left(\right]-\infty ,x]\right))\backslash ]-\infty ,x\left]\right)$ for all $x\in \mathbb{R}$, have measure 0. For example, this is true if g is equal to the cumulative distribution function.

4.1. On the Boundary of R

The condition (8) in Theorem 1, that the boundary of R apart from countably many points has measure 0, holds true for all “simple” sets R. In the following lemma, we specify what we mean by “simple”.

Lemma 2.

Let $(\Omega ,\mathcal{A},\mu )$ be a probability space, $(X_1,X_2,\dots ,X_d)$ be a random vector and $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$. If, for all $i\in \{1,2,\dots ,d\}$:

$$\begin{array}{cc}\hfill & \partial R\cap (\left\{x\right\}\times \mathbb{R})\mathit{is}\mathit{countable}\mathit{for}{\mu }_{X_i}\text{-}\mathit{almost}\mathit{all}x\in \mathbb{R}\hfill \\ \hfill \mathit{or}& \partial R\cap (\mathbb{R}\times \left\{y\right\})\mathit{is}\mathit{countable}\mathit{for}{\mu }_{X_i}\text{-}\mathit{almost}\mathit{all}y\in \mathbb{R},\hfill \end{array}$$

then R satisfies (8), i.e., there exists a countable set $C\subseteq {\mathbb{R}}^2$ with:

$${\mu }_{X_i}^2(\partial R\backslash C)=0\mathit{for}\mathit{all}i\in \{1,2,\dots ,d\}.$$

Proof. 

Consider the sets:

$$A_i:=\{x\in \mathbb{R}\mid {\mu }_{X_i}\left(\left\{x\right\}\right)>0\}$$

for $i\in \{1,2,\dots ,d\}$, which, obviously, are countable. Set:

$$C:=\bigcup _{i=1}^d{A}_i\times A_i.$$

Let $i\in \{1,2,\dots ,d\}$. If $\{y\in \mathbb{R}\mid (x,y)\in \partial R\}$ is countable for ${\mu }_{X_i}$-almost all $x\in \mathbb{R}$, Fubini’s theorem implies:

$$\begin{array}{cc}\hfill {\mu }_{X_i}^2(\partial R\backslash C)& =\int \int 1_{\partial R\backslash C}(x,y)\mathrm{d}{\mu }_{X_i}\left(y\right)\mathrm{d}{\mu }_{X_i}\left(x\right)\hfill \\ \hfill & =\int {\mu }_{X_i}\left(\{y\in \mathbb{R}\mid (x,y)\in \partial R\backslash C\}\right)\mathrm{d}{\mu }_{X_i}\left(x\right)\hfill \\ \hfill & =\int \sum _{\begin{array}{c}y\in \mathbb{R}:\\ (x,y)\in \partial R\backslash C\end{array}}{\mu }_{X_i}\left(\left\{y\right\}\right)\mathrm{d}{\mu }_{X_i}\left(x\right)\hfill \\ \hfill & =\int 0\mathrm{d}{\mu }_{X_i}\left(x\right)=0.\hfill \end{array}$$

Analogously, one can show the same if $\{x\in \mathbb{R}\mid (x,y)\in \partial R\}$ is countable for ${\mu }_{X_i}$-almost all $y\in \mathbb{R}$. □

Remark 2.

The patterns visualized in Figure 1 could also be defined on the whole real axis instead of a bounded interval by, for example, applying the transformation $\phi \left(x\right)=tan\left(\pi \right(x-1/2\left)\right)$. Then, $\tilde{R}=(\phi \times \phi )\left(R\right)$ is a pattern defined on ${\mathbb{R}}^2$ if R is defined on ${[0,1[}^2$.

In the following three subsections, Y is assumed to be constant, and hence can be omitted.

4.2. Basic Ordinal Patterns

If:

$$R=\{(x,y)\in {\mathbb{R}}^2\mid x\ge y\}$$

(see Figure 1a), then $f_{X_i}^R$ is just the distribution function of ${\mu }_{X_i}$, i.e., $f_{X_i}^R=F_{X_i}$. Since $\partial R\cap \left\{x\right\}\times \mathbb{R}=\left\{\right(x,x\left)\right\}$ is finite for all $x\in \mathbb{R}$, (8) holds true by Lemma 2. According to Lemma 1, one has:

$$\sigma (X_i\circ T^t){\subseteq }_{\mu }\sigma (F_{X_i}\circ X_i\circ T^t)$$

(12)

for all $t\in {\mathbb{N}}_0$ and $i=1,2,\dots ,n$. Therefore:

$$\begin{array}{cc}\hfill \mathcal{A}& {=}_{\mu }\sigma \left((f_{X_i}^R\circ X_i\circ T^t)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right)\hfill \\ \hfill & =\sigma \left((F_{X_i}\circ X_i\circ T^t)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right)\hfill \end{array}$$

(13)

is equivalent to:

$$\mathcal{A}{=}_{\mu }\sigma \left((X_i\circ T^t)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right).$$

(14)

By Theorem 1, for ergodic systems, condition (14) implies (10). A more general statement also includes a large class of non-ergodic systems which was shown in [4]. Condition (14) is, for example, satisfied if $\Omega \in \mathcal{B}\left({\mathbb{R}}^d\right)$ and $X_i$ is the projection on the i-th coordinate for all $i\in \{1,2,\dots ,d\}$, or if $\Omega$ is a compact Hausdorff space and $\mathit{X}=(X_1,X_2,\dots ,X_d)$ is injective and continuous. One can also use Taken’s theorem to argue that the set of maps $\mathit{X}:\Omega \to {\mathbb{R}}^d$ that satisfy (14) is large in a certain topological sense. For both, see Keller [8].

4.3. Patterns Defined by “Injective” Functions

Let $\mathit{X}=(X_1,X_2,\dots ,X_d)$ be a random vector and consider now:

$$R=\left\{\right(x,y)\in \mathbb{R}\mid g(x)\ge y\}$$

(15)

for a $\mathcal{B}-\mathcal{B}$ measurable function $g:\mathbb{R}\to \mathbb{R}$ (see Figure 1b). Since $\partial R\cap \left(\right\{x\}\times \mathbb{R})=\left\{\right(x,g\left(x\right)\left)\right\}$ is finite for all $x\in \mathbb{R}$, (8) holds true by Lemma 2. Moreover, one easily sees that $f_{X_i}^R=F_{X_i}\circ g$.

Now, suppose that:

$$\sigma \left(F_{X_i}\right)\subseteq \sigma (F_{X_i}\circ g)$$

(16)

holds true for all $i\in \{1,2,\dots ,d\}$. This directly yields:

$$\sigma (F_{X_i}\circ X_i\circ T^t)\subseteq \sigma (F_{X_i}\circ g\circ X_i\circ T^t)$$

for all $i\in \{1,2,\dots ,d\}$ and $t\in \mathbb{N}$. Remember that $\sigma (X_i\circ T^t){\subseteq }_{\mu }\sigma (F_{X_i}\circ X_i\circ T^t)$ holds true according to Lemma 1. Thus, (14) and (16) imply (10). When considering basic ordinal patterns in Section 4.2, we stated some conditions under which (14) holds true. It remains to consider when (16) is satisfied.

Assume that g maps Borel sets to Borel sets and is injective. This implies:

$$\sigma (g\circ X_i\circ T^t)=\sigma (X_i\circ T^t)$$

for all $t\in {\mathbb{N}}_0$ and $i\in \{1,2,\dots ,d\}$. Now, suppose that:

$$\mathcal{A}=\sigma \left(F_{X_i}\circ X_i\circ T^t\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right).$$

holds true. This would then imply (16). However, the above equation only holds true $\mu$-almost surely (see (13)). This can be a problem when applying the function g because there could exist sets $B\in \mathcal{B}$ with ${\mu }_{X_i}\left(B\right)=0$ but ${\mu }_{X_i}\left(g\left(B\right)\right)>0$. Additionally, we therefore need to require that ${\mu }_{X_i}\left(g^{-1}\left(B\right)\right)=0$ implies ${\mu }_{X_i}\left(B\right)=0$ for all $B\in \mathcal{B}$.

Theorem 1 then provides the following statement:

Corollary 1.

Let $(\Omega ,\mathcal{A},\mu ,T)$ be an ergodic measure-preserving dynamical system, $\mathit{X}=(X_1,X_2,\dots ,X_d):\Omega \to {\mathbb{R}}^d$ be a random vector and ${\left(E_n\right)}_{n\in \mathbb{N}}$ be a timing. Let further $g:\mathbb{R}\to \mathbb{R}$ be a $\mathcal{B}-\mathcal{B}$ measurable function which maps Borel sets to Borel sets, is injective on $X_i(\Omega )$ and satisfies ${\mu }_{X_i}\left(g^{-1}\left(B\right)\right)=0\Rightarrow {\mu }_{X_i}\left(B\right)=0$ for all $B\in \mathcal{B}$ and $i\in \{1,2,\dots ,d\}$. Let $R=\{(x,y)\in {\mathbb{R}}^2\mid g\left(x\right)\ge y\}$.

Then, (14) implies (10). Moreover, (10) holds true if $\Omega \in \mathcal{B}\left({\mathbb{R}}^d\right)$ and $X_i$ is the projection on the i-th coordinate for all $i\in \{1,2,\dots ,d\}$ or if Ω is a compact Hausdorff space and $\mathit{X}=(X_1,X_2,\dots ,X_d)$ is injective and continuous.

Note that the statements in Corollary 1, in principle, were shown in [6]. The case of basic ordinal patterns is included by $g\left(x\right)=x$ for all $x\in \mathbb{R}$.

4.4. Patterns Defined by “Surjective” Functions

Swapping coordinates in (15) yields the set:

$$R=\left\{\right(x,y)\in \mathbb{R}\mid x<g(y\left)\right\}$$

(see Figure 1c) with (8) following from Lemma 2 and with:

$$\begin{array}{cc}\hfill f_{X_i}^R\left(x\right)& =\mu \left(\{\omega \in \Omega \mid (x,X_i\left(\omega \right))\in R\}\right)=\mu \left(\{\omega \in \Omega \mid x<g\left(X_i\left(\omega \right)\right)\}\right)\hfill \\ \hfill & =\mu (\{\omega \in \Omega \mid g\left(X_i\left(\omega \right)\right)\in ]x,\infty \left[\right\})=1-F_{g\circ X_i}\left(x\right).\hfill \end{array}$$

Corollary 2.

Let $(\Omega ,\mathcal{A},\mu ,T)$ be an ergodic measure-preserving dynamical system, $\mathit{X}=(X_1,X_2,\dots ,X_d):\Omega \to {\mathbb{R}}^d$ be a random vector and ${\left(E_n\right)}_{n\in \mathbb{N}}$ be a timing. Let further $g:\mathbb{R}\to \mathbb{R}$ be a $\mathcal{B}-\mathcal{B}$ measurable function and let $R=\{(x,y)\in {\mathbb{R}}^2\mid x<g\left(y\right)\}$. Then, the following holds:

(i)

If $F_{g\circ X_i}$ is injective on $X_i(\Omega )$ for $i\in \{1,2,\dots ,d\}$, (14) implies (10).

(ii)

If $\Omega \in \mathcal{B}\left({\mathbb{R}}^d\right)$ and $X_i$ is the projection on the i-th coordinate for all $i\in \{1,2,\dots ,d\}$ or if Ω is a compact Hausdorff space and $\mathit{X}=(X_1,X_2,\dots ,X_d)$ is injective and continuous, if further $\mu \left(U\right)>0$ for every non-empty open set $U\subseteq \Omega$, g is continuous and $X_i(\Omega )\subseteq g\left(X_i(\Omega )\right)$, then (10) is valid in each of the following two cases:

(1)

For each $i\in \{1,2,\dots ,d\}$ and all $x_1,x_2\in X_i(\Omega )$ with $x_1<x_2$, there exists some $y\in X_i(\Omega )$ with $x_1<y<x_2$,

(2)

Ω is connected.

Proof.

(i): If the above assumptions are satisfied and $F_{g\circ X_i}$ is injective on $X_i(\Omega )$ for all $i\in \{1,2,\dots ,d\}$, then by Lemma 1 it holds that $\sigma (X_i\circ T^t){\subseteq }_{\mu }\sigma (F_{g\circ X_i}\circ X_i\circ T^t)$ for all $t\in {\mathbb{N}}_0$ and $i\in \{1,2,\dots ,d\}$. This implies (9), hence, by Theorem 1 the statement (10).

(ii): Given the assumptions of (ii), we have to show that $F_{g\circ X_i}$ is injective on $X_i(\Omega )$ for all $i\in \{1,2,\dots ,d\}$. If $\Omega$ is connected, then (1) is obviously satisfied. We can thus start from (1). Take $x_1,x_2\in X_i(\Omega )$ with $x_1<x_2$. Then, $g^{-1}\left(\right]x_1,x_2\left[\right)$ is non-empty and because $g\circ X_i$ is continuous, $X_i^{-1}(g^{-1}\left(\right]x_1,x_2]\left)\right)$ contains a non-empty open set. This implies that $F_{g\circ X_i}\left(x_1\right)<F_{g\circ X_i}\left(x_2\right)$. because every non-empty open set was assumed to have a strictly positive measure. □

Notice that, unlike in (15), it is not necessary that g is one-to-one.

4.5. Piecewise Patterns

The previous subsection illustrates that (9) is fulfilled if, roughly speaking, $(X_1,X_2,\dots ,X_d)$ preserves all information and if $f_{X_i}^R$ is a ${\mu }_{X_i}$ almost surely invertible function for all $i\in \{1,2,\dots ,d\}$. The finite-valued random variable Y in (9) can be used to weaken the condition of invertibility in the sense that only piecewise invertibility is needed where the different pieces are induced by the random variable Y.

For $\Omega =[0,1[$ and an absolutely continuous measure $\mu$, one could, for example, consider:

$$R_{\mathrm{circles}}=\{(x,y)\in {\Omega }^2\mid {\parallel (kxmod1,kymod1)-(0.5,0.5)\parallel }_2\le 0.5\}$$

(17)

for any $k\in \mathbb{N}$, as shown for $k=5$ in Figure 1d. The set R satisfies condition (9) with $Y\left(\omega \right)=i$ for $\omega \in \left[\right(i-1)/(2k),i/(2k\left)\right[$ and $i\in \{1,2,\dots ,2k\}$. The set R is a pattern with $k^2$ circles of diameter $1/k$ distributed in ${[0,1]}^2$ on a square grid.

4.6. A Remark on the Work of Amigó et al.

Consider the discriminating relation:

$$R_k=\{(x,y)\in {\mathbb{R}}^2\mid \lceil k·x\rceil \ge \lceil k·y\rceil \}$$

shown in Figure 3 for $k\in \mathbb{N}$. Assume for simplicity that the dynamical system is defined on $\Omega =[0,1[$ and that X is the identity map $id$. It is easy to see that:

$$\sigma \left(\underset{t=0}{\overset{n}{\bigvee }}{T}^{-t}\left({\mathcal{P}}_k\right)\mid n\in \mathbb{N}\right){=}_{\mu }\sigma \left(f_{id}^{R_k}\circ T^t\mid t\in {\mathbb{N}}_0\right)$$

holds true, where ${\mathcal{P}}_k:=\left\{\right[(i-1)/k,i/k{\left[\right\}}_{i=1}^k$. Therefore, (9) in Theorem 1 holds true if ${\mathcal{P}}_k$ is a generating partition.

Additionally, one could consider the quantity:

$$\underset{k\to \infty }{lim}\underset{n\to \infty }{lim\; inf}\frac{1}{n}H\left(\underset{s=0}{\overset{n-1}{\bigvee }}\underset{t=s+1}{\overset{n-1}{\bigvee }}{(T^s,T^t)}^{-1}\left(\{R_k,{\mathbb{R}}^2\backslash R_k\}\right)\right)$$

(18)

which was introduced by Amigó et. al. [9]. They used finite-valued random variables to quantize the dynamical system into k parts and considered the ordinal patterns of the quantized systems while we directly apply the quantization to the discriminating relation. Both approaches only differ in their notation. They showed in their paper that the limit in (18) is equal to the Kolmogorov–Sinai entropy.

5. Proof of the Main Statement

We first recall some definitions and statements related to partitions and the conditional entropy. For two partitions $\mathcal{P},\mathcal{Q}\subset \mathcal{A}$ of $\Omega$, the conditional entropy is defined as

$$H\left(\mathcal{P}\right|\mathcal{Q}):=H(\mathcal{P}\vee \mathcal{Q})-H(\mathcal{Q}).$$

Roughly speaking, the conditional entropy $H\left(\mathcal{P}\right|\mathcal{Q})$ describes how much uncertainty is left in the outcomes described by the sets given in $\mathcal{P}$ if one already has information about the outcomes described by the sets given in $\mathcal{Q}$. For example, if $\mathcal{P}=\mathcal{Q}$, then $H\left(\mathcal{P}\right|\mathcal{Q})=0$. However, if $\mathcal{P}$ and $\mathcal{Q}$ are independent, meaning that $\mu (P\cap Q)=\mu \left(P\right)·\mu \left(Q\right)$ for all $P\in \mathcal{P}$ and $Q\in \mathcal{Q}$, and $H\left(\mathcal{P}\right|\mathcal{Q})=H(\mathcal{Q})$.

Without explicitly referencing them, we will use the following properties of the conditional entropy:

(i)

$H\left(T^{-1}\left(\mathcal{P}\right)\right|T^{-1}\left(\mathcal{Q}\right))=H\left(\mathcal{P}\right|\mathcal{Q})$,

(ii)

$H\left({\bigvee }_{i=1}^n{\mathcal{P}}_i\right|\mathcal{Q})\le {\sum }_{i=1}^{n}H\left({\mathcal{P}}_i\right|\mathcal{Q})$,

(iii)

$H\left(\mathcal{P}\right|{\mathcal{Q}}_1\vee {\mathcal{Q}}_2)\le H\left(\mathcal{P}\right|{\mathcal{Q}}_1)$.

See, for examples, [7] for proofs.

A sequence of partitions ${\left(P_i\right)}_{i\in \mathbb{N}}$ in $\mathcal{A}$ of $\Omega$ is said to be generating (the $\sigma$-algebra $\mathcal{A}$), if $\sigma \left(P_i\right)\subseteq \sigma \left({\mathcal{P}}_{i+1}\right)$ for all $i\in \mathbb{N}$ and:

$$\sigma ({\mathcal{P}}_i\mid i\in \mathbb{N}){=}_{\mu }\mathcal{A}$$

holds true. As a consequence of this property:

$$\underset{n\to \infty }{lim}H(\mathcal{P}\mid {\mathcal{P}}_n)=0$$

(19)

holds true for all partitions $\mathcal{P}\subset \mathcal{A}$ of $\Omega$. Using the properties of the conditional entropy implies:

$$h\left(T\right)=\underset{n\to \infty }{lim}h(T,{\mathcal{P}}_n).$$

For $N\in \mathbb{N}$:

$${\mathcal{U}}_N=\left\{\left[(i-1)/2^N,i/2^N\right[\mid i\in \{1,2,\dots ,2^N-1\}\right\}\cup \left\{\left[(2^N-1)/2^N,1\right]\right\}$$

will denote the partition of $[0,1]$ in $2^N$ equally sized intervals.

We start the proof of Theorem 1 with two basic lemmata.

Lemma 3.

Let $(\Omega ,\mathcal{A},\mu ,T)$ be a measure-preserving dynamical system, $\mathit{X}=(X_1,X_2,\dots ,X_d)$ be a random vector and Y be a random variable satisfying (9). Then, there exists some constant $c\in \mathbb{R}$ with:

$$h\left(T^m\right)\le \underset{N\to \infty }{lim}h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{t=0}{\overset{m-1}{\bigvee }}{T}^{-t}\left(X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)\right)\right)+c.$$

for all $m\in \mathbb{N}$.

Proof. 

Fix $m\in \mathbb{N}$. Set:

$$\mathcal{M}:=\left\{Y^{-1}\left(y\right)\mid y\in Y(\Omega )\right\}$$

Since Y was assumed to attain only a finite number of different values, $\mathcal{M}$ is a finite partition of $\Omega$. Because the Borel $\sigma$-algebra of $[0,1]$ is generated by the partitions ${\mathcal{U}}_N$ and due to (9), we have:

$$\begin{array}{cc}\hfill \mathcal{A}& {=}_{\mu }\sigma \left((f_{X_i}\circ X_i\circ T^t,Y)\mid t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right)\hfill \\ \hfill & =\sigma \left(T^{-t}\left(X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)\right)\vee \mathcal{M}\mid N\in \mathbb{N},t\in {\mathbb{N}}_0,i\in \{1,2,\dots ,d\}\right).\hfill \end{array}$$

Thus, for any $\epsilon >0$ and any finite partition $\mathcal{P}\subset \mathcal{A}$ of $\Omega$, there exists an $N_{\epsilon }\in \mathbb{N}$ and a $t_{\epsilon }\in \mathbb{N}$ with:

$$\begin{array}{cc}\hfill h(T^m,\mathcal{P})& \le h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{t=0}{\overset{t_{\epsilon }-1}{\bigvee }}{T}^{-t}\left(X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)\right)\vee \mathcal{M}\right)+\epsilon \hfill \\ \hfill & \le h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{t=0}{\overset{t_{\epsilon }-1}{\bigvee }}{T}^{-t}\left(X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)\right)\right)+h\left(T^m,\mathcal{M}\right)+\epsilon \hfill \\ \hfill & \le h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{t=0}{\overset{t_{\epsilon }-1}{\bigvee }}{T}^{-t}\left(X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)\right)\right)+H\left(\mathcal{M}\right)+\epsilon \hfill \\ \hfill & \le h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{t=0}{\overset{m-1}{\bigvee }}{T}^{-t}\left(X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)\right)\right)+H\left(\mathcal{M}\right)+\epsilon \hfill \end{array}$$

for all $N\ge N_{\epsilon }$. Hence:

$$h(T^m,\mathcal{P})\le \underset{N\to \infty }{lim}h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{t=0}{\overset{m-1}{\bigvee }}{T}^{-t}\left(X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)\right)\right)+H\left(\mathcal{M}\right)+\epsilon$$

for any $\epsilon >0$, which implies:

$$\begin{array}{cc}\hfill h\left(T^m\right)& =\underset{\mathcal{P}}{sup}h(T^m,\mathcal{P})\hfill \\ \hfill & \le \underset{N\to \infty }{lim}h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{t=0}{\overset{m-1}{\bigvee }}{T}^{-t}\left(X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)\right)\right)+H\left(\mathcal{M}\right).\hfill \end{array}$$

□

Lemma 4.

Let $(\Omega ,\mathcal{A},\mu )$ be a probability space, $X:\Omega \to \mathbb{R}$ be a random variable and $A,B\in \mathcal{B}\left({\mathbb{R}}^2\right)$. Then:

$$\int \left|f_X^A-f_X^B\right|\mathrm{d}{\mu }_X\le {\mu }_X^2(A▵B)$$

holds true.

Proof. 

For all $x\in \mathbb{R}$:

$$\begin{array}{cc}\hfill & \mu \left(\right\{\omega \in \Omega \mid (x,X(\omega \left)\right)\in A\Delta B\left\}\right)\hfill \\ \hfill =& \mu \left(\right\{\omega \in \Omega \mid (x,X(\omega \left)\right)\in A\backslash B\left\}\right)+\mu \left(\right\{\omega \in \Omega \mid (x,X(\omega \left)\right)\in B\backslash A\left\}\right)\hfill \\ \hfill \ge & \mu \left(\right\{\omega \in \Omega \mid (x,X(\omega \left)\right)\in A\backslash B\left\}\right)\hfill \\ \hfill \ge & \mu \left(\right\{\omega \in \Omega \mid (x,X(\omega \left)\right)\in A\left\}\right)-\mu \left(\right\{\omega \in \Omega \mid (x,X(\omega \left)\right)\in B\left\}\right)\hfill \\ \hfill =& f_X^A\left(x\right)-f_X^B\left(x\right)\hfill \end{array}$$

holds true. Analogously, one can show:

$$\mu \left(\{\omega \in \Omega \mid (x,X\left(\omega \right))\in A\Delta B\}\right)\ge f_X^B\left(x\right)-f_X^A\left(x\right).$$

This implies:

$$\mu \left(\{\omega \in \Omega \mid (x,X\left(\omega \right))\in A\Delta B\}\right)\ge \left|f_X^A\left(x\right)-f_X^B\left(x\right)\right|$$

and, by Fubini’s theorem:

$$\begin{array}{cc}\hfill & \int \left|f_X^A-f_X^B\right|\mathrm{d}{\mu }_X\left(x\right)\hfill \\ \hfill & \le \int \mu \left(\{\omega \in \Omega \mid (x,X\left(\omega \right))\in A\Delta B\}\right)\mathrm{d}{\mu }_X\left(x\right)\hfill \\ \hfill & =\int \int 1_{\{\omega \in \Omega \mid (x,X\left(\omega \right))\in A\Delta B\}}\left({\omega }^{\prime }\right)\mathrm{d}\mu \left({\omega }^{\prime }\right)\mathrm{d}{\mu }_X\left(x\right)\hfill \\ \hfill & =\int \int 1_{\{y\in \mathbb{R}\mid (x,y)\in A\Delta B\}}\left(y^{\prime }\right)\mathrm{d}{\mu }_X\left(y^{\prime }\right)\mathrm{d}{\mu }_X\left(x\right)\hfill \\ \hfill & ={\int }_{{\mathbb{R}}^2}{1}_{A\Delta B}(x,y^{\prime })\mathrm{d}{\mu }_X^2(x,y^{\prime })\hfill \\ \hfill & ={\mu }_X^2(A\Delta B).\hfill \end{array}$$

□

Therefore, in particular, the above lemma implies that, if ${\left(R_j\right)}_{j\in \mathbb{N}}$ is a sequence of sets in $\mathcal{B}\left({\mathbb{R}}^2\right)$ with ${lim}_{j\to \infty }{\mu }_X^2(R_j▵R)=0$, then $f_X^{R_j}$ converges to $f_X^R$ in $L^1$ for $j\to \infty$.

Given $R\subseteq {\mathbb{R}}^2$ and a random variable $X:\Omega \to \mathbb{R}$, consider the function $f_{X,n}^R:\Omega \times \mathbb{R}\to [0,1]$ with:

$$f_{X,n}^R(x,\omega ):=\frac{1}{n}\#\{t\in \{1,2,\dots ,n\}\mid (x,X\left(T^t\left(\omega \right)\right))\in R\}.$$

We want to show that $f_{X,n}^R(x,\omega )$ converges to $f_X^R\left(x\right)$ for all $x\in \mathbb{R}$ and $\mu$-almost all $\omega \in \Omega$. If $f_{X,n}^R(x,\omega )$ is monotone in x for all $\omega \in \Omega$ and $n\in \mathbb{N}$, this can be shown relatively easily using the pointwise ergodic theorem and the monotonicity of the considered functions. Monotonicity is guaranteed, if $x_1\le x_2$ implies:

$$\{y\in \mathbb{R}\mid (x_1,y)\in \mathbb{R}\}\subseteq \{y\in \mathbb{R}\mid (x_2,y)\in \mathbb{R}\}.$$

For example, if $R=\{(x,y)\in {\mathbb{R}}^2\mid x>y\}$, the above implication holds true. For this special case, a proof of the statement in Lemma 5 can be found in [4].

However, we are interested in general sets $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$ and therefore, cannot use the monotonicity. Therefore, we have to prove this statement differently.

Lemma 5.

Let $(\Omega ,\mathcal{A},\mu ,T)$ be an ergodic measure-preserving dynamical system,$\mathit{X}=(X_1,X_2,\dots ,X_d)$ be a random vector and $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$ satisfy (8). Then, for all $i\in \{1,2,\dots ,d\}$, there exist sets $\tilde{\Omega }\in \mathcal{A}$ and $B\in \mathcal{B}\left(\mathbb{R}\right)$ with $\mu \left(\tilde{\Omega }\right)={\mu }_{X_i}\left(B\right)=1$ satisfying:

$$\underset{n\to \infty }{lim}{f}_{X_i,n}^R(x,\omega )=f_{X_i}^R\left(x\right)$$

for all $\omega \in \tilde{\Omega }$ and $x\in B$.

Proof. 

Fix $i\in \{1,2,\dots ,d\}$. According to (8), there exists a countable set

$C=\{(a_k,b_k)\mid k\in \mathbb{N}\}$ with:

$${\mu }_{X_i}^2(\partial R\backslash C)=0.$$

By the pointwise ergodic theorem (see, e.g., [10]), for all $j,k\in \mathbb{N}$, there exists ${\Omega }_{j,k}^{*}\in \mathcal{A}$ with $\mu \left({\Omega }_{j,k}^{*}\right)=1$ and:

$$\underset{n\to \infty }{lim}{f}_{X_i,n}^{\left\{(a_k,b_k)\right\}}(a_j,\omega )=f_{X_i}^{\left\{(a_k,b_k)\right\}}\left(a_j\right)$$

for all $\omega \in {\Omega }_{j,k}^{*}$. It is easy to see that:

$$f_{X_i,n}^{\left\{(a_k,b_k)\right\}}(x,\omega )=0=f_{X_i}^{\left\{(a_k,b_k)\right\}}\left(x\right)$$

holds true for all $n\in \mathbb{N}$ and $\omega \in \Omega$ if $x\ne a_k$. Hence:

$$\underset{n\to \infty }{lim}{f}_{X_i,n}^{\left\{(a_k,b_k)\right\}}(x,\omega )=f_{X_i}^{\left\{(a_k,b_k)\right\}}\left(x\right)$$

(20)

for all $x\in \mathbb{R}$ and $\omega \in {\bigcap }_{j=1}^{\infty }{\Omega }_{j,k}^{*}$. Using Fatou’s lemma and the fact that C is countable implies:

$$\begin{array}{cc}\hfill \underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{R\cap C}(x,\omega )& =\underset{n\to \infty }{lim\; inf}\sum _{\begin{array}{c}k\in \mathbb{N}:\\ (a_k,b_k)\in R\end{array}}{f}_{X_i,n}^{\left\{(a_k,b_k)\right\}}(x,\omega )\hfill \\ & \ge \sum _{\begin{array}{c}k\in \mathbb{N}:\\ (a_k,b_k)\in R\end{array}}\underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{\left\{(a_k,b_k)\right\}}(x,\omega )\hfill \\ \hfill & \stackrel{\left(20\right)}{=}\sum _{\begin{array}{c}k\in \mathbb{N}:\\ (a_k,b_k)\in R\end{array}}{f}_{X_i}^{\left\{(a_k,b_k)\right\}}\left(x\right)=f_{X_i}^{R\cap C}\left(x\right)\hfill \end{array}$$

(21)

for all $x\in \mathbb{R}$ and $\omega \in {\bigcap }_{j=1}^{\infty }{\bigcap }_{k=1}^{\infty }{\Omega }_{j,k}^{*}$. We will use this fact later.

Since $R\backslash \partial R$ is open, there exists a countable collection of pairwise disjoint rectangles $A_j\subseteq {\mathbb{R}}^2$ with:

$$R\backslash \partial R=\bigcup _{j=1}^{\infty }{A}_j.$$

(22)

Take $(x_j,y_j)\in A_j$ for all $j\in \mathbb{N}$. Using the pointwise ergodic theorem, for all $j\in \mathbb{N}$ there exists a set ${\Omega }_j\in \mathcal{A}$ with $\mu \left({\Omega }_j\right)=1$ and:

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}{f}_{X_i,n}^{A_j}(x_j,\omega )=f_{X_i}^{A_j}\left(x_j\right)\end{array}$$

(23)

for all $\omega \in {\Omega }_j$. Because $A_j$ is a rectangle, for all $\omega \in \Omega$:

$$\begin{array}{cc}\hfill f_{X_i,n}^{A_j}(x,\omega )& =f_{X_i,n}^{A_j}(x_j,\omega )\hfill \\ \hfill \mathrm{and}{f}_{X_i}^{A_j}\left(x\right)& =f_{X_i}^{A_j}\left(x_j\right)\hfill \end{array}$$

holds true for all $x\in \mathbb{R}$ with $\left\{x\right\}\times \mathbb{R}\cap A_i\ne \varnothing$ and:

$$\begin{array}{c}\hfill f_{X_i,n}^{A_j}(x,\omega )=f_{X_i}^{A_j}\left(x\right)=0\end{array}$$

holds true for all $x\in \mathbb{R}$ with $\mathbb{R}\times \left\{x\right\}\cap A_i=\varnothing$. Together with (23), this implies:

$$\underset{n\to \infty }{lim}{f}_{X_i,n}^{A_j\backslash C}(x,\omega )=f_{X_i}^{A_j\backslash C}\left(x\right)$$

(24)

for all $x\in \mathbb{R}$ and $\omega \in {\Omega }_j$.

Set $R_J:={\bigcup }_{j=1}^J{A}_j$. Lemma 4 provides:

$$\begin{array}{cc}\hfill & \underset{J\to \infty }{lim}\int \left|f_{X_i}^{R_J\backslash C}\left(x\right)-f_{X_i}^{R\backslash C}\left(x\right)\right|\mathrm{d}{\mu }_X\left(x\right)\hfill \\ \hfill & =\underset{J\to \infty }{lim}{\mu }_{X_i}^2((R_J\backslash C)▵(R\backslash C))\hfill \\ \hfill & =\underset{J\to \infty }{lim}{\mu }_{X_i}^2((R\backslash C)\backslash (R_J\backslash C))\hfill \\ \hfill & =\underset{J\to \infty }{lim}{\mu }_{X_i}^2(R\backslash (R_J\cup C))\hfill \\ \hfill & =\underset{J\to \infty }{lim}{\mu }_{X_i}^2(((R\cap \partial R)\cup (R\backslash \partial R))\backslash (R_J\cup C))\hfill \\ \hfill & =\underset{J\to \infty }{lim}{\mu }_{X_i}^2((R\cap \partial R)\backslash (R_J\cup C))+{\mu }_{X_i}^2((R\backslash \partial R)\backslash (R_J\cup C))\hfill \\ \hfill & \le \underset{J\to \infty }{lim}{\mu }_{X_i}^2(\partial R\backslash C)+{\mu }_{X_i}^2((R\backslash \partial R)\backslash R_J)\hfill \\ \hfill & \stackrel{\left(8\right)}{=}\underset{J\to \infty }{lim}{\mu }_{X_i}^2((R\backslash \partial R)\backslash R_J)\hfill \\ \hfill & \stackrel{\left(22\right)}{=}{\mu }_{X_i}^2((R\backslash \partial R)\backslash (R\backslash \partial R))=0.\hfill \end{array}$$

Therefore, there exists a set $B_1$ with ${\mu }_{X_i}\left(B_1\right)=1$ and a sequence ${\left(J_k\right)}_{k\in \mathbb{N}}$ with:

$$\underset{k\to \infty }{lim}{f}_{X_i}^{R_{J_k}\backslash C}\left(x\right)=f_{X_i}^{R\backslash C}\left(x\right)$$

(25)

for all $x\in B_1$. Thus:

$$\begin{array}{cc}\hfill \underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^R(x,\omega )& \ge \underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{R\cap C}(x,\omega )+\underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{R\backslash C}(x,\omega )\hfill \\ \hfill & \stackrel{\left(21\right)}{\ge }{f}_{X_i}^{R\cap C}\left(x\right)+\underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{R_{J_k}\backslash C}(x,\omega )\hfill \\ \hfill & \ge f_{X_i}^{R\cap C}\left(x\right)+\underset{k\to \infty }{lim}\underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{R_{J_k}\backslash C}(x,\omega )\hfill \\ \hfill & =f_{X_i}^{R\cap C}\left(x\right)+\underset{k\to \infty }{lim}\underset{n\to \infty }{lim\; inf}\sum _{j=1}^{J_k}{f}_{X_i,n}^{A_j\backslash C}(x,\omega )\hfill \\ \hfill & \ge f_{X_i}^{R\cap C}\left(x\right)+\underset{k\to \infty }{lim}\sum _{j=1}^{J_k}\underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{A_j\backslash C}(x,\omega )\hfill \\ \hfill & \stackrel{\left(24\right)}{=}{f}_{X_i}^{R\cap C}\left(x\right)+\underset{k\to \infty }{lim}\sum _{j=1}^{J_k}{f}_{X_i}^{A_j\backslash C}\left(x\right)\hfill \\ \hfill & =f_{X_i}^{R\cap C}\left(x\right)+\underset{k\to \infty }{lim}{f}_{X_i}^{R_{J_k}\backslash C}\left(x\right)\hfill \\ \hfill & \stackrel{\left(25\right)}{=}{f}_{X_i}^{R\cap C}\left(x\right)+f_{X_i}^{R\backslash C}\left(x\right)\hfill \\ \hfill & =f_{X_i}^R\left(x\right)\hfill \end{array}$$

for all $x\in B_1$ and $\omega \in {\tilde{\Omega }}_1:={\bigcap }_{j=1}^{\infty }{\bigcap }_{k=1}^{\infty }{\Omega }_j\cap {\Omega }_{j,k}^{*}$. Because $R^c\backslash \partial R$ is open as well, one can analogously show that there exist sets ${\tilde{\Omega }}_2\in \mathcal{A}$ and $B_2\in \mathcal{B}\left(\mathbb{R}\right)$ with $\mu \left({\tilde{\Omega }}_2\right)={\mu }_{X_i}\left(B_2\right)=1$ and:

$$\underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{R^c}(x,\omega )\ge f_{X_i}^{R^c}\left(x\right)$$

for all $x\in B_2$ and $\omega \in {\tilde{\Omega }}_2$. This implies:

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim\; sup}{f}_{X_i,n}^R(x,\omega )=1-\underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^{R^c}(x,\omega )\le 1-f_{X_i}^{R^c}\left(x\right)=f_{X_i}^R\left(x\right).\end{array}$$

Hence:

$$f_{X_i}^R\left(x\right)\le \underset{n\to \infty }{lim\; inf}{f}_{X_i,n}^R(x,\omega )\le \underset{n\to \infty }{lim\; sup}{f}_{X_i,n}^R(x,\omega )\le f_{X_i}^R\left(x\right)$$

(26)

for all $x\in B:=B_1\cap B_2$ and $\omega \in \tilde{\Omega }:={\tilde{\Omega }}_1\cap {\tilde{\Omega }}_2$. □

Given a random vector $(X_1,X_2,\dots ,X_d)$ and $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$, we define the partition:

$${\mathcal{R}}_i:={(X_i,X_i)}^{-1}\left(\{R,R^c\}\right)$$

for all $i\in \{1,2,\dots ,d\}$, which is equal to:

$$\begin{array}{cc}\hfill {\mathcal{R}}_i=\{& \{({\omega }_1,{\omega }_2)\in {\Omega }^2\mid (X_i\left({\omega }_1\right),X_i\left({\omega }_2\right))\in R\},\hfill \\ \hfill & \{({\omega }_1,{\omega }_2)\in {\Omega }^2\mid (X_i\left({\omega }_1\right),X_i\left({\omega }_2\right))\notin R\}\}.\hfill \end{array}$$

Lemma 1.

Let $(\Omega ,\mathcal{A},\mu ,T)$ be an ergodic measure-preserving dynamical system,$\mathit{X}=(X_1,X_2,\dots ,X_d):\Omega \to {\mathbb{R}}^d$ be a random vector, ${\left(E_n\right)}_{n\in \mathbb{N}}$ be a timing and $R\in \mathcal{B}\left({\mathbb{R}}^2\right)$ satisfying (8). Then, there exists a sequence ${\left(n_k\right)}_{k\in \mathbb{N}}\subseteq {\mathbb{N}}_0^{\mathbb{N}}$ with:

$$\underset{k\to \infty }{lim}H\left(T^{-n_k}\left({(f_{X_i}\circ X_i)}^{-1}\left({\mathcal{U}}_N\right)\right)\left|\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left(\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right)\right.\right)=0$$

for all $N\in \mathbb{N}$ and $i\in \{1,2,\dots ,d\}$.

Proof. 

Because ${\left(E_n\right)}_{n\in \mathbb{N}}$ is a timing, there exist a sequence ${\left(a_n\right)}_{n\in \mathbb{N}}\in {\mathbb{N}}_0^{\mathbb{N}}$ with:

$$\underset{N\to \infty }{lim\; sup}\frac{\#\left\{n\in \{1,2,\dots ,N\}\mid (a_n,a_n+n)\in {\bigcup }_{k=1}^{\infty }{E}_k\right\}}{N}=1.$$

So one can find a strictly increasing sequence ${\left(N_n\right)}_{n\in \mathbb{N}}\in {\mathbb{N}}^{\mathbb{N}}$ with:

$$(a_{N_n},a_{N_n}+N_n)\in \bigcup _{k=1}^{\infty }{E}_k$$

for all $n\in \mathbb{N}$ and:

$$\underset{n\to \infty }{lim\; sup}\frac{n}{N_n}=1.$$

(27)

Now, fix $i\in \{1,2,\dots ,d\}$. According to Lemma 5, there exist sets $\tilde{\Omega }\in \mathcal{A}$ and $B\in \mathcal{B}\left(\mathbb{R}\right)$ with $\mu \left(\tilde{\Omega }\right)={\mu }_{X_i}\left(B\right)=1$ satisfying:

$$\underset{n\to \infty }{lim}{f}_{X_i,n}^R(\omega ,x)=f_{X_i}^R\left(x\right)$$

for all $\omega \in \tilde{\Omega }$ and $x\in B$. Set

$${\Omega }_0:=\tilde{\Omega }\cap X_i^{-1}\left(B\right).$$

Consider the function ${\varphi }_n:\Omega \to [0,1]$ with:

$${\varphi }_n\left(\omega \right):=\frac{1}{N_n}\#\{t\in \{N_1,N_2,\dots ,N_n\}\mid (X_i\left(T^t\left(\omega \right)\right),X_i\left(\omega \right))\in R\}.$$

Then:

$$\begin{array}{cc}\hfill & f_{X_i}^R\left(X_i\left(\omega \right)\right)\hfill \\ \hfill =& \underset{n\to \infty }{lim}{f}_{X_i,n}^R(\omega ,X_i\left(\omega \right))\hfill \\ \hfill =& \underset{n\to \infty }{lim\; sup}{f}_{X_i,N_n}^R(\omega ,X_i\left(\omega \right))\hfill \\ \hfill \ge & \underset{n\to \infty }{lim\; sup}{\varphi }_n\left(\omega \right)\hfill \\ \hfill =& \underset{n\to \infty }{lim\; sup}\left[f_{X_i,N_n}^R(\omega ,X_i\left(\omega \right))\right.\hfill \\ \hfill & -\left.\frac{1}{N_n}\#\{t\in \{1,2,\dots ,N_n\}\backslash \{N_1,N_2,\dots ,N_n\}\mid (X_i\left(T^t\left(\omega \right)\right),X_i\left(\omega \right))\in R\}\right]\hfill \\ \hfill \ge & \underset{n\to \infty }{lim\; sup}\left[f_{X_i,N_n}^R(\omega ,X_i\left(\omega \right))-\frac{1}{N_n}\#\{1,2,\dots ,N_n\}\backslash \{N_1,N_2,\dots ,N_n\}\right]\hfill \\ \hfill =& \underset{n\to \infty }{lim\; sup}\left[f_{X_i,N_n}^R(\omega ,X_i\left(\omega \right))-\frac{N_n-n}{N_n}\right]\hfill \\ \hfill =& \underset{n\to \infty }{lim}{f}_{X_i,N_n}^R(\omega ,X_i\left(\omega \right))-1+\underset{n\to \infty }{lim\; sup}\frac{n}{N_n}\hfill \\ \hfill \stackrel{\left(27\right)}{=}& f_{X_i}^R\left(X_i\left(\omega \right)\right)\hfill \end{array}$$

(28)

for all $\omega \in {\Omega }_0$.

It is easy to see that:

$$\sigma \left({\varphi }_n\right)\subseteq \sigma \left(\underset{t=1}{\overset{k}{\bigvee }}{\left(id,T^{N_t}\right)}^{-1}\left({\mathcal{R}}_i\right)\mid k\in \mathbb{N}\right)$$

holds true for all $n\in \mathbb{N}$. This implies (see for instance [11], Theorem 13.4 (i)):

$$\sigma \left(f_{X_i}^R\circ X_i\right)\stackrel{\left(28\right)}{{=}_{\mu }}\sigma \left(\underset{n\to \infty }{lim\; sup}{\varphi }_n\right)\subseteq \sigma \left(\underset{t=1}{\overset{k}{\bigvee }}{\left(id,T^{N_t}\right)}^{-1}\left({\mathcal{R}}_i\right)\mid k\in \mathbb{N}\right).$$

Therefore ${\bigvee }_{t=1}^k{\left(id,T^{N_t}\right)}^{-1}\left({\mathcal{R}}_i\right)$ is a sequence of partitions generating $\sigma \left(f_{X_i}^R\circ X_i\right)$. By (19), this implies:

$$\underset{k\to \infty }{lim}H\left({(f_{X_i}\circ X_i)}^{-1}\left({\mathcal{U}}_N\right)\left|\underset{t=1}{\overset{k}{\bigvee }}{\left(id,T^{N_t}\right)}^{-1}\left({\mathcal{R}}_i\right)\right.\right)=0$$

(29)

for all $N\in \mathbb{N}$. Set:

$$n_k:=\underset{1\le n\le k}{max}{a}_{N_n}.$$

Notice that:

$$\sigma \left(T^{-n_k}\left(\underset{t=1}{\overset{k}{\bigvee }}{\left(id,T^{N_t}\right)}^{-1}\left({\mathcal{R}}_i\right)\right)\right)\subseteq \sigma \left(\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left(\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right)\right)$$

holds true for all $k\in \mathbb{N}$. Consequently:

$$\begin{array}{cc}\hfill & \underset{k\to \infty }{lim}H\left(T^{-n_k}\left({(f_{X_i}\circ X_i)}^{-1}\left({\mathcal{U}}_N\right)\right)\left|\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left(\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right)\right.\right)\hfill \\ \hfill & \le \underset{k\to \infty }{lim}H\left(T^{-n_k}\left({(f_{X_i}\circ X_i)}^{-1}\left({\mathcal{U}}_N\right)\right)\left|T^{-n_k}\left(\underset{t=1}{\overset{k}{\bigvee }}{\left(id,T^{N_t}\right)}^{-1}\left({\mathcal{R}}_i\right)\right)\right.\right)\hfill \\ \hfill & =\underset{k\to \infty }{lim}H\left({(f_{X_i}\circ X_i)}^{-1}\left({\mathcal{U}}_N\right)\left|\underset{t=1}{\overset{k}{\bigvee }}{\left(id,T^{N_t}\right)}^{-1}\left({\mathcal{R}}_i\right)\right.\right)\stackrel{\left(29\right)}{=}0\hfill \end{array}$$

for all $N\in \mathbb{N}$. □

We can now finalize the proof of Theorem 1.

Proof of Theorem 1.

Let $N\in \mathbb{N}$ and $m\in \mathbb{N}$. Set:

$${\mathcal{P}}_N^i:=X_i^{-1}\left(f_{X_i}^{-1}\left({\mathcal{U}}_N\right)\right)$$

and:

$${\mathcal{Q}}_k^i:=\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)$$

for all $i\in \{1,2,\dots ,d\}$ and $k\in \mathbb{N}$. According to Lemma 1, there exists a sequence ${\left(n_k\right)}_{k\in \mathbb{N}}\subseteq {\mathbb{N}}_0^{\mathbb{N}}$ with:

$$\underset{k\to \infty }{lim}H\left(T^{-n_k}\left({\mathcal{P}}_N^i\right)\left|\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left({\mathcal{Q}}_k^i\right)\right.\right)=0$$

(30)

for all $i\in \{1,2,\dots ,d\}$. We have:

$$\begin{array}{cc}\hfill & \underset{n\to \infty }{lim}\frac{1}{n}H\left(\underset{i=1}{\overset{d}{\bigvee }}\underset{u=0}{\overset{nm-1}{\bigvee }}{T}^{-u}\left({\mathcal{P}}_N^i\right)\left|\underset{i=1}{\overset{d}{\bigvee }}\underset{u=0}{\overset{nm-1}{\bigvee }}{T}^{-u}\left({\mathcal{Q}}_k^i\right)\right.\right)\hfill \\ \hfill \le & \sum _{i=1}^d\underset{n\to \infty }{lim}\frac{1}{n}H\left(\underset{u=0}{\overset{nm-1}{\bigvee }}{T}^{-u}\left({\mathcal{P}}_N^i\right)\left|\underset{u=0}{\overset{nm-1}{\bigvee }}{T}^{-u}\left({\mathcal{Q}}_k^i\right)\right.\right)\hfill \\ \hfill =& \sum _{i=1}^d\underset{n\to \infty }{lim}\frac{1}{n}H\left(\underset{u=0}{\overset{nm-1-n_k}{\bigvee }}{T}^{-u}\left(T^{-n_k}\left({\mathcal{P}}_N^i\right)\right)\left|\underset{u=0}{\overset{nm-1-n_k}{\bigvee }}{T}^{-u}\left(\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left({\mathcal{Q}}_k^i\right)\right)\right.\right)\hfill \\ \hfill \le & \sum _{i=1}^d\underset{n\to \infty }{lim}\frac{1}{n}\sum _{u=0}^{nm-1-n_k}H\left(T^{-u}\left(T^{-n_k}\left({\mathcal{P}}_N^i\right)\right)\left|\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left({\mathcal{Q}}_k^i\right)\right.\right)\hfill \\ \hfill =& \sum _{i=1}^d\underset{n\to \infty }{lim}\frac{nm-1-n_k}{n}H\left(T^{-n_k}\left({\mathcal{P}}_N^i\right)\left|\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left({\mathcal{Q}}_k^i\right)\right.\right)\hfill \\ \hfill \le & \sum _{i=1}^{d}m·H\left(T^{-n_k}\left({\mathcal{P}}_N^i\right)\left|\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left({\mathcal{Q}}_k^i\right)\right.\right)\hfill \end{array}$$

for all $k,m,N\in \mathbb{N}$. This implies:

$$\begin{array}{cc}\hfill & h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{u=0}{\overset{m-1}{\bigvee }}{T}^{-u}\left({\mathcal{P}}_N^i\right)\right)-\underset{k\to \infty }{lim}h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{u=0}{\overset{m-1}{\bigvee }}{T}^{-u}\left({\mathcal{Q}}_k^i\right)\right)\hfill \\ \hfill & \le \underset{k\to \infty }{lim}\underset{n\to \infty }{lim}\frac{1}{n}H\left(\underset{i=1}{\overset{d}{\bigvee }}\underset{u=0}{\overset{nm-1}{\bigvee }}{T}^{-u}\left({\mathcal{P}}_N^i\right)\left|\underset{i=1}{\overset{d}{\bigvee }}\underset{u=0}{\overset{nm-1}{\bigvee }}{T}^{-u}\left({\mathcal{Q}}_k^i\right)\right.\right)\hfill \\ \hfill & \le \underset{k\to \infty }{lim}\sum _{i=1}^{d}m·H\left(T^{-n_k}\left({\mathcal{P}}_N^i\right)\left|\underset{v=0}{\overset{n_k}{\bigvee }}{T}^{-v}\left({\mathcal{Q}}_k^i\right)\right.\right)\stackrel{\left(30\right)}{=}0.\hfill \end{array}$$

Using Lemma 3, we can conclude that there exists a constant $c\in \mathbb{R}$ with:

$$\begin{array}{cc}\hfill h\left(T^m\right)& \le \underset{k\to \infty }{lim}h\left(T^m,\underset{i=1}{\overset{d}{\bigvee }}\underset{u=0}{\overset{m-1}{\bigvee }}{T}^{-u}\left(\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right)\right)+c\hfill \\ \hfill & =\underset{k\to \infty }{lim}m·h\left(T,\underset{i=1}{\overset{d}{\bigvee }}\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right)+c\hfill \end{array}$$

for all $m\in \mathbb{N}$. Thus:

$$\begin{array}{cc}\hfill & h\left(T\right)-\underset{k\to \infty }{lim}h\left(T,\underset{i=1}{\overset{d}{\bigvee }}\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right)\hfill \\ \hfill & =\underset{m\to \infty }{lim}\frac{1}{m}·h\left(T^m\right)-\underset{k\to \infty }{lim}h\left(T,\underset{i=1}{\overset{d}{\bigvee }}\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right)\hfill \\ \hfill & \le \underset{m\to \infty }{lim}\frac{1}{m}·c=0,\hfill \end{array}$$

which is equivalent to:

$$h\left(T\right)\le \underset{k\to \infty }{lim}h\left(T,\underset{i=1}{\overset{d}{\bigvee }}\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right).$$

(31)

On the other hand:

$$\begin{array}{c}\hfill h\left(T\right)=\underset{\mathcal{P}}{sup}h(T,P)\ge \underset{k\to \infty }{lim}h\left(T,\underset{i=1}{\overset{d}{\bigvee }}\underset{(s,t)\in E_k}{\bigvee }{(T^s,T^t)}^{-1}\left({\mathcal{R}}_i\right)\right),\end{array}$$

which, together with (31), finishes the proof. □

6. Conclusions

We discussed a special “two-dimensional” approach to symbolic dynamics differing from many usual approaches which was introduced in [6]. From the practical viewpoint, the difference can be illustrated as follows: given the time-dependent measurements of a real-valued quantity, a symbolization is not conducted for the measurements themselves as in usual approaches, but for pairs of measurements at two different times. This means that to each pair of possible measured values, a symbol from a finite symbol set is assigned. Here, we only considered two symbols which lead to a partitioning of the two-dimensional real space ${\mathbb{R}}^2$ into a set R and its complement ${\mathbb{R}}^2\backslash R$. In usual approaches, partitions of $\mathbb{R}$ are considered. (Advantages of the “two-dimensional” approach are described in [6]).

The set R, called a discriminating relation, was considered as a basic building block for constructing partitions of the state space of a given dynamical system, having time-dependent measurements of finitely many quantities in mind. In addition to the discrimination relation, the second central concept was the concept of a timing which roughly describes which pairs of times are included in the symbolization process and guarantees that there are not too few such pairs. The central question of the paper was that of under which conditions on a discriminating relation R the partitions constructed from R determine the KS entropy of a measure-preserving dynamical system. With Theorem 1, we gave a relatively general statement partially answering this question. Some specifications of the theorem in Section 4 illustrate the nature of “successful” discriminating relations.

Although the statement of Theorem 1 appears relatively natural when looking at the proofs a little closer, we do not expect that all cases where the K-S entropy can be constructed based on a discriminating relation is covered by the statement; however, we have no counterexample. The main tool used in the proofs of the results is the pointwise ergodic theorem. It allows to establish a connection between the generalized ordinal patterns and the shape of the discriminating relation.

The results of this paper, being on a rather abstract level, give some insights as to why the idea of ordinal patterns is working well, as reported by several applied papers, with extracting those advantageous features being more general than in the original ordinal approach. Having many choices for a discriminating relation, for practical purposes such as, for example, in a classification context, one needs methods and criteria for finding good discrimination relations, adapted to given data and problems. This is an important challenge for further research related to the given approach to symbolic dynamics. A further aspect is to discuss the approach for partitioning the ${\mathbb{R}}^2$ into more than two pieces.