1 Introduction
Let A be a countable set (called an alphabet),
$A^*$
be the set of finite words on A, and
$A^{\mathbb {Z}_+}$
be the set of infinite words on A, where
$\mathbb {Z}_+ = \{0,1,2,\ldots \}$
. A substitution is a map
$\sigma : A \to A^{*}$
. We assume that for every letter
$a \in A$
,
$\sigma (a) $
is not empty. We extend
$\sigma $
to
$A^*$
and
$A^{\mathbb {Z}_+}$
by concatenation and, to simplify the notation, we also denote these extensions by
$\sigma $
. Hence,
$\sigma (u_0 \ldots u_n)= \sigma (u_0) \ldots \sigma (u_n)$
for all
$u_0 \ldots u_n \in A^{*}$
and
$\sigma (u_0 u_1 \ldots )= \sigma (u_0) \sigma (u_1)\ldots $
for all
$u_0 u_1 \ldots \in A^{\mathbb {Z}_+}.$
We assume that there exists a letter a in A such that the length of the finite word
$\sigma ^{n}(a)$
converges to infinity as n goes to infinity.
To any substitution
$\sigma $
, we can associate a shift dynamical system
$(\Omega _\sigma , S)$
, where
$$ \begin{align*} \Omega_\sigma = \{ u \in A^{\mathbb{Z}_+} : \, \textrm{any finite factor of } u \textrm{ occurs in } \sigma^n (a) \textrm{ for some } n\in \mathbb{N} \textrm{ and } a\in A\}, \end{align*} $$
$\mathbb {N} = \{1,2,\ldots \}$
, and S is the shift map given by
$$ \begin{align*}S(u_0 u_1\ldots)= u_1 u_2 \ldots \quad\mbox{for all } u= u_0 u_1\ldots \in A^{\mathbb{Z}_+}.\end{align*} $$
Shift dynamical systems associated to substitutions provide many important examples in ergodic theory and they have been well studied in the literature when the alphabet is finite (see for instance [Reference Pytheas Fogg, Berthé, Ferenczi, Mauduit and Siegel18, Reference Queffélec19]). It is classical that if
$\sigma $
is a primitive substitution on
$A= \{0,\ldots , d-1\},\; d \geq 2$
, i.e., there exists
$k \in \mathbb {N}$
such that for all
$a, b \in A$
, the letter b occurs in the word
$\sigma ^{k} (a)$
, then the dynamical system is minimal, uniquely ergodic with topological entropy
$0$
(see [Reference Michel16] and [Reference Queffélec19, Ch. 5]). Moreover,
$\Omega _\sigma $
is the closure of the orbit of any periodic point of
$\sigma $
.
The unique shift invariant probability measure
$\mu $
is given on cylinders
$[w]$
, where
$w=w_0 \ldots w_n$
,
$w_i \in A$
for
$i=0,\ldots ,n$
, is a finite word that occurs in u and
$[w]= \{u_0 u_1 \ldots \in \Omega _\sigma ,\; u_i=w_i,\; i=0,\ldots , n \}$
, by
$\mu [w]$
which is the frequency of occurrences of w in the periodic point u. Moreover, the vector
$(\mu [0], \ldots , \mu [d-1])$
is the normalized left Perron eigenvector associated to the dominant Perron–Frobenius eigenvalue of the matrix
$M_{\sigma }= (M_{ij})_{0 \leq i, j \leq d-1}$
associated to
$\sigma $
, where
$ M_{ij} := \vert \sigma (i) \vert _j$
is the number of occurrences of the letter j in the word
$\sigma (i)$
. However, it is known (see [Reference Canterini and Siegel2]) that if
$\sigma $
is of Pisot type, then the dynamical system
$(\Omega _\sigma , S)$
has good geometrical properties, in particular, it is semi-conjugated to a translation on the torus
$\mathbb {T}^{d-1}$
.
When the alphabet A is a topological compact set, many results are given in [Reference Durand, Ormes and Petite4, Reference Manibo, Rust and Walton13, Reference Queffélec19].
When A is countably infinite, the situation is more complicated and there are already some work on the subject, see for instance [Reference Bezugly, Jorgensen and Sanadhya1, Reference Durand, Ormes and Petite4, Reference Ferenczi6, Reference Manibo, Rust and Walton13]. One of the difficulties in studying ergodic properties of the dynamical system
$(\Omega _\sigma ,S)$
in such cases lies in the fact that the countably infinite matrix
$M_{\sigma }$
may present a larger number of possible behaviors. Specifically, consider an irreducible countably infinite matrix
$M= (M_{ij})_{i, j \in \mathbb {Z}_+}$
, which means for all
$i, j \in \mathbb {Z}_+$
, there exists an integer
$n \geq 1$
such that for all
$k \geq n,\; M^{k}_{ij}>0$
, where for the sake of simplicity, we write
$(M^{n})_{ij} = M^n_{ij}$
. It is known that for all
$i, j \in \mathbb {Z}_+,\; \lim _{n \to \infty } (M^n_{ij})^{1/n}= \unicode{x3bb} $
exists. We say that M is transient if and only if
$\sum _{n=0}^{+\infty } ({M^n_{ij}}/{\unicode{x3bb} ^n}) < + \infty , $
otherwise M is said to be recurrent. It is known that if M is recurrent, there are left and right eigenvectors l and r associated to
$\unicode{x3bb} $
, and when the scalar product
$l\cdot r$
is finite, we say that M is positive recurrent, otherwise M is said to be null recurrent. Thus, for instance, if the countably infinite matrix
$M_{\sigma }$
is irreducible, then it could be either transient or null recurrent or positive recurrent and each of these cases may be associated to a distinct behavior of
$(\Omega _\sigma ,S)$
.
For substitutions on countably infinite alphabets, an important study was initiated by Ferenczi in [Reference Ferenczi6]. In that paper, several results were proved, in particular, it considered the squared drunken substitution defined on
$A= 2 \mathbb {Z}$
by
$\sigma (n)= (n-2)nn (n+2), \; n \in A$
and proved that the dynamical system
$(\Omega _\sigma , S)$
is not minimal and has non-finite invariant measure. However, it is also shown that
$(\Omega _\sigma , S)$
has an infinite invariant measure
$\mu $
which is shift ergodic and has Krengel entropy equal to
$0$
.
Let us recall that
$\sigma $
is called left determined or determined to order
$1$
if there exists a non-negative integer N such that every w of length at least N which occurs on some element of
$\Omega _\sigma $
has a unique decomposition
$w = w_1 \ldots w_s$
, where each
$w_i = \sigma (a_i)$
for some
$a_i \in A$
, except that
$w_1$
may be only a suffix of
$\sigma (a_1)$
and
$w_s$
may be only a prefix of
$\sigma (a_s)$
, and the
$a_i,\; 1 \leq i \leq s-1$
are unique.
The definition of determined to order
$1$
was introduced in [Reference Martin14] (see also [Reference Mossé17, Definition 1]). In [Reference Ferenczi6], the author used the same definition and called it left determined. It is known that this condition is stronger than recognizability, see [Reference Mossé17].
In [Reference Ferenczi6], it is also proved that if
$\sigma $
is of constant length, left determined, and has an irreducible aperiodic positive recurrent matrix
$M_{\sigma }$
, then the associated shift dynamical system admits an ergodic probability invariant measure.
In [Reference Bezugly, Jorgensen and Sanadhya1], the authors constructed stationary and non-stationary generalized Bratteli–Vershik models for left determined, irreducible, aperiodic, and recurrent substitutions on an infinite countable alphabet. As a consequence, they proved that for a left determined substitution
$\sigma : \mathbb {Z} \to \mathbb {Z}$
with
$M_{\sigma }$
irreducible, aperiodic, and recurrent which is also of bounded size (the letters of all
$ \sigma (n) $
belong to the set
$\{n-t, n- t+1, \ldots , n+t\}$
, where
$t \in \mathbb {Z}$
is independent of n), there exists a shift invariant measure
$\mu $
on
$\Omega _\sigma $
.
It is also worth mentioning that an arithmetic study of substitutions on countably infinite alphabets was done in [Reference Mauduit15].
In this paper, unless explicitly indicated, we consider
$A= \mathbb {Z}_{+}$
and
$\sigma : A \to A^{*}$
a bounded length substitution (
$\sup \{ |\sigma (a)|, a \in A \}$
is finite) such that
$\sigma $
has a periodic point u and
$M= M_{\sigma }$
is irreducible and aperiodic. We prove that if
$M_{\sigma }$
satisfies
$$ \begin{align} \lim_{n \to +\infty} \sup_{i \in A} \frac{ M^{n} _{ij}} { \sum_{k=0}^{+\infty} M^n_{ik}}= 0 \quad\mbox{for all } j \in A, \end{align} $$
then the dynamical system
$(\Omega _{\sigma }, S)$
has no finite invariant measure. In particular, the last result holds for a subclass of substitutions
$\sigma $
such that
$M_{\sigma }$
is transient and
$\sigma $
has constant length, or
$M_{\sigma }$
is recurrent and has a left Perron eigenvector
$l= (l_i)_{i \geq 0} \not \in l^1$
.
We also prove that if
$M_{\sigma }$
is positive recurrent, then the dynamical system
$(\Omega _{\sigma }, S)$
has a shift invariant measure
$\mu $
which is finite if and only if
$M_{\sigma }$
has a left Perron eigenvector
$l \in l^1$
. Moreover, if
$\sigma $
has constant length and
$M_ \sigma $
has a power that is scrambling, then
$(\Omega _{\sigma }, S)$
has a unique shift invariant probability measure
$\mu $
. Let us recall that a non-negative matrix
$M= (M_{ij})_{i,j \geq 0}$
is said to be scrambling if there exists
$a>0$
such that
$$ \begin{align*}\sum_{j=0}^{+\infty} \min ( M_{i j}, M_{k j}) \geq a \quad\mbox{for all } i \neq k \in \mathbb{Z}_+.\end{align*} $$
Scrambling stochastic infinite countable matrices are very important, since a stochastic matrix
$P= (P_{ij})_{i, j \geq 0} $
is strongly ergodic (see Definition 2.12) if and only if a power of P is scrambling.
We also consider the case where
$\sigma $
is not a constant length substitution. We introduce the notions of strongly ergodic and
$\star $
-strongly ergodic matrices
$M_{\sigma }$
related to the convergence of
$$ \begin{align*} \frac{ M^{n} _{ij}} { \sum_{k=0}^{+\infty} M^n_{ik}}, \quad i, \, j \in A, \end{align*} $$
as
$n\rightarrow \infty $
. Then we show that if
$M_ \sigma $
has a right Perron eigenvector in
$l^{\infty }$
and has a power that is scrambling (
$M_ \sigma $
strongly ergodic), then
$(\Omega _{\sigma }, S)$
is minimal and has a unique shift invariant probability measure
$\mu $
.
A difference concerning substitutions on countable infinite alphabets that we should point out is that substitutions may not have a periodic point. In this paper, we consider
$M_\sigma $
irreducible and suppose the existence of a periodic point u, thus
$\Omega _\sigma $
is the closure of the orbit of any periodic point of
$\sigma $
. However, our results will remain valid for
$\sigma $
that have no periodic point, since instead of using the left determined condition, we use the true fact that any finite word V occurring in some element of
$\Omega _{\sigma }$
has a decomposition (not necessarily unique) as
$V=v_0\sigma (Z )w_0$
where
$v_0$
,
$w_0$
, and Z finite words occurring in some elements of
$\Omega _{\sigma }$
and
$\max (|v_0|, |w_0|) \leq \sup \{| \sigma (a)|,\; a \in A\}$
, where for all finite word
$z \in A^{*}, |z|$
denotes the length of z.
The paper is organized as follows. In §2, we give notation, definitions, and preliminary results. Section 3 is devoted to the main results of the paper.
2 Preliminaries and notation
As in §1, let A be a countable set (called an alphabet),
$A^*$
be the set of finite words on A, and
$A^{\mathbb {Z}_+}$
the set of infinite words on A. We denote a finite word on A by
$u_0 \ldots u_{n-1}$
for some
$n \ge 1$
and we call
$n= \vert u_0 \cdots u_{n-1}\vert $
its length. An infinite word on A will be denoted by
$u = u_0 u_1\ldots .$
For
$U= u_0 \ldots u_{n-1}$
and
$V= v_0 \ldots v_{m-1}$
in
$A^*$
, where
$n \geq m$
are positive integers, we denote
$$ \begin{align*} |U|_V = \{0 \leq k \leq n-m, u_k \ldots u_{k+m-1}= v_0 \ldots v_{m-1}\}, \end{align*} $$
which is the number of occurrences of V in U. Let
$u= u_0u_1 \ldots \in A^{\mathbb {Z}_+}$
and
$V \in A^{*}$
. We say that V occurs in u or V is a factor of u if
$V= u_k \ldots u_l$
for some integer
$0 \leq k \leq l$
. We denote by
$F_u$
the set of all factors of u.
On
$A^{\mathbb {Z}_+}$
, we consider the discrete product topology, which is metrizable and generated by the metric d defined on
$A^{\mathbb {Z}_+}$
by
$$ \begin{align*}d(u_0 u_1\ldots, v_0 v_1\ldots )= 0 \quad\mbox{if } u_0 u_1\ldots= v_0 v_1\ldots \end{align*} $$
and
$$ \begin{align*}d(u_0 u_1\ldots, v_0 v_1\ldots )=\frac{1}{2^{k_{0}}} \quad\mbox{where } k_0= \min \{i \geq 0,\; u_i \ne v_i\} \mbox { otherwise}.\end{align*} $$
A base for the discrete product topology is given by the cylinders
$$ \begin{align*}[w]= \{u_0 u_1 \ldots \in A^{\mathbb{Z}_+},\; u_i= w_i \text{ for all } 0 \leq i \leq k\},\end{align*} $$
for
$w= w_0 \ldots w_k \in A^*$
. The cylinders are clopen sets. When the alphabet A is finite, the set
$A^{\mathbb {Z}_+}$
is compact and is homeomorphic to a Cantor set. If A is infinite,
$A^{\mathbb {Z}_+}$
is closed but not compact.
Let
$\sigma : A \to A^{*}$
be a substitution. We will assume without loss of generality that
$A = \mathbb {Z}_+$
(and occasionally
$A= \mathbb {Z}$
in some examples). We define the infinite matrix
$M_{\sigma }= (M_{ij})_{ i, j \in \mathbb {Z}_+}$
by
$ M_{ij} = \vert \sigma (i) \vert _j$
. Observe that
$M_{\sigma }$
is the transpose of the substitution matrix given in [Reference Queffélec19]. It is easy to prove by induction that for all
$i, j \in A$
and for all integers
$n \in \mathbb {N}$
,
$$ \begin{align*} | \sigma^n (i) |_j = M^n_{i j},\quad | \sigma^n (i) | = \sum_{j =1}^{\infty} M^n_{i j}.\end{align*} $$
For example, if
$\sigma (n)= 0 (n+1) \mbox { for all } n \in \mathbb {Z}_+$
, then
$$ \begin{align} M_{\sigma}= {\left[ \begin{array}{cccccccccc} 1 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array} \right]}. \end{align} $$
We say that a substitution
$\sigma : A \to A^{*}$
is of constant length (respectively bounded length) if there exists an integer
$L \geq 1$
such that
$|\sigma (a)|= L$
(respectively
$|\sigma (a)|\leq L$
) for all
$ a \in A$
.
Observe that if
$\sigma $
has constant length L (respectively bounded length by L), then the sum of the coefficients of each line of the matrix
$M^n_{\sigma },\; n \in \mathbb {N}$
equals
$L^n$
(respectively
$\leq L^n$
).
In this paper, we will assume that
$\sigma $
is a bounded length substitution and there exists
$a \in A$
such that
$| \sigma ^n (a) |$
tends to infinity as n converges to infinity.
We define the language of a substitution
$\sigma $
on
$ A$
as the set
$F_{\sigma }$
of finite factors of
$\sigma ^n (a)$
for some integer
$n \geq 0$
and
$a \in A$
.
We will need some classical definitions from the theory of countable non-negative matrices, see [Reference Kitchens9, Reference Seneta20].
Definition 2.1. Let
$M= (M_{ij})_{i, j \in \mathbb {Z}_+}$
be an infinite non-negative matrix (not necessarily a substitution matrix). We say that M is irreducible if for all
$i, j \in \mathbb {Z}_+$
, there exists an integer
$k = k(i,j) \geq 1$
such that
$M^{k}_{ij}>0$
. Let
$i \in \mathbb {Z}_+$
. The number
$$ \begin{align*}p_{i}=\mathrm{gcd} \{n \in \mathbb{N},\; M^{n}_{ii}>0\}\end{align*} $$
is called the period of the state i. If M is irreducible, then there exists
$p\ge 1$
such that
$p_i=p$
for every
$i \in \mathbb {Z}_+$
and we say that M has period
$p \geq 1$
. We say that an irreducible matrix M is aperiodic if
$p=1$
and periodic otherwise.
Observe that
$M_{\sigma }$
in equation (2.1) is irreducible and aperiodic, and
$\sigma $
is a constant length substitution which has a fixed point
$u= \lim _{n \to \infty } \sigma ^{n}(0)$
since
$\sigma (0)= 01$
begins with
$0$
.
Remark 2.2. (See [Reference Kitchens9]) If a matrix
$M= (M_{ij})_{i, j \in \mathbb {Z}_+}$
is irreducible and aperiodic, then for all
$i, j \in \mathbb {Z}_+$
, there exists an integer
$n = n(i,j) \geq 1$
such that for all
$k \geq n,\; M^{k}_{ij}>0$
.
Remark 2.3. Let
$\sigma : A \to A^{*}$
be a substitution which has a fixed point and
$M_{\sigma }$
is irreducible. Since there exists
$i \in \mathbb {Z}_+$
such that
$M_{ii}>0$
, we deduce that
$M_{\sigma }$
is aperiodic.
Assume that
$M= (M_{ij})_{i, j \in \mathbb {Z}_+}$
is an irreducible and aperiodic non-negative matrix until the end of this section. It is known (see [Reference Queffélec19, Reference Vere-Jones21]) that there exists
$\unicode{x3bb} _M \in [0,\infty ]$
, called the Perron value of M, such that for all
$i, j \in \mathbb {Z}_+$
,
For all
$i, j \in \mathbb {Z}_+$
, put as usual
$M_{ij}^0 = \delta _{ij}$
, then consider the series
$$ \begin{align*} \overline M_{i j}(z)= \sum_{n=0}^{+\infty} M^n_{ij} z^n, \quad z \in \mathbb{C}. \end{align*} $$
Observe that the convergence radius of the series
$\overline M_{i j}(z)$
is equal to
$\unicode{x3bb} _M^{-1}$
. When there is no possibility of confusion, we will omit the subscript in
$\unicode{x3bb} _M$
and write simply
$\unicode{x3bb} $
.
Remark 2.4. Directly from the definition, if
$\hat M = C M$
for some
$C>0$
, then
$\unicode{x3bb} _{\hat M} = C \unicode{x3bb} _M$
. If
$\sigma $
is a substitution with constant length L, then
$P = M/L$
is a stochastic matrix and
$\unicode{x3bb} _M = L \unicode{x3bb} _P$
. Moreover, for the stochastic matrix P, clearly
$\unicode{x3bb} _P \leq 1$
and if
$\overline P_{ij} (1) = +\infty $
, then
$\unicode{x3bb} _P =1$
. Thus,
$\unicode{x3bb} _M \le L$
. Indeed it is enough to have
$\sigma $
with bounded length L, see Lemma 2.10.
We either have
$\overline M_{ij} (1/ \unicode{x3bb} ) < \infty $
for every
$i, j \in \mathbb {Z}_+$
, in this case, we say that M is transient, or
$\overline M_{ij} (1/ \unicode{x3bb} ) = \infty $
for every
$i, j \in \mathbb {Z}_+$
, and we say that M is recurrent. The class of irreducible, aperiodic recurrent matrices can be divided into two classes: positive recurrent matrices and null recurrent ones. To present the definitions, we need to introduce the series
$$ \begin{align*} L_{i j}(M, z)= L_{i j}( z)= \sum_{n=0}^{+\infty} l_{ij} (M, n) z^n ,\end{align*} $$
where
$l_{ij} (M, n)= l_{i,j}(n)$
is defined by:
$l_{ij} (0)= 0,\; l_{ij}(1) =M_{ij} \mbox { and }$
$$ \begin{align*} l_{ij} (n+1)= \sum_{s \ne i}^{+\infty} l_{is} (n) M_{s j} \quad\mbox{for all } n \geq 1. \end{align*} $$
The matrix M is said to be positive recurrent if
$$ \begin{align*} \sum_{n=0}^{+\infty} \frac{n l_{ii} (n)}{\unicode{x3bb} ^n} < +\infty , \end{align*} $$
otherwise we say that M is null recurrent.
An interesting result is that if M is an irreducible, aperiodic, and recurrent matrix with finite Perron value
$\unicode{x3bb}>0$
, then
$\unicode{x3bb} $
has strictly positive left and right eigenvectors l and r, unique up to multiples by a constant. Moreover, the scalar product
$l \cdot r $
is finite if and only if M is positive recurrent.
Remark 2.5. In §3.2, we will give examples of null recurrent non-negative matrices with constant length L having Perron value strictly smaller than L. These cases are associated to stochastic matrices with Perron value strictly smaller than
$1$
, so they are transient in probabilistic sense (see [Reference Durrett5]), but they might be null recurrent according to the above definition. This is not a novelty, see [Reference Kitchens9]. What is important here is also that we provide substitution matrices in our examples.
To state the next result, we still need to introduce another important series
$$ \begin{align*}R_{i j}(M, z)= R_{i j}( z)= \sum_{n=0}^{+\infty} r_{ij} (M, n) z^n ,\end{align*} $$
where
$r_{ij} (M, n)= r_{ij} (n)$
is defined by
$r_{ij} (0)= 0,\; r_{ij}(1) =M_{i,j}$
and
$$ \begin{align*}r_{ij} (n+1)= \sum_{s \ne j}^{+\infty} M_{i s} r_{sj} (n) \quad\mbox{for all } n \geq 1.\end{align*} $$
Lemma 2.6. (See [Reference Vere-Jones22] and [Reference Kitchens9, p. 211])
Let M be a non-negative, irreducible, and aperiodic matrix, with finite Perron value
$\unicode{x3bb}>0$
. Let
$i, j \in \mathbb {Z}_+$
.
-
(1) If M is positive recurrent, then
where
$$ \begin{align*} \lim_{n \to \infty} \frac{M^{n}_{ij}}{\unicode{x3bb}^{n}} = \frac{L_{ij}(1/ \unicode{x3bb})}{\mu (i)}= \frac {R_{ij}(1/ \unicode{x3bb})}{\mu (j)}>0 ,\end{align*} $$
$\mu (i)= \sum _{n=1}^{+\infty } n l_{ii} (n)/ \unicode{x3bb} ^n.$
-
(2) If M is transient or null recurrent, then
$ \lim _{n \to \infty } M^{n}_{ij}/ \unicode{x3bb} ^{n}= 0$
.
For all
$i, j \in \mathbb {Z}_+$
, let
$$ \begin{align*}l^ {(i)}= (L_{ik}(1/ \unicode{x3bb}))_{k \geq 0} \quad\mbox {and}\quad r^ {(j)}= (R_{sj}(1/ \unicode{x3bb}))_{s \geq 0}.\end{align*} $$
Lemma 2.7. (See [Reference Kitchens9, p. 203])
Let M be a non-negative, irreducible, aperiodic matrix, with finite Perron value
$\unicode{x3bb}>0$
.
-
(1) If M is recurrent, then for all
$i, j \in \mathbb {Z}_+$
,
$$ \begin{align*}l^ {(i)} M= \unicode{x3bb} l^ {(i)} \quad\mbox {and}\quad M r^ {(j)} = \unicode{x3bb} r^ {(j)}.\end{align*} $$
-
(2) If M is transient, then for all
$i, j \in \mathbb {Z}_+$
,
$$ \begin{align*}l^ {(i)} M \leq \unicode{x3bb} l^ {(i)} \quad\mbox {and}\quad M r^ {(j)} \leq \unicode{x3bb} r^ {(j)}.\end{align*} $$
Remark 2.8. Let
$M = ( M_{ij})_{i,j \geq 0}$
be a non-negative, irreducible, aperiodic positive recurrent matrix, with finite Perron value
$\unicode{x3bb}>0$
. By item (1) of Lemma 2.6 and item (1) of Lemma 2.7, the vector
$$ \begin{align} T_i= (t_{ij})_{j \geq 0} \quad\mbox{where } t_{ij}=\lim_{n \to \infty} M^{n}_{ij}/ \unicode{x3bb}^{n} \end{align} $$
is a left eigenvector for
$\unicode{x3bb} $
associated to M. Moreover, we have
$$ \begin{align} \lim_{n \to \infty } \frac{M^n_{i, j}}{ \unicode{x3bb}^n} = \frac{ l_j r_i}{\sum_{k=0}^{+\infty} l_k r_k} \end{align} $$
where
$l= (l_k)_{k \geq 0}$
and
$r= (r_k)_{k \geq 0}$
are respectively a left and a right Perron eigenvector of M (see [Reference Seneta20]).
Lemma 2.9. (See [Reference Kitchens9, Proposition 7.1.11, p. 204])
Let
$M= ( M_{ij})_{i,j \geq 0}$
be a non-negative, irreducible, aperiodic, and recurrent matrix with finite Perron value
$\unicode{x3bb} $
. Let
$Z= (z_{i})_{i \geq 0}$
be a sub invariant non-negative and non-zero eigenvector of
$M_{\sigma }$
associated to
$\unicode{x3bb} $
, that is,
$(Z M)_i \leq \unicode{x3bb} z_i$
for all
$i \geq 0$
and
$Z \neq 0$
, then Z is a left Perron eigenvector associated to M.
Lemma 2.10. Let
$M= ( M_{i j})_{i, j \in \mathbb {Z}_+}$
be a non-negative, irreducible, and aperiodic matrix with finite Perron value
$\unicode{x3bb} $
. The following results hold.
-
(1) If M has line sums uniformly bounded by
$L>0 $
, then
$\unicode{x3bb} \leq L$
. -
(2) If M is positive recurrent and has constant line sums equal to L, then
$\unicode{x3bb} = L$
. Moreover, L is the unique eigenvalue of M having non-negative probability left eigenvector.
Proof. (1) Suppose that M has line sums bounded by L, then for all integers
$j \geq 0$
and
$n \geq 1$
, we have
$$ \begin{align*}M^n_{jj} \leq \sum_{k=0}^{+\infty} M^n_{jk} \leq L^n.\end{align*} $$
We deduce by equation (2.2) that
$\unicode{x3bb} \leq L.$
(2) If M is positive recurrent and has constant line sums equal to L, then there exists
$l= (l_i)_{i \geq 0} \in l^1$
such that
$\sum _{i = 0}^{\infty }l_i=1$
and
$ l M = \unicode{x3bb} l$
, then
$\sum _{j = 0}^{\infty } \sum _{i = 0}^{\infty } l_i M_{i j} = \unicode{x3bb} $
, then
$L= \unicode{x3bb} $
. Using the same idea, we obtain that L is the unique eigenvalue of M having non-negative probability left eigenvector.
Definition 2.11. Let
$M= (M_{ij})_{i,j \geq 0}$
be a non-negative matrix. We say that M is scrambling if there exists
$a>0$
such that
$$ \begin{align*}\sum_{j=0}^{+\infty} \min ( M_{i j}, M_{k j}) \geq a \quad\mbox{for all } i \neq k \in \mathbb{Z}_+.\end{align*} $$
Note that a substitution matrix
$M_ \sigma $
has a power that is scrambling if and only if for some
$n\ge 1$
,
$$ \begin{align} \text{ for all } i, k \in A,\; \text{ there exists } j \in A \mbox { which occurs in } \sigma^n(i) \mbox { and } \sigma^n(k). \end{align} $$
Definition 2.12. Let
$P= (P_{ij})_{i, j \geq 0}$
be a non-negative stochastic matrix. We say that P is:
-
• ergodic if
$\lim _{n \to \infty } P^{n}_{i j}= \pi _j> 0$
for all
$i, j \in \mathbb {N}$
, where
$(\pi _j)_{j \geq 0}$
is a probability vector; -
• strongly ergodic if P is ergodic and if there exists a probability vector
$(\pi _i)_{i \geq 0}$
of non-negative real numbers such that
$\lim _{ n \to \infty } \|P^n - Q\|_s= 0$
, where Q is the infinite stochastic matrix with rows equal to
$(\pi _j)_{j \geq 0}$
and
$\| N\|_s= sup_{i \geq 0} \sum _{j=0}^{+\infty } |N_{ij}|$
for any infinite complex matrix
$N= ( N_{ij})_{i,j \geq 0}$
. In other words,
$$ \begin{align*}\lim_{n \to \infty} \sup_{i \geq 0} \sum_{j =0}^{\infty} |P^{n}_{ij} - \pi_{j}| = 0.\end{align*} $$
Remark 2.13. It was proved in [Reference Huang, Isaacson and Vinograde7] that if P is strongly ergodic, then P is uniformly geometrically ergodic, that is, there exist
$\beta \in (0,1)$
and a constant
$C>0$
such that
$$ \begin{align*} \vert P^{n}_{ij} - \pi_{j}\vert \leq C \beta^n \quad \text{for all } i,j, n \in \mathbb{Z}_+. \end{align*} $$
The converse is proved in [Reference Luecke and Isaacson12]. In particular, it is shown that P is strongly ergodic if and only if for some
$j \geq 0$
with
$\pi _j \geq 0$
, we have
$$ \begin{align} \lim_{n \to \infty} \sup_{i \geq 0} \vert P^{n}_{ij} - \pi_{j} \vert = 0. \end{align} $$
There is a nice characterization of the strong ergodicity (see [Reference Isaacson and Madsen8]). It is defined as follows. If
$P= (P_{ij})_{i, j \in \mathbb {N}}$
is a stochastic non-negative countable matrix, then P is strongly ergodic if and only if there exists an integer
$n \geq 1$
such that
$\delta (P^n) <1$
, where the
$\delta $
coefficient of any non-negative countable stochastic matrix
$N= (N_{ij})_{i, j \in \mathbb {N}}$
is
$$ \begin{align} \delta (N)= \frac{1}{2} \sup_{i, k \in \mathbb{N}} \sum_{j=0}^{+\infty} | N_{i j}- N_{k j}|. \end{align} $$
The number
$\delta (N)$
is called Dobrushin coefficient of N or coefficient of ergodicity of N (see for instance [Reference Dobrushin3, Reference Huang, Isaacson and Vinograde7, Reference Levin, Peres and Wilmer11, Reference Luecke and Isaacson12]). It is not difficult to show that
$$ \begin{align} \delta (N)= 1 - \inf_{i \neq k} \sum_{j=0}^{+\infty} \min ( N_{i j}, N_{k j}). \end{align} $$
Observe that
$\delta (N) <1$
if and only if N is scrambling. Hence, P is strongly ergodic if and only if there exists an integer
$n \geq 1$
, such that
$P^n$
is scrambling.
3 Irreducible aperiodic substitutions
3.1 Non-existence of finite invariant measure
In [Reference Ferenczi6], the author proved that if
$A= \mathbb {Z}$
and
$\sigma (n)= (n-1)nn (n+1), \; n \in A,$
then the dynamical system
$(\Omega _\sigma , S)$
has no finite invariant measure. We will extend this result in the next theorem.
Theorem 3.1. Let
$\sigma : \mathbb {Z}_+ \to \mathbb {Z}_+^{*}$
be a bounded length substitution such that
$\sigma $
has a periodic point u and
$M= M_{\sigma }$
is irreducible and aperiodic. If M satisfies
$$ \begin{align} \lim_{n \to +\infty} \sup_{i \in \mathbb{Z}_+} \frac{ M^{n} _{ij}} { \sum_{k=0}^{+\infty} M^n_{ik}}= 0 \quad\mbox{for all } j \in \mathbb{Z}_+, \end{align} $$
then the dynamical system
$(\Omega _{\sigma }, S)$
has no finite invariant measure.
Remark 3.2. One natural question is if the condition in equation (3.1) can be replaced by the weaker condition
$$ \begin{align} \lim_{n \to +\infty} \frac{ M^{n} _{ij}} { \sum_{k=0}^{+\infty} M^n_{ik}}= 0 \quad\mbox{for all } i, \, j \in \mathbb{Z}_+. \end{align} $$
This last condition is more natural and holds for a large class of substitutions
$\sigma $
such that
$M_{\sigma }$
is transient or null recurrent and
$\sigma $
has constant length, or
$M_{\sigma }$
is positive recurrent with left Perron eigenvector
$l= (l_k)_{k \geq 0} \not \in l^1$
, see Lemma 3.4 at the end of this section and also Remark 3.3 just below.
Proof of Theorem 3.1
Assume without loss of generality that
$u= u_0 u_1 \ldots $
is a fixed point of
$\sigma $
. By equation (3.1), we have that for all
$j \in \mathbb {Z}_+$
,
$$ \begin{align} \lim_{n \to +\infty} \sup_{a \in A} \frac{\vert \sigma^{n} (a) \vert_{j}}{ \vert \sigma^{n} (a)|}= 0. \end{align} $$
Now, assume that
$(\Omega _{\sigma }, S)$
has a finite invariant measure, then there exists a finite ergodic invariant measure
$\mu $
. By Birkhoff’s ergodic theorem, we deduce that for
$\mu $
almost all
$x \in \Omega _u$
,
$$ \begin{align} \lim_{N \to \infty} \frac{1}{N} \; \mathrm{card} \{ 0 \leq k \leq N-1 : \, S^k (x) \in [j]\} = \mu[j] \quad \text{for all } \, j \in \mathbb{Z}_+. \end{align} $$
Now, let
$x \in \Omega _\sigma $
satisfying equation (3.4) and
$N \in \mathbb {N} $
. Let
$V = u_m \ldots u_{m+N-1},\; m \in \mathbb {N}$
be a prefix of x. The word V can be written as
$$ \begin{align} V= v_0\sigma (v_1) \ldots \sigma^{n-1}(v_{n-1})\sigma^{n}(v_{n})\sigma^{n-1}(w_{n-1}) \ldots \sigma (w_1)w_0, \end{align} $$
where
$n \geq 1$
is an integer and
$v_i, \; i \in \{0,\ldots , n\}, \; w_j,\; j \in \{ 0,\ldots , n-1\}$
are elements of
$F_u$
possibly empty words of lengths smaller or equal to
$K= \max \{ |\sigma (b)|,\; b \in A\} $
and
$v_n$
is not empty. Equation (3.5) comes from the fact that since
$u= \sigma (u)$
, there exists
$a \in A$
and
$n \in \mathbb {N}$
such that V is a factor of
$\sigma ^{n+1}(a)$
and V is not a factor of
$\sigma ^n(a)$
. Hence, there exist
$v_0,w_0, V_1$
in
$F_u$
such that
$$ \begin{align*} V=v_0\sigma(V_1)w_0\end{align*} $$
and
$|v_0|,|w_0| \leq K$
. We proceed analogously with
$V_1$
, continuing by induction until the process stops and we obtain equation (3.5).
With our choice of x and its prefix V, from equations (3.4) and (3.5), we have that
$$ \begin{align*} &\frac{1}{N}\mathrm{card} \{ 0 \leq k \leq N-1, S^k (x) \in [j]\}\\ &\quad= \frac{|V|_{j }}{|V|} = \frac{| \sigma^n (v_n) |_{j}+ \sum_{k=0}^{n-1} (| \sigma^k (v_k) |_{j} + | \sigma^k (w_k) |_{j})}{| \sigma^n (v_n) |+ \sum_{k=0}^{n-1} (| \sigma^k (v_k) | + | \sigma^k (w_k) |)}. \end{align*} $$
By equation (3.3), we deduce that
$$ \begin{align} \lim_{k \to \infty} \sup \bigg\{ \frac{| \sigma^k (v) |_{j}}{ | \sigma^k (v) |},\; v \in F_u,\; |v| \leq K \bigg\}= 0. \end{align} $$
Using equation (3.6) and the Stolz–Cesaro theorem, we deduce that
$$ \begin{align*}\lim_{n \to \infty} \frac{| \sigma^n (v_n) |_{j}+ \sum_{k=0}^{n-1} (| \sigma^k (v_k) |_{j} + | \sigma^k (w_k) |_{j})}{| \sigma^n (v_n) |+ \sum_{k=0}^{n-1} (| \sigma^k (v_k) | + | \sigma^k (w_k) |)}=0.\end{align*} $$
Therefore,
$$ \begin{align*} \lim_{N \to \infty} \frac{1}{N} \; \mathrm{card} \{ 0 \leq k \leq N-1, S^k (x) \in [j]\} = \mu[j]=0. \end{align*} $$
Since j is arbitrary,
$\mu (\Omega )=0$
, which yields a contradiction.
Remark 3.3. It is important to notice that the condition in equation (3.1) may or may not hold on both the transient and the null recurrent cases. To see this, we consider examples where M is a multiple of an irreducible stochastic matrix P. In this situation, equation (3.1) is equivalent to
$$ \begin{align} \lim_{n \to +\infty} \sup_{i \in A} P^{n} _{i j} = 0 \quad\mbox{for all } j \in A. \end{align} $$
It is simple to find examples of stochastic matrices for which equation (3.7) does not hold. So we start with a first example that can be adapted to both transient and recurrent cases. Consider
$A = \mathbb {Z}$
and set
$P_{-n,-n-1} = q_n = 1 - P_{-n,-n+1}$
for
$n\ge 1$
, where
$q_n \in (0,1)$
and
$\sum _{n= 1}^{+\infty } q_n < \infty $
. Also put
$P_{0,-1} = P_{0,1} = 1/2$
and
$P_{m,-n}=0$
for
$m, n \ge 1$
. No matter how we complete the definition of P to obtain a irreducible and aperiodic matrix which may be recurrent or transient, we have that
$$ \begin{align*} \sup_{a \in A} P^{n}_{a,0} \ge P^{n}_{-n,0} \ge \prod_{k= 1}^{+\infty} (1-q_k)> 0 \quad \textrm{for every } n\ge 1. \end{align*} $$
Thus, equation (3.7) does not hold. However, since
$\lim _{n\rightarrow \infty } q_n = 0$
, there is no multiple of P which is a matrix M associated to a substitution. Thus, we will provide another example.
Again we consider
$A {\kern-1pt}={\kern-1pt} \mathbb {Z}$
and set
$P_{-2^n,0} {\kern-1pt}={\kern-1pt} 1/2 {\kern-1pt}={\kern-1pt} P_{-2^n,-2^n-1}$
and
$P_{-2^n-j,-2^n-j-1} {\kern-1pt}={\kern-1pt} 1$
for
$j=1,\ldots ,2^n-1$
and
$n\ge 1$
. We can check that
$P^{2^n}_{-2^{n-1}-1,0}=1/2$
. Again, no matter how we complete the definition of P, which may be recurrent or transient, we have that
$$ \begin{align*} \limsup_{n\rightarrow \infty} \sup_{a \in A} P^{n}_{a,0} \ge 1/2> 0, \end{align*} $$
thus equation (3.7) does not hold. In this case, we could define
$M_{-2^n,0} = 1 = M_{-2^n,-2^n-1}$
and
$M_{-2^n-j,-2^n-j-1} = 2$
and complete the definition for the other entries for M to have an irreducible and aperiodic matrix associated to a substitution of constant length equal to two. We have that
$P = M/2$
, thus equation (3.1) does not hold.
As a third example, we consider P as the transition matrix of a simple random walk on
$\mathbb {Z}$
, that is, we fix
$p\in (0,1)$
and set
$P_{n,n+1} = p = 1 - P_{n,n-1}$
for every
$n\in \mathbb {Z}$
(for basic properties of random walks, the reader can check [Reference Durrett5]). Notice that this Markov chain is irreducible with period two which is null recurrent if
$p=1/2$
and transient otherwise. The stochastic matrix P is irreducible and we can use
$P^2$
instead of P for an example with an aperiodic chain. A standard computation using the binomial distribution and Stirling formula shows that
$$ \begin{align*} \sup_{w\in \mathbb{Z}} P^n_{w,\tilde{w}} = \sup_{w\in \mathbb{Z}} P^n_{0,\tilde{w}-w} \le \max_{0\le k \le n} {n \choose k} p^k (1-p)^{n-k} = O(n^{-{1}/{2}}). \end{align*} $$
Thus, equation (3.7) holds. Here, we also have
$P = M/2$
, where M is a substitution matrix of constant length equal to
$2$
defined as
$$ \begin{align*} M_{n,n+1} = M_{n,n-1} = 1 \quad \text{for all } n\in \mathbb{Z}. \end{align*} $$
Thus, M satisfies equation (3.1).
Question 3.1. Under the hypothesis of Theorem 3.1, is the dynamical system
$(\Omega _{\sigma }, S)$
not minimal?
Question 3.2. Is the result of Theorem 3.1 still true if
$M_{\sigma }$
is transient, or recurrent with a left Perron eigenvector
$l= (l_i)_{i \geq 0} \not \in l^1$
and without the condition in equation (3.1)? Even in a little less general setting, is the result of Theorem 3.1 still true if
$M_{\sigma }$
satisfies the weaker condition in equation (3.2)?
We finish this section proving a result with conditions that imply the condition in equation (3.2).
Lemma 3.4. Let
$M= ( M_{i j})_{i, j \in \mathbb {Z}_+}$
be a non-negative, irreducible, and aperiodic matrix with finite Perron value
$\unicode{x3bb} $
. If M is transient with constant line sums, or M is positive recurrent with a left Perron eigenvector
$l= (l_k)_{k \geq 0} \not \in l^1$
, then
$$ \begin{align*} \lim_{n \to +\infty} \frac{ M^{n}_{ij}} { \sum_{k=0}^{+\infty} M^n_{ik}}= 0 \quad\mbox{for all } i, j \in \mathbb{Z}_+.\end{align*} $$
Proof. Assume that M is transient with constant line sums equal to L. Let
$i, j \in \mathbb {Z}_+$
. Since
$\unicode{x3bb} \leq L$
and
$\lim _{n \to +\infty } M^n_{ij}/ \unicode{x3bb} ^n =0$
, then
$$ \begin{align*} \frac{M^n_{ij}}{\sum_{k=0}^{+\infty} M^n_{ik}}= \frac{M^n_{ij}}{L^n} \le \frac{M^n_{ij}}{\unicode{x3bb}^n} \rightarrow 0 \quad \textrm{as } n \rightarrow \infty. \end{align*} $$
Now, let us suppose that M is positive recurrent and
$l= (l_k)_{k \geq 0} \not \in l^1$
is a left Perron eigenvector. Let
$i, j \in \mathbb {Z}_+$
. Since M is positive recurrent, we have by Remark 2.8 that
$$ \begin{align*}\lim_{n \to \infty} \frac{M^n_{i k}} {\unicode{x3bb}^n} = cl_k \quad\mbox {for all } k \in \mathbb{Z}_,\end{align*} $$
where
$c>0$
. Using the Fatou lemma for series and the fact
$l= (l_k)_{k \geq 0} \not \in l^1$
, we deduce that
$$ \begin{align*} \lim_{n \to +\infty} \frac {\sum_{k=0}^{+\infty} M^n_{ik} }{M^n_{ij}} \geq \frac {\sum_{k=0}^{+\infty} l_{k} }{l_{j}} = +\infty\end{align*} $$
and we are done.
Question 3.3. (1) If M is transient with non-constant line sums, is
$$ \begin{align*} \lim_{n \to +\infty} \frac{ M^{n} _{ij}} { \sum_{k=0}^{+\infty} M^n_{ik}}= 0 \quad\mbox{for all } i, j \in \mathbb{Z}_+?\end{align*} $$
Note that the answer is affirmative if
$$ \begin{align*} \liminf_{n \to +\infty} \frac{ M^{n} \mathbf{1}}{\unicode{x3bb}^n}> 0, \end{align*} $$
which is simple to verify in the finite dimensional case from linear algebra arguments. It is also true to check in the infinite dimensional case when M is transient and has a right Perron eigenvector
$r= (r_{i})_{ i \geq 0} \in l^{\infty }$
such that
$\inf \{ r_j, j \geq 0\}>0$
, since for all
$j \geq 0$
,
$$ \begin{align} \frac{\inf _{j} r_j}{ \sup _{j} r_j} \leq \frac{1}{\unicode{x3bb}^n} \sum_{k=0}^{+\infty} M^n_{ik} \leq \frac{\sup _{j} r_j}{ \inf _{j} r_j}. \end{align} $$
(2) Assume that M is recurrent with a left Perron eigenvector
$l= (l_k)_{k \geq 0} \in l^1$
. Does there exist
$i, j \in A$
such that
$$ \begin{align*} \lim_{n \to +\infty} \frac{ M^{n} _{ij}} { \sum_{k=0}^{+\infty} M^n_{ik}}> 0?\end{align*} $$
Again, from item (2) in Lemma 2.6, item (2) in Lemma 2.10, and equation (3.3), it is simple to check that this holds when M is positive recurrent and has a right Perron eigenvector
$r= (r_{i})_{ i \geq 0} \in l^{\infty }$
such that
$\inf \{ r_j, j \geq 0\}>0$
. In particular, in the case of lines with constant sums.
3.2 A class of examples
Let
$\sigma := \sigma _{a,b,c}$
be defined by
$$ \begin{align*}\sigma(0)= 0^{a+b} 1^c \quad\mbox {and}\quad \sigma(n)= (n-1)^a n^b (n+1)^c \quad\mbox{for all } n \geq 1,\end{align*} $$
where
$a, b, c$
are non-negative integers such that
$a>0$
,
$c>0$
, and
$i^k= i i \ldots i$
(k times). The matrix
$M_{\sigma }$
is irreducible and aperiodic. We have
$$ \begin{align*} M_{\sigma}= \begin{bmatrix} a+b & c & 0 & 0 & 0 & 0 & 0 & \cdots\\ a & b & c & 0 & 0 & 0 & 0 & \cdots\\ 0 & a & b & c & 0 & 0 & 0 & \cdots\\ 0 & 0 & a & b & c & 0 & 0 & \cdots\\ 0 & 0 & 0 & a & b & c & 0 & \cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{bmatrix}\!. \end{align*} $$
Note that
$\sigma $
is a substitution of constant length
$L=a+b+c$
. The stochastic matrix
$P = M_\sigma /L$
is the transition matrix of a homogeneous nearest-neighbor random walk in
$\{0,1,2,\ldots \}$
partially reflected at the boundary, see also the last example in Remark 3.3. It is well known, see [Reference Durrett5], that the random walk is (in the probabilistic sense) positive recurrent if
$c<a$
, null recurrent if
$c=a$
, and transient if
$c>a$
. The difference for the matrix theoretical definition is that we also have null recurrence in the case
$c>a$
, see also [Reference Kitchens9, Example 7.1.28] for the case
$b=0$
and
$a=c$
.
Proposition 3.5. The following properties hold:
-
• if
$c <a$
, then
$M_{\sigma }$
is positive recurrent; -
• if
$c \ge a$
, then
$M_{\sigma }$
is null recurrent and
$(\Omega _\sigma , S)$
has no finite invariant measure.
Proof. For the cases
$c<a$
and
$c=a$
, we have
$\unicode{x3bb} _P = 1$
, thus
$\unicode{x3bb} _{M_\sigma } = L$
. From the probabilistic results on transience/recurrence of random walks, we have that
$M_{\sigma }$
is positive recurrent for
$c<a$
and null recurrent for
$c=a$
.
Before we deal with the case
$c>a$
, let us point out that we can prove the result in the cases
$c<a$
and
$c=a$
by directly computing the Perron eigenvectors.
Let
$\unicode{x3bb} $
be the Perron value of
$M_{\sigma }$
, then by Lemma 2.10, we have
$\unicode{x3bb} \leq L= a+b+c$
. Let
$l= (l_{i})_{i \geq 0}$
be a left eigenvector of
$M_{\sigma }$
associated to L. A simple computation implies that
$l_1= {c}/{a} l_0 $
and
$$ \begin{align*}c l_n+ a l_{n+2}= (a+ c) l_{n+1} \quad\mbox{for all } n \geq 0.\end{align*} $$
Hence,
$$ \begin{align*} l_n= \Big(\frac{c}{a}\Big)^n l_0 \quad\mbox{for all } n \geq 1.\end{align*} $$
Assume that
$M_{\sigma }$
is positive recurrent, then by Lemma 2.10, we deduce that
$\unicode{x3bb} = L$
. Thus,
$l \in l^1$
(since a right Perron eigenvector of
$M_{\sigma }$
has constant entries) and we deduce that
$c <a$
.
Now assume that
$c \leq a$
. If
$\unicode{x3bb} = L$
, then
$l $
is a left Perron eigenvector, and hence
$M_{\sigma }$
is positive recurrent if
$c <a$
and null recurrent if
$c=a$
. Now suppose that
$\unicode{x3bb} < L$
and let
$u= (u_i)_{i \geq 0}$
be a non-zero non-negative left Perron sub-invariant eigenvector of
$M_{\sigma }$
associated to
$\unicode{x3bb} $
. Thus,
$u M < L M.$
Hence,
$$ \begin{align*} u_{n+1} \leq \frac{c}{a} u_{n} \quad\mbox{for all } n \geq 0,\end{align*} $$
and there exists a real number
$s>0$
and an integer
$k \geq 1$
such that
$u_k = ({c}/{a}) u_{k-1}-s $
. Since
$c u_{k-1}+ a u_{k+1} \leq (a+ c) u_{k} $
, we deduce that
$u_{k+1} \leq ({c}/{a}) u_{k}-s. $
Thus,
$$ \begin{align} u_{n+1} \leq \frac{c}{a} u_{n}-s \quad\mbox{for all } n \geq k. \end{align} $$
Therefore,
$$ \begin{align*} u_n \leq \bigg(\frac{c}{a}\bigg)^{n -k} u_{k}-s \quad\mbox{for all } n \geq k+1.\end{align*} $$
If
$c <a,$
we deduce that there exists a positive integer N such that
$u_n <0$
for all integers
$n \geq N$
. This is absurd, then
$ u= u_{0}l$
. Therefore,
$\unicode{x3bb} =L$
and hence
$M_{\sigma }$
is positive recurrent.
If
$c = a$
, we deduce by equation (3.9) that
$$ \begin{align*}u_{n} \leq u_{k}- (n -k) s \quad\mbox{for all } n \geq k+1.\end{align*} $$
Then
$\unicode{x3bb} = L$
and
$M_{\sigma }$
is null recurrent.
Now consider the case
$c>a$
. We will consider a probabilistic approach to show that
$\unicode{x3bb} _P<1$
and that
$\overline P_{00} ( 1/ \unicode{x3bb} _P ) = \infty $
, this implies null recurrence. Let
$(X_n)_{n\ge 0}$
be a Markov chain with transition matrix P and
$\mathbb {P}^x$
the distribution of
$(X_n)_{n\ge 0}$
, when
$X_0 = x$
for
$x \in \mathbb {Z}_+$
. Set
$p = c/(a+c)$
, which is the conditional probability that the random walk jumps to the right when it necessarily leaves its current position and this is not
$0$
, that is,
$$ \begin{align*} p = \mathbb{P}^x \big( X_{n+1} = X_n + 1 \big| X_{n+1} \neq X_n \big) \ \, \text{ for all } \, x \neq 0. \end{align*} $$
We want to estimate
$P^n_{00}$
, that is, the probability that the random walk is visiting state
$0$
at time n given that it has also started at
$0$
. For this last event to happen, necessarily, we must have a number of jumps to the right equal to the number of jumps to the left. Here we need two important observations.
-
(i) Note that
$\# \{1 \le j \le n : \ X_{n+1} \neq X_n \}$
counts the total number of jumps to the right or to the left. There exist strictly positive constants
$c,\delta \in (0,1)$
such that
$$ \begin{align*} \mathbb{P}^0 \big( \# \{1 \le j \le n : \ X_{n+1} \neq X_n \} \ge cn \big)> 1 - (\delta q)^n. \end{align*} $$
-
(ii) In
$2k$
transitions to the left or to the right, the number of transitions to the right is distributed as a binomial random variable with parameters
$2k$
and p. Thus, the probability of having an equal number of jumps to the left or to the right is (the approximation could be appropriately described using Stirling’s formula). Note that
$$ \begin{align*} \mathbb{P} \big( Bin(2k,p) = k \big) = {2k \choose k} p^k (1-p)^k \approx \frac{C}{\sqrt{k}} \big( 4p(1-p) \big)^k \end{align*} $$
$q = 4p(1-p) < 1$
.
Using observations (i) and (ii), we are able to show that
$P^n_{00}$
is of order
$O(q^n/\sqrt {n})$
. This implies that
$\unicode{x3bb} _P = q$
and
$\overline P_{00} ( 1/ \unicode{x3bb} _P ) = \overline P_{00} ( 1/ q ) = \infty $
. Therefore, P and
$M_\sigma $
are null recurrent matrices.
It is worth mentioning that
$M_\sigma $
satisfies equation (3.1) for every
$a \le c$
and b. This follows as in the last example in Remark 3.3, in the case
$a=c$
, and from computation as in the proof of Proposition 3.5. Indeed, one can prove that
$\sup _{i\in \mathbb {Z}_+} P^n_{i,j}$
is of order
$O(1/\sqrt {n})$
, which implies that
$M_\sigma $
satisfies equation (3.1). This can also be proved using the local central limit theorem for simple random walks [Reference Lawler10, Theorem 1.2.1].
Remark 3.6. It is worth mentioning that apparently small modifications on the matrix can completely change its behavior. For instance, consider the case
$b=0$
and
$a=c$
which implies that
$M_\sigma $
is null recurrent. Instead of
$\sigma (0)=0^{a}1^c$
, put
$\sigma (0)=1^c$
, then, from [Reference Kitchens9, (i) in Example 7.1.29], we have that
$M_\sigma $
is transient. For the case
$b>0$
,
$a\le c$
, and
$\sigma (0)=1^c$
, we also have transience as a consequence of our Proposition 3.5 and [Reference Kitchens9, Lemma 7.1.23].
Remark 3.7. We consider the substitution
$\sigma $
of [Reference Ferenczi6] defined on
$A= \mathbb {Z}$
by
$\sigma (n)= (n-1)nn (n+1)$
. The associated matrix is null recurrent and satisfies the condition in equation (3.1). Hence, by using Theorem 3.1, we deduce that the dynamical system
$(\Omega _\sigma , S)$
associated to
$\sigma $
has non-finite invariant measure.
Let
$\sigma := \sigma _{a_n,b_n,c_n}$
be defined by
$$ \begin{align*}\sigma(0)= 0^{a_0+b_0} 1^{c_0}\quad\mbox {and}\quad \sigma(n)= (n-1)^{a _n} n^{b_n} (n+1)^{c_{n}} \quad\mbox{for all } n \geq 1,\end{align*} $$
where
$a_n, b_n, c_n$
are non-negative integers such that
$a_n>0$
,
$c_n> 0$
for every
$n\ge 1$
, and
$L= \sup \{a_n+b_n+c_n :\, n \geq 1\}<\infty $
. The matrix
$M_{\sigma }$
is irreducible and aperiodic with bounded length L and can be represented as
$$ \begin{align*} M_{\sigma}= \begin{bmatrix} a_0+b_0 & c_0 & 0 & 0 & 0 & 0 & 0 & \cdots\\ a_1 & b_1 & c_1 & 0 & 0 & 0 & 0 & \cdots\\ 0 & a_2 & b_2 & c_2 & 0 & 0 & 0 & \cdots\\ 0 & 0 & a_3 & b_3 & c_3 & 0 & 0 & \cdots\\ 0 & 0 & 0 & a_4 & b_4 & c_4 & 0 & \cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{bmatrix}\!. \end{align*} $$
We will see in Proposition 3.8 below that
$(\Omega _\sigma , S)$
is not minimal for these substitutions. We do not discuss the transience/recurrence in this general case, but we discuss an example. Consider
$(a_n, b_n, c_n)= (2,1,1)$
for n even and
$(a_n, b_n, c_n)=(1,1,1)$
otherwise. Our first step is to compute the Perron value
$\unicode{x3bb} $
. For this, we will estimate
$(M_\sigma ^n)_{0,0}$
. Consider a matrix
$\hat M_\sigma ^n$
which has the form above but with
$(a_n, b_n, c_n)= (2,1,1)$
for every n. The Perron eigenvalue of
$\hat M_\sigma ^n$
is
$4$
, since it has constant row sums equal to 4. Now for each path of length n leaving and returning to n, we will have the number of jumps to the left equal to the number of jumps to the right. So for a total of
$2m \le n$
jumps with m jumps to the left and m jumps to right (neglecting jumps from 0 to 1 and jumps from an state to itself),
$m/2$
jumps to the left are made from an odd position and these jumps contribute with a factor of
$(\sqrt [4]{2})^{2m} = 2^{{m}/{2}}$
to the product of weights
$(\hat M_\sigma ^n)_{0,0}$
. This shows that
$$ \begin{align*} \bigg(\frac{\sqrt[4]{2}}{4}\bigg)^n (M_\sigma^n)_{0,0} \ge \frac{(\hat M_\sigma^n)_{0,0}}{4^n} , \end{align*} $$
which implies
$\unicode{x3bb} \ge 4/ \sqrt [4]{2}$
. However,
$(M_\sigma ^n)_{0,0} \le (\hat M_\sigma ^n)_{0,0}$
and
$\unicode{x3bb} \le 4$
. Thus,
$\unicode{x3bb} \in [4/ \sqrt [4]{2} , 4]$
. With this bound on
$\unicode{x3bb} $
, we can show that
$M_\sigma $
is positive recurrence. For this, we follow the computation in [Reference Kitchens9, Example 7.1.29(iii)] to obtain that
$$ \begin{align*} \lim_{n\rightarrow \infty} \sqrt[2n]{\ell_{00}(2n)} = 2^{{5}/{4}} < \unicode{x3bb}, \end{align*} $$
then apply [Reference Kitchens9, Lemma 7.1.25] to conclude.
Proposition 3.8. Let
$(\Omega _\sigma , S)$
be the shift dynamical system associated to
$ \sigma _{a_n,b_n,c_n}$
, then it is not minimal.
Proof. For all
$n \geq 2$
, we have
$$ \begin{align*}\sigma^{k-1} (k)= (\sigma^{k-2} (k-1))^{a_n} (\sigma^{k-2} (k)) ^{b_n} (\sigma^{k-2}(k+1))^{c_n}. \end{align*} $$
Hence, the infinite word
$w $
beginning with
$\sigma ^{k-1} (k)$
for all
$k \geq 2$
is well defined and belongs to
$\Omega _\sigma $
. Moreover, the letter
$0$
does not occur in w. Thus, the orbit of
$ w$
does not visit the cylinder
$[0]$
, and hence
$(\Omega _\sigma , S)$
is not minimal.
Remark 3.9. The last proposition gives examples of positive or null recurrent, aperiodic irreducible substitutions such that its shift dynamical systems are not minimal. The first example was given by Ferenczi in [Reference Ferenczi6] by considering
$\sigma (n)= (n-1)nn (n+1), \; n \in \mathbb {Z}.$
We will see in Theorem 3.33 that given a substitution
$\sigma $
on
$A= \mathbb {Z}_+,$
not necessarily with constant length such that
$\sigma $
has a periodic point
$u $
and
$M_{\sigma }$
is irreducible, aperiodic, and has a scrambling positive power, then
$(\Omega _{\sigma }, S)$
is minimal. Observe that the matrices associated to substitutions
$\sigma _{a_n, b_n, c_n}$
do not have a scrambling power, since for any positive integer k, there is no letter occurring both in the words
$\sigma _{a_n, b_n, c_n} ^k (k)$
and
$\sigma _{a_n, b_n, c_n} ^k (4 k)$
.
To end this section, we describe an interesting substitution whose matrix is transient. The construction of the matrix is based on multidimensional random walks in dimension greater or equal to 3. Thus, we set
$A = \mathbb {Z}^d$
, let
$\{e_j:1\le j \le d \}$
, and define the substitution
$$ \begin{align*} \sigma(x) = (x+e_1) (x-e_1) (x+e_2) (x-e_2) \ldots (x+e_d) (x-e_d). \end{align*} $$
We have that
$M_\sigma $
is a matrix of length
$2d$
. The stochastic matrix
$P = M_\sigma / 2d$
is transient with
$\unicode{x3bb} _P = 1$
. Indeed, from classical results in probability theory, one has that
$P^n_{00} \sim O(n^{-d/2})$
and
$\overline P_{00} (1) < \infty $
. Therefore,
$M_\sigma $
is a transient matrix with
$\unicode{x3bb} _{M\sigma } = 2d$
. Using again the local central limit theorem [Reference Lawler10, Theorem 1.2.1], we have that
$M_\sigma $
also satisfies equation (3.1).
3.3 Shift invariant measures and unique ergodicity
In this subsection, we prove the following results.
Theorem 3.10. Let
$\sigma $
be a bounded length substitution on
$A= \mathbb {Z}_+$
such that
$M_{\sigma }$
is irreducible, aperiodic, positive recurrent, then the dynamical system
$(\Omega _{\sigma }, S)$
has a shift invariant measure
$\mu $
which is finite if and only if any left Perron eigenvector l belongs to
$l^1$
.
Remark 3.11. Theorem 3.10 improves [Reference Bezugly, Jorgensen and Sanadhya1, Theorem 7.6], where it is assumed the additional hypothesis where
$\sigma $
is a bounded size left determined substitution.
Theorem 3.12. Let
$\sigma $
be a constant length substitution on
$A= \mathbb {Z}_+$
such that
$\sigma $
has a periodic point
$u $
and
$M_{\sigma }$
is irreducible and aperiodic. If there exists a positive integer n such that
$M_{\sigma }^n$
is scrambling, then there exists a unique probability shift invariant measure of
$(\Omega _{\sigma }, S)$
.
Remark 3.13. The same proof of Theorem 3.12 will show that if
$\sigma $
is a constant length substitution on
$A= \mathbb {Z}_+$
without periodic point such that
$M_{\sigma }$
is irreducible, aperiodic, and
$M_{\sigma }^n$
is scrambling positive integer n, then there exists a unique probability shift invariant measure of
$(\Omega _{\sigma }, S)$
.
Before proving Theorems 3.10 and 3.12, we need to introduce some notation and state some preliminary results.
Let
$\sigma : A \to A^*$
be a bounded length substitution, not necessarily with constant length. Let
$t \geq 2$
be an integer and
$A_t$
be the set of finite words of length t that occur in u. Now, consider a substitution
$\sigma _t$
on the alphabet
$A_t$
defined in the following way: if
$w= w_0 \ldots w_{t-1} \in A_t$
and
$\sigma (w)= y_0 \ldots y_{\vert \sigma (w_0) \vert -1}y_{\vert \sigma (w_0) \vert } \ldots y_{\vert \sigma (w)\vert -1 }$
, then
$$ \begin{align} \sigma_t(w)= (y_0 \ldots y_{t-1})(y_{1 } \ldots y_t) \ldots (y_{\vert \sigma(w_0) \vert -1} \ldots y_{\vert \sigma(w_0) \vert +t-2 }). \end{align} $$
Considering that
$|\sigma _t(w)|$
counts letters in
$A_t$
(not in A), note that
$$ \begin{align} \vert \sigma_t(w_0 \ldots w_{t-1}) \vert = \vert \sigma(w_0) \vert , \end{align} $$
and for all
$i_1 \ldots i_{t} \in A_t$
, we have
$$ \begin{align} \vert \sigma(w_0) \vert_{i_1 \ldots i_{t}} \leq \vert \sigma_t(w_0 \ldots w_{t-1}) \vert_{i_1 \ldots i_{t}} \leq \vert \sigma(w_0) \vert_{i_1 \ldots i_{t}} + t. \end{align} $$
We extend
$\sigma _t$
by concatenation to
$A_t^ {*}$
and to
$A_t^{\mathbb {Z}_+}$
. The substitution
$\sigma _t$
was defined in [Reference Queffélec19] (in the case of substitutions on finite alphabets).
For example, for
$A= \{0,1\}$
and
$\sigma (0)=0 1 ,\; \sigma (1)= 0$
. We have
$A_2= \{00, 01, 10\}$
and
$$ \begin{align*} \sigma_2(00)=(01)(10),\; \sigma_2(01)=(01)(10),\; \sigma_2(10)=(00). \end{align*} $$
If
$A= \mathbb {Z}_+$
and
$\tau (n)= 0 (n+1)$
for all
$n \in A$
, then
$A_2= \{0 n, \; n 0,\; n \geq 1\}$
and
$$ \begin{align*}\tau_2(0n)=(01)(10),\; \tau_2(n0)=(0(n+1))((n+1)0) \quad\mbox{for all } n \geq 1. \end{align*} $$
Lemma 3.14. The following results hold:
-
(1) for all integers
$n \geq 1$
and
$t \geq 2$
, we have
$(\sigma ^{n})_t= (\sigma _t)^n;$
-
(2) let
$u= u_0 u_1\ldots $
be a periodic point of
$\sigma $
, then for all integers
$t \geq 2$
, the infinite word
$(u_0 \ldots u_{t-1}).(u_1 \ldots u_{t}) \ldots (u_i \ldots u_{t+i-1}) \ldots $
is a periodic point (with the same period) of
$\sigma _t$
; -
(3) if
$M_\sigma $
is irreducible and aperiodic, then so is
$M_{\sigma _t}$
for all integers
$t \geq 2$
.
Proof. The proof is analogous to that for the case of a finite alphabet, which is given in [Reference Queffélec19, pp. 138–139].
Lemma 3.15. Let
$A = \mathbb {Z}_+$
and
$\sigma : A \to A^*$
be a bounded length substitution such that
$M_{\sigma }$
irreducible and aperiodic with Perron value
$\unicode{x3bb} $
, then for all integers
$t \geq 2$
, the matrix
$M_t= M_{\sigma _{t}}$
associated to
$\sigma _t$
also has Perron value
$\unicode{x3bb} $
. Moreover, if
$M_\sigma $
is positive recurrent (respectively null recurrent, transient), then
$ M_{\sigma _{t}}$
is also positive recurrent (respectively null recurrent, transient).
Proof. Let
$t \geq 2$
be an integer and denote by
$\unicode{x3bb} _t$
the Perron value of
$M_t$
. First observe that by item (3) in Lemma 3.14,
$M_t$
is irreducible and aperiodic. For
$i_1 \ldots i_t , \; j_1 \ldots j_t \in A_t$
, we have
$$ \begin{align*} \vert \sigma_t^{n} (i_1 \ldots i_t) \vert_{j_1 \ldots j_t} \leq |\sigma^n (i_1)|_{j_1 \ldots j_t} + t \leq |\sigma^n (i_1)|_{j_1} + t. \end{align*} $$
Hence,
$$ \begin{align} (M_{t}^{n})_{i_1\ldots i_t, j_1 \ldots j_t} \leq (M^n)_{i_1, j_1} + t \quad\mbox{for all } n \in \mathbb{N}. \end{align} $$
We deduce by equation (2.2) that
$1 \le \unicode{x3bb} _t \leq \unicode{x3bb} $
.
However, let
$k, m \in \mathbb {N}$
such that
$j_1 \ldots j_t $
is a factor of
$\sigma ^m (k)$
. Hence,
$$ \begin{align*}| \sigma^{n+m} (i_1)|_{j_1 \ldots j_t} \geq |\sigma^n (i_1)|_k.\end{align*} $$
Thus, for all
$n \in \mathbb {N}$
, we have
$ \vert \sigma _t^{n+m} (i_1 \ldots i_t) \vert _{j_1 \ldots j_t} \geq |\sigma ^n (i_1)|_k. $
Therefore,
$$ \begin{align} (M_{t}^{n+m})_{i_1\ldots i_t, j_1 \ldots j_t} \geq (M^n)_{i_1, k} \quad\mbox{for all } n \in \mathbb{N}. \end{align} $$
Thus,
$\unicode{x3bb} _t \geq \unicode{x3bb} $
and hence
$\unicode{x3bb} _t= \unicode{x3bb} $
.
Assume that
$M_\sigma $
is positive recurrent. By equation (3.14), we have
$$ \begin{align} \liminf_{n \to +\infty} \frac{(M_{t}^{n+m})_{i_1\ldots i_t, j_1 \ldots j_t}}{ \unicode{x3bb}^{n+m}} \geq \unicode{x3bb}^{-m} \lim_{n \to +\infty} \frac{(M^n)_{i_1, k}}{ \unicode{x3bb}^n}. \end{align} $$
Hence, by equation (3.15) and Lemma 2.6, we deduce that
$\lim _{n \to +\infty } ({(M_t^{n})_{ i_1 \ldots i_t ,{j_1 \ldots j_t}}}/{ \unicode{x3bb} _{t}^{n}})> 0 .$
Thus,
$M_{\sigma _{t}}$
is positive recurrent.
Now suppose that
$M_\sigma $
is null recurrent, then we have by equation (3.14) that
$$ \begin{align} \sum_{n=0}^{+\infty}\frac{(M_{t}^{n})_{i_1\ldots i_t, j_1 \ldots j_t}}{\unicode{x3bb}^n} = +\infty. \end{align} $$
Hence, by equation (3.13), we deduce that
$$ \begin{align} \lim_{n \to \infty}\frac{(M_t^{n})_{ i_1 \ldots i_t ,j_1 \ldots j_t}}{ \unicode{x3bb}^n} =0. \end{align} $$
By equations (3.16) and (3.17), we deduce that
$ M_{\sigma _{t}}$
is null recurrent.
Finally, if
$M_\sigma $
is transient, we deduce by equation (3.13) that
$$ \begin{align*} \sum_{n=0}^{+\infty}\frac{(M_{t}^{n})_{i_1\ldots i_t, j_1 \ldots j_t}}{\unicode{x3bb}^n} < +\infty.\end{align*} $$
Hence,
$ M_{\sigma _{t}}$
is transient.
Before proving Theorem 3.10, we need the following lemma.
Lemma 3.16. Let
$\sigma $
be a bounded length substitution on
$A=\mathbb {Z}_+$
such that
$M_{\sigma }$
is irreducible, aperiodic, recurrent, and has finite Perron value
$\unicode{x3bb} $
. Let
$r= (r_i)_{i \geq 0}$
be a right Perron eigenvector of
$M_{\sigma }$
. For all integers
$t \geq 2$
, let
$r^{(t)}= (r_I)_{ I \in A_t}$
be an infinite vector defined by
$$ \begin{align*}r_ I=r_{i_0} \quad\mbox{for all } I=i_0\ldots i_{t-1} \ \in A_t,\end{align*} $$
then
$r^{(t)}$
is a right Perron eigenvector of
$M_t= M_{\sigma _{t}}$
associated to
$\unicode{x3bb} $
.
Proof. Let
$I=i_0\ldots i_{t-1} \ \in A_t.$
We have
$$ \begin{align*} (M_{t} r^{(t)})_I=\sum_{J= j_0 \ldots j_{t-1} \in A_t} |\sigma_{t}(I)|_{J}\; r_{j_{0}} = \sum_{ j_0 \in A} r_{j_0} \sum_{ J^{*}=j_1 \ldots j_{t-1}, j_{0} J^{*} \in A_t} |\sigma_t(I)|_{j_{0} J^{*}}. \end{align*} $$
However, for all
$j_0\ \in A$
, we have
$$ \begin{align*} \sum_{ J^{*}=j_1 \ldots j_{t-1}, j_{0} J^{*} \in A_t} |\sigma_t(I)|_{j_{0} J^{*}}\leq |\sigma(i_0)|_{j_0}= M_{ i_0 j_0}.\end{align*} $$
Thus,
$$ \begin{align*} (M_t r^{(t)})_I \leq \sum_{j_0 \in A} M_{ i_0 j_0} r_{j_0}=\unicode{x3bb} r_{i_0}=\unicode{x3bb} (r^{(t)})_I. \end{align*} $$
Since
$M_t$
is an aperiodic, irreducible, and recurrent matrix, Lemma 2.9 implies that
$r^{(t)}$
is a right eigenvector of
$M_t$
associated to
$\unicode{x3bb} $
.
Proof of Theorem 3.10
Let
$u=u_0u_1 \ldots = \sigma (u)$
be an element of
$\Omega _{\sigma }$
. For
$j \in A$
, set
$$ \begin{align*} \mu[j] := \lim_{n \to \infty} \frac{| \sigma^n (u_0)|_{j} }{\unicode{x3bb}^n}= \lim_{n \to \infty} \frac{ M^n_{u_0, j} }{\unicode{x3bb}^n}. \end{align*} $$
The last limit exists since
$M_{\sigma }$
is positive recurrent with Perron eigenvalue
$\unicode{x3bb} $
. For integers
$t \geq 2$
and
$ I_t= i_1 \ldots i_{t} \in A_t$
, set
$$ \begin{align} \mu[i_1 \ldots i_{t}] = \lim_{n \to \infty} \frac{| \sigma^n (u_0)|_{i_1 \ldots i_{t}} }{{\unicode{x3bb}^n}}. \end{align} $$
Applying equation (3.12) for
$\sigma ^n$
in place of
$\sigma $
and the fact that
$\unicode{x3bb}>1$
, we deduce that
$$ \begin{align*} \mu[i_1 \ldots i_{t}] = \lim_{n \to \infty} \frac{| \sigma_t^n (u_0 \ldots u_{t-1})|_{i_1 \ldots i_{t}} }{\unicode{x3bb}^n}= \lim_{n \to \infty} \frac{ (M_{t}^n)_{U_t, I_t} }{\unicode{x3bb}^n}, \end{align*} $$
where
$U_t= u_0 \ldots u_{t-1}$
and
$I_t= i_1 \ldots i_{t}$
. Observe that
$\lim _{n \to \infty } \frac { (M_{t}^n)_{U_t, I_t} }{\unicode{x3bb} ^n}$
exists since
$M_t$
is positive recurrent with Perron value
$\unicode{x3bb} _t= \unicode{x3bb} .$
By the Kolmogorov consistency theorem, there exists a unique measure
$\mu $
with cylinder specification in equation (3.18) if for every integer
$t \geq 1$
and
$I= i_1 \ldots i_t \in A_t$
, we have
$$ \begin{align} \mu[I ]= \sum_{b \in A, I b \in A_{t+1}} \mu [I b] \end{align} $$
and
$$ \begin{align} \mu[I ] = \sum_{a \in A, a I } \mu [a I]. \end{align} $$
For the proof of equation (3.19), let
$l= (l_{i})_{i \geq 0}$
and
$r= (r_{i})_{i \geq 0}$
be respectively left and right Perron eigenvectors of M such that the scalar product
$l \cdot r=1$
. For all
$t \geq 2$
, let
$l^{(t)}= (l_I)_{I \in A_t} $
and
$r^{(t)}= (r_I)_{I \in A_t}$
be left and right Perron eigenvectors of
$M_{t}$
such that
$$ \begin{align*} r_{i_1 \ldots i_t}= r_{i_1} \quad\mbox{for all } i_1 \ldots i_t \in A_{t} \mbox { and } l^{(t)} \cdot r^{(t)}= 1.\end{align*} $$
We could choose
$ r_{i_1 \ldots i_t}= r_{i_1}$
because of Lemma 3.16.
For all
$I= i_1 \ldots i_t,\; t \geq 2$
, we have by equation (2.4) that
$$ \begin{align*} \mu [I]= r_{U_t} l_{I}= r_{u_0} l_{I}.\end{align*} $$
Hence, equation (3.19) is equivalent to
$$ \begin{align} l_{I}= \sum_{b \in A, I b \in A_{t+1}} l_{I b}. \end{align} $$
However, for all
$I= i_1 \ldots i_t \in A_t,$
we have by Fatou’s lemma that
$$ \begin{align*} \sum_{b \in A, I b \in A_{t+1}} \mu [I b] \leq \lim_{n \to \infty} \frac{1} {\unicode{x3bb}^n} \sum_{b \in A, I b \in A_{t+1}} |\sigma_{t+1}^n (u_0 \ldots u_{t})|_{I b} = \lim_{n \to \infty} \frac{1} {\unicode{x3bb}^{n} } |\sigma_{t}^n (u_0 \ldots u_{t-1})|_{I }. \end{align*} $$
Hence,
$$ \begin{align*}\sum_{b \in A, I b \in A_{t+1}} \mu [I b] \leq \mu [I],\end{align*} $$
that is,
$$ \begin{align} \sum_{b \in A, I b \in A_{t+1}} l_{I b} \leq l_{I}. \end{align} $$
Since
$\sum _{I \in A_t} r_{I} l_{I}= \sum _{J \in A_{t+1}} r_{J} l_{J}= 1$
and
$r(Ib)= r(I)$
for all
$I \in A_t$
and
$Ib \in A_{t+1}$
, we deduce that
$$ \begin{align*}\sum_{I \in A_t} r_{I} l_{I}= \sum_{I \in A_t} r_{I} \sum_{b \in A, I b \in A_{t+1}} l_{Ib}= 1.\end{align*} $$
Using this last equality and equation (3.22), we obtain equation (3.21) and hence we get equation (3.19).
Analogously, equation (3.20) is equivalent to
$$ \begin{align} l_{I}= \sum_{a \in A, a I \in A_{t+1}} l_{a I}. \end{align} $$
Using Fatou’s lemma, we have for all
$I \in A_t$
,
$$ \begin{align*}\sum_{a \in A, a I \in A_{t+1}} \mu [a I] \leq \lim_{n \to \infty} \frac{1} {\unicode{x3bb}^n} \sum_{a \in A, a I \in A_{t+1}} |\sigma_{t+1}^n (u_0 \ldots u_{t})|_{a I}.\end{align*} $$
Note that
$$ \begin{align*} \beta_I := \sum_{a \in A, a I \in A_{t+1}} |\sigma_{t+1}^n (u_0 \ldots u_{t})|_{a I}- | \sigma_{t}^n (u_0 \ldots u_{t-1})|_{ I} \in \{-1, 0, 1\},\end{align*} $$
indeed
$\beta _I= -1$
if the first letter of
$\sigma _{t+1}^n (u_0 \ldots u_{t})$
begins with I and the last letter of
$\sigma _{t+1}^n (u_0 \ldots u_{t})$
does not end with I. The number
$\beta _I= 1$
if the first letter of
$\sigma _{t+1}^n (u_0 \ldots u_{t})$
does not begin with I and the last letter of
$\sigma _{t+1}^n (u_0 \ldots u_{t})$
ends with I. In the complementary case, we have
$\beta _I= 0$
.
Since
$\unicode{x3bb}>1$
, we deduce that
$$ \begin{align*} \lim_{n \to \infty} \frac{1} {\unicode{x3bb}^n} \sum_{a \in A, a I \in A_{t+1}} |\sigma_{t+1}^n (u_0 \ldots u_{t})|_{a I} = \lim_{n \to \infty} \frac{1} {\unicode{x3bb}^n} |\sigma_{t}^n (u_0 \ldots u_{t-1})|_{ I}. \end{align*} $$
Hence,
$$ \begin{align*}\sum_{a \in A, Ia \in A_{t+1}} \mu [a I] \leq \mu (I),\end{align*} $$
that is,
$$ \begin{align} \sum_{a \in A, Ia \in A_{t+1}} l_{a I} \leq l_I. \end{align} $$
However, by equation (3.21), we have
$$ \begin{align*}\sum_{J \in A_{t+1} } l_J= \sum_{I \in A_{t} } \bigg(\sum_{b \in A, I b \in A_{t+1}} l_{Ib}\bigg)= \sum_{I \in A_{t} } l_I.\end{align*} $$
Thus,
$$ \begin{align*}\sum_{I \in A_{t} } \bigg(\sum_{a \in A, a I \in A_{t+1}} l_{a I}\bigg)= \sum_{I \in A_{t} } l_I.\end{align*} $$
By using equation (3.24), we obtain equation (3.20). Hence,
$\mu $
is an invariant measure for
$(\Omega _u,S)$
.
3.3.1 Constant length substitution and unique ergodicity
Let
$\sigma $
be a substitution on
$A= \mathbb {Z}_+$
with constant length
$L>0$
. By equation (2.8), the stochastic matrix
$M_\sigma / L$
is strongly ergodic if and only if there exists a positive power of
$M_{\sigma }$
which is scrambling.
As an example, the dyadic substitution
$\sigma $
defined by
$\sigma (n)= 0 (n+1) $
has a strongly ergodic matrix
$M_{\sigma }/2$
since the matrix
$M_{\sigma }$
is scrambling.
Another way to see that
$M_{\sigma }/2$
is strongly ergodic comes from the fact that for all
$i, j \in \mathbb {Z}_+$
,
$$ \begin{align} \lim_{n \to \infty} \sup_{i \in \mathbb{Z}_+} \sum_{j=0}^{+\infty} \bigg| \frac{ |\sigma^n (i)|_j}{| \sigma^n (i)|}- \frac{1}{2^{j+1}} \bigg|= 0. \end{align} $$
Indeed, for all integers
$n \in \mathbb {N}, i, j \in \mathbb {Z}_+$
, we have
$$ \begin{align*}|\sigma^n (i)|_j= |\sigma^{n-1} (i)|_{j-1}= 2^{n-j-1} \quad\mbox{for all } 0 \leq j < n\end{align*} $$
and
$$ \begin{align*}|\sigma^n (i)|_j= |\sigma (i)|_{j+1-n} \quad\mbox{for all } j \geq n.\end{align*} $$
Thus, for all
$j \geq n,$
$$ \begin{align*}|\sigma^n (i)|_j= 1 \quad\mbox{if } j = i+n \mbox { and } 0 \mbox { otherwise}.\end{align*} $$
Hence,
$$ \begin{align*} \sum_{j=0}^{+\infty} \bigg|\frac{ |\sigma^n (i)|_j}{| \sigma^n (i)|}- \frac{1}{2^{j+1}} \bigg|= \sum_{j=n }^{+\infty} \frac{1}{2^{j+1}} + \bigg(\frac{1 } {2^n} - \frac{1 } {2^{i+n}}\bigg) \quad\mbox{for all } i \ge 0, \end{align*} $$
which implies that
$$ \begin{align*} \sup_{i \in \mathbb{Z}_+} \sum_{j=0}^{+\infty} \bigg|\frac{ |\sigma^n (i)|_j}{| \sigma^n (i)|}- \frac{1}{2^{j+1}}\bigg|= \frac{1 } {2^{n-1}}, \end{align*} $$
and we obtain equation (3.25).
Another example are the substitutions
$\sigma _{a, b, c}, \; a, b, c \in \mathbb {N}$
and
$a>c$
. We have seen in the proposition that for all positive integers
$a, b, c$
with
$a>c$
, the matrix
$M_{\sigma _{a, b, c}}$
is positive recurrent. Furthermore, the stochastic matrix
${M_{\sigma _{a, b, c}} }/( {a+b +c})$
is not strongly ergodic since
$M_{\sigma _{a, b, c}}$
does not have a scrambling power (see Remark 3.9).
Remark 3.17. Let
$\sigma $
be a substitution on
$A= \mathbb {Z}_+$
with constant length
$L>0$
and a periodic point u such that the stochastic matrix
$M_\sigma / L$
is strongly ergodic. Then
$M_{\sigma }$
is positive recurrent and, by Theorem 3.10,
$\Omega _\sigma $
has a finite invariant measure.
Lemma 3.18. Assume that
$\sigma $
is a constant length substitution on
$A= \mathbb {Z}_+$
and
$M_{\sigma }$
is irreducible and aperiodic. If
$M_\sigma $
is strongly ergodic, then for all integers
$t \geq 2,\; M_{\sigma _t}$
is also strongly ergodic.
Proof. Let
$L>0$
be the length of
$\sigma $
. Fix and integer
$t \geq 2$
and
$i_1\ldots i_t$
,
$k_1 \ldots k_t \in A_t$
. Since
$M_\sigma $
is strongly ergodic, then equation (2.5) implies that there exists an integer
$n>0$
and
$j_1 \in \mathbb {N}$
such that
$$ \begin{align*} j_1 \quad\mbox {occurs in } \sigma^n(i_1) \mbox { and } \sigma^n(k_1). \end{align*} $$
Let
$m>0$
be an integer such that
$$ \begin{align*}m = \bigg[\frac{\ln (2t)} {\ln L}\bigg]+1,\end{align*} $$
then
$$ \begin{align*} \sigma^m(j_1) = a_1 \ldots a_s \quad\mbox{where } s \geq 2t.\end{align*} $$
Hence,
$a_1 \ldots a_{2t} \mbox { occurs in } \sigma ^{n+ m}(i_1) \mbox { and } \sigma ^{n+m}(k_1 ) $
. Thus,
$$ \begin{align*}a_1 \ldots a_{t} \quad\mbox{occurs in } \sigma_t^{n+ m}(i_1 \ldots i_t) \mbox { and } \sigma_t^{n+m}(k_1 \ldots k_t ), \end{align*} $$
and we are done again by equation (2.5).
Proof of Theorem 3.12
Assume without loss of generality that
$\sigma $
has a fixed point
$u= \sigma (u)= u_0u_1\ldots = \lim _{n \to \infty } \sigma (u_0)$
and let
$L>0$
be the length of
$\sigma $
. Recall that for all
$i, j \in \mathbb {Z}_+$
and
$n \geq 0$
,
$$ \begin{align*}\frac{| \sigma^{n} (i) |_{j}}{ | \sigma^{n} (i)|}= \frac{M^{n}_{ij}}{ L^n}.\end{align*} $$
Since
$M_{\sigma }$
is irreducible, aperiodic, and strongly ergodic, we have that
$\unicode{x3bb} = L$
and
$$ \begin{align*} \lim_{n \to +\infty} \frac{\vert \sigma^{n} (i) \vert_{j}}{ \vert \sigma^{n} (i)\vert}= v_j> 0\end{align*} $$
independently of i. Moreover, strong ergodicity implies that there exist
$c{\kern-1pt}>{\kern-1pt}0$
and
$0 {\kern-1pt}<{\kern-1pt} \beta {\kern-1pt}<{\kern-1pt}1$
such that
$$ \begin{align*} \sup_{i \geq 0} \bigg| \frac{\vert \sigma^{n} (i) \vert_{j}}{ \vert \sigma^{n} (i) \vert} - v_j \bigg| \leq c \beta^n \quad\mbox{for all } n \geq 0. \end{align*} $$
To compute
$ \lim _{n \to +\infty } ({\vert \sigma ^{n} (i) \vert _{w}}/{ \vert \sigma ^{n} (i)|})$
, where w is a word of length
$t \geq 2$
, we will consider a substitution
$\sigma _t$
on the alphabet
$ A_t$
. From Lemmas 3.14 and 3.18, we deduce that
$M_{\sigma _t}$
is irreducible, aperiodic, and strongly ergodic. Thus, if
$w= w_0 \ldots w_{t-1}$
and
$ B= b_0 \ldots b_{t-1} \in A_t$
, then there exists
$d_B>0$
such that
$ \lim _{n \to +\infty } ({\vert \sigma _{t}^{n} (w) \vert _{B}}/{ \vert \sigma _{t}^{n} (w)|}) = d_{B}$
independently of w. Now, since
$$ \begin{align*}\vert \sigma_{t}^ n (w) \vert= \vert \sigma^ n (w_0) \vert= L^n \quad\mbox {and}\quad \vert \sigma^{n} (w_0) \vert_{B} \leq \vert \sigma_{t}^{n} (w) \vert_{B} \leq \vert \sigma^{n} (w_0) \vert_{B} + t,\end{align*} $$
we obtain
$$ \begin{align} \lim_{n \to +\infty} \frac{\vert \sigma^{n} (w_0) \vert_{z}}{ \vert \sigma^{n} (w_0)|} = d_{B}. \end{align} $$
Moreover, there exists
$c_t>0$
and
$0 < \beta _t<1$
such that
$$ \begin{align} \sup_{w_0 \ge 0} \bigg| \frac{\vert \sigma^{n} (w_0) \vert_{B}}{ \vert \sigma^{n} (w_0)|} - d_{B} \bigg| \leq c_t \beta_t^n \quad\mbox{for all } n \geq 0. \end{align} $$
To finish the proof, we have to show the following claim.
Claim. Let
$t \geq 2$
and
$B= b_1 \ldots b_t \in F_u$
. Then
$\lim _{N \to \infty } ({1}/{N})|u_k \ldots u_{k+N-1}|_B = d_B$
uniformly on k.
The proof is the same as that for a finite alphabet and
$\sigma $
primitive given in [Reference Queffélec19, Theorem 4.6, pp. 141–142]. Indeed, let
$V_k = u_k \ldots u_{k+N-1} \in F_u,\; k \in \mathbb {Z}_+$
,
$N \in \mathbb {N}$
. As cited in the proof of Theorem 3.1, the word
$V_k$
can be written as
$$ \begin{align} V_k = v_0\sigma (v_1) \ldots \sigma^{n-1}(v_{n-1})\sigma^{n}(v_{n})\sigma^{n-1}(w_{n-1}) \ldots \sigma (w_1)w_0, \end{align} $$
where
$n \geq 0$
is an integer and
$v_i, \; i \in \{0,\ldots , n\}, \; w_j,\; j \in \{ 0,\ldots , n-1\}$
are elements of
$F_u$
possibly empty words of lengths
$\leq L $
and
$v_n$
is not empty.
Since
$L\ge 2$
, there exist
$C>0$
and
$1 < \tau < L$
such that
$C \tau ^n \ge c_t (2 n -1) ( (\max (\beta _t L,1))^n$
for every
$n\ge 1$
. Now for
$V_k= u_k \ldots u_{k+N-1},\; k \in \mathbb {Z}_+$
, for
$N \in \mathbb {N}$
, and
$B \in F_u$
such that
$|B| <N$
, we use equations (3.28) and (3.27) to obtain that
$$ \begin{align} ||V_k|_{B} - d_{B} N | & \leq \sum_{j=0}^n \big| |\sigma^{j} (v_j)|_{B} - d_{B} |\sigma^{j} (v_j)| \big| + \sum_{j=0}^{n-1} \big| |\sigma^{j} (w_j)|_{B} - d_{B} |\sigma^{j} (w_j)| \big| \nonumber \\ & \le \sum_{j=0}^n c_t (\beta_t L)^j + \sum_{j=0}^{n-1} c_t (\beta_t L)^j \le c_t (2 n -1) ( (\max(\beta_t L,1))^n \le C \tau^{n}. \end{align} $$
Since
$N \geq | \sigma ^{n} (v_n)|= L^n$
, we obtain that
$$ \begin{align} \sup_{k\ge 0}\bigg| \frac{|V_k|_{B}} N - d_{B} \bigg| \leq C \gamma^{n} \end{align} $$
for some
$\gamma < 1$
and we obtain the claim.
3.3.2 Strong ergodicity for non-constant bounded length substitution
Definition 3.19. Let
$M= (M_{ij})_{i,j \geq 0}$
be a non-negative matrix such that M is irreducible, aperiodic, and positive recurrent with finite Perron value
$\unicode{x3bb}>0$
. Let
$P= (P_{ij})_{i, j \geq 0}$
be the stochastic matrix defined by
$$ \begin{align*}P_{ij}= \frac{M_{ij} r_{j}} {\unicode{x3bb} r_i} \quad\mbox{for all } i, j \geq 0,\end{align*} $$
where
$r=(r_{k})_{k \geq 0}$
is a right Perron eigenvector of M. We say that M is strongly ergodic if
$P= (P_{ij})_{i, j \geq 0}$
is too.
Remark 3.20. (1) It is easy to see that the stochastic matrix P defined in the last definition satisfies
$P_{ij}= {M_{ji}l_j}/{\unicode{x3bb} l_i}$
for all
$i, j \geq 0$
, where
$l=(l_{k})_{k \geq 0}$
is a left Perron eigenvector of M. Furthermore, we have that
$P^n_{i,j} = {M^n_{ij}r_j}/{\unicode{x3bb} ^n r_i}$
for all integers
$n \geq 1$
.
(2) Definition 3.19 appeared in [Reference Seneta20] in the case where M is a finite irreducible, aperiodic matrix. It is also an extension of the definition in the case where M has constant row sums L. This comes from the fact that
$r_i= 1 $
for all
$i \geq 0$
and
$\unicode{x3bb} =L$
.
Remark 3.21. Let
$M= (M_{ij})_{i,j \geq 0}$
be a non-negative, irreducible, aperiodic, and positive recurrent matrix with finite Perron value
$\unicode{x3bb}>0$
. Then M is strongly ergodic if and only if there exists positive integer n and a vector of probability
$(\pi _j)_{j \geq 0} $
such that
$$ \begin{align} \lim_{n \to \infty} \sup_{i \geq 0} \sum_{j =0}^{+\infty} \bigg| \frac{M^{n}_{ij}r_j } {\unicode{x3bb}^{n} r_i } - \pi_{j} \bigg| = 0. \end{align} $$
Furthermore,
$\pi _j = l_j r_j$
, where l and r are respectively Perron left and right eigenvectors such that
$l\cdot r = 1$
. By using Remark 2.13, we deduce that M is strongly ergodic if and only if there exists a positive integer n and a positive constant a such that for all integers
$i \neq k$
, we have
$$ \begin{align} \sum_{j =0}^{+\infty} \min \bigg( \frac{M^{n}_{ij}r_j } {\unicode{x3bb}^{n} r_i }, \frac{M^{n}_{kj}r_j } {\unicode{x3bb}^{n} r_k } \bigg) \geq a. \end{align} $$
Remark 3.22. Let
$M= (M_{ij})_{i,j \geq 0}$
be a non-negative, irreducible, aperiodic, and positive recurrent matrix with finite Perron value
$\unicode{x3bb}>0$
. Assume that M has a right Perron eigenvector
$r= (r_i)_{i \geq 0} \in l^{\infty }$
which satisfies
$\inf \{r_i : i\ge 0\}>0$
, then by Remark 3.21, we deduce that M is strongly ergodic if and only if there exists a positive integer n such that
$M^n$
is scrambling.
Theorem 3.23. Let
$\sigma $
be a non-constant bounded length substitution on
$A= \mathbb {Z}_+$
with a periodic point u and such that
$M= M_{\sigma }$
is irreducible, aperiodic, positive recurrent and has a finite Perron value. Assume that
$M_\sigma $
has a right Perron eigenvector
$r= (r_i)_{i \geq 0} \in l^{\infty }$
and there exists a positive integer such that
$M_\sigma ^{n}$
is scrambling. Then the dynamical system
$(\Omega _{\sigma }, S)$
has a unique invariant probability measure.
For the proof, we need the following results.
Lemma 3.24. Let
$M= (M_{ij})_{i, j \in \mathbb {Z}_+}$
be an irreducible, aperiodic, positive recurrent non-negative matrix such that
$\| M\|= \sup \{\sum _{j=0}^{+\infty } M_{ij},\; i \in \mathbb {Z}_+\} < \infty $
and
$\inf \{ M_{ij} : \; i, j \in \mathbb {Z}_+ , \ M_{ij}>0 \} >0.$
Assume that there exists a positive integer such that
$M^{n}$
is scrambling. Then M has a right Perron eigenvector
$r= (r_i)_{i \geq 0}$
which satisfies
$\inf \{r_i : i\ge 0\}>0$
.
Proof. Assume without loss of generality that M is scrambling. Let
$r= (r_i)_{i \geq 0}$
be a non-negative right Perron eigenvector of M. Since M is irreducible,
$r_i> 0$
for every
$i\ge 0$
. Moreover,
$\|M\| < \infty $
and
$\inf \{ M_{ij} : \; i, j \in \mathbb {Z}_+ , \ M_{ij}>0 \} >0$
imply that there exists
$L>0$
such that
$M_{0k}= 0$
for all
$k>L.$
Since M is scrambling, then for all
$i \in \mathbb {Z}_+$
, there exists
$k_i \in \{0,\ldots , L\}$
such that
$M_{i,k_i}>0.$
Since
$\sum _{k=0}^{+\infty } M_{ik} r_k = \unicode{x3bb} r_i,$
we deduce that
$$ \begin{align*} r_{i} \ge \frac{M_{i, k_i} r_{k_i}}{\unicode{x3bb}} \ge \frac{C \inf\{r_k: \; 0\le k\le L\}}{\unicode{x3bb}}> 0 \quad\mbox{for all } i \in \mathbb{Z}_+, \end{align*} $$
where
$C = \inf \{ M_{ij} : \; i, j \in \mathbb {Z}_+ , \ M_{ij}>0 \}$
.
Lemma 3.25. Let
$\sigma $
be a non-constant bounded length substitution on
$A= \mathbb {Z}_+$
with a periodic point u such that
$M= M_{\sigma }$
is irreducible, aperiodic, and has a finite Perron value. Assume that
$M_\sigma $
is strongly ergodic and has a right Perron eigenvector
$r= (r_i)_{i \geq 0} \in l^{\infty }$
which satisfies
$\inf \{r_i : i\ge 0\}>0$
. Then for all integers
$t \geq 2,\; M_{\sigma _t}$
is strongly ergodic and has a right Perron eigenvector
$r^{(t)}= (r_I)_{I \in A_l} \in l^{\infty }$
such that
$\inf \{ r_I: I \in A_t\}>0$
.
Proof. Using the same proof given in Lemma 3.18, we can show that if
$M_\sigma $
is strongly ergodic, then
$M_{\sigma _t}$
is also strongly ergodic. Moreover, since
$r= (r_i)_{i \geq 0} \in l^{\infty }$
and
$\inf \{r_i : i\ge 0\}>0$
, Lemma 3.16 implies that
$r^{(t)}= (r_I)_{I \in A_t} \in l^{\infty }$
and
$\inf \{ r_I: I \in A_t\}>0$
.
Lemma 3.26. Let
$M= (M_{ij})_{i,j \geq 0}$
be a non-negative strongly ergodic matrix with finite Perron value
$\unicode{x3bb}>0$
. Assume that M has a right Perron eigenvector
$r= (r_i)_{i \geq 0} \in l^{\infty }$
which satisfies
$\inf \{r_i : i\ge 0\}>0$
. Then
$$ \begin{align*}\lim _{n \to +\infty} \sup_{i \geq 0} \sum_{j=0}^{\infty} \bigg\vert \frac{M^n_{ij} } { \sum_{k=0}^{+\infty} M^n_{ik}} - z_j \bigg\vert= 0, \end{align*} $$
where
$ z_j = {l_j}/{\sum _{k=0}^{+\infty } l_k}$
and
$l= (l_i)_{i \geq 0} \in l^1$
is a left Perron eigenvector of M.
Proof. Since M is strongly ergodic, we deduce by equation (3.31) that for all
$i, j \in \mathbb {Z}_+$
,
$$ \begin{align*} \lim_{n \to \infty} \frac{M^{n}_{ij}}{\unicode{x3bb}^{n}} = \pi_{j} \frac{r_i } { r_j} \end{align*} $$
and
$$ \begin{align*}\lim_{n \to \infty} \sum_{k =0}^{+\infty} \frac{M^{n}_{ik} } {\unicode{x3bb}^{n} } = \sum_{k=0}^{+\infty} \pi_{k} \frac{r_i } { r_k},\end{align*} $$
where the last two limits are finite and uniform on i. Hence,
$$ \begin{align*}\lim _{n \to +\infty} \sup_{i \geq 0} \sum_{j=0}^{\infty} \bigg\vert \frac{M^n_{ij} } { \sum_{k=0}^{+\infty} M^n_{ik}} - z_j \bigg\vert= 0, \end{align*} $$
where
$$ \begin{align*} z_j= \frac{\pi_{j} / r_j} {\sum_{k=0}^{+\infty} \pi_{k} / r_k}= \frac{l_j}{\sum_{k=0}^{+\infty} l_k} \quad\mbox{for all } j \geq 0.\\[-34pt] \end{align*} $$
Corollary 3.27. Let
$M= (M_{ij})_{i,j \geq 0}$
be a non-negative strongly ergodic matrix with finite Perron value
$\unicode{x3bb}>0$
. Assume that M has a right Perron eigenvector
$r= (r_i)_{i \geq 0} \in l^{\infty }$
which satisfies
$\inf \{r_i : i\ge 0\}>0$
. Then
$$ \begin{align*} \lim_{n \rightarrow \infty} \frac{\sum_{j=1}^{+\infty} M^n_{ij}}{\unicode{x3bb}^n} = c r_i \end{align*} $$
for some
$c>0$
.
Proof of Theorem 3.23
Without loss of generality, assume that
$\sigma $
has a fixed point
$u= \sigma (u)= u_0u_1\ldots .$
For all
$i, j \in \mathbb {Z}_+$
and
$n \in \mathbb {N}$
, we have
$$ \begin{align*}\frac{\vert \sigma^{n} (i) \vert_{j}}{ \vert \sigma^{n} (i)|}= \frac{M^n_{ij}}{ \sum_{k=0}^{+\infty} M^n_{ik}}.\end{align*} $$
Hence, by Lemma 3.26, we have
$$ \begin{align*}\lim _{n \to +\infty} \sup_{i \geq 0} \sum_{j=0}^{\infty} \bigg\vert \frac{\vert \sigma^{n} (i) \vert_{j}}{ \vert \sigma^{n} (i) \vert} - \frac{l_j}{\sum_{k=0}^{+\infty} l_k} \bigg\vert= 0. \end{align*} $$
Let
$j \in \mathbb {Z}_+$
and put
$$ \begin{align*}\mu[j] = \lim_{n \to \infty} \frac{| \sigma^n (u_0)|_{j} }{| \sigma^n (u_0)|} = \frac{l_j}{\sum_{k=0}^{+\infty} l_k}.\end{align*} $$
Let
$t \geq 2$
be an integer and
$ I_t= i_1 \ldots i_{t} \in A_t$
, and put
$$ \begin{align*} \mu[i_1 \ldots i_{t}] = \lim_{n \to \infty} \frac{| \sigma^n (u_0)|_{i_0 \ldots i_{t-1}} }{| \sigma^n (u_0)|}. \end{align*} $$
By equation (3.12) and the fact that
$\unicode{x3bb}>1$
, we deduce that
$$ \begin{align*}\mu[i_1 \ldots i_{t}] = \lim_{n \to \infty} \frac{| \sigma_t^n (u_0 \ldots u_{t-1})|_{i_1 \ldots i_{t}} }{|\sigma_t^n (u_0 \ldots u_{t-1})|}= \lim_{n \to \infty} \frac{ (M_{t}^n)_{U_t, I_t} }{\sum_{J \in A_t} M^n_{U_t,J}},\end{align*} $$
where
$U_t= u_0 \ldots u_{t-1}, I_t=i_1 \ldots i_{t} $
. By Lemmas 3.25 and 3.26, we have
$$ \begin{align*} \mu[i_1 \ldots i_{t}]=\frac{l^{(t)}_{I_t}}{\sum_{J \in A_t} l^{(t)}_J}, \end{align*} $$
where
$(l^{(t)}_{I})_{I \in A_t}$
is a left Perron eigenvector of
$M_{\sigma _t}$
associated to its Perron value
$\unicode{x3bb} $
.
The measure
$\mu $
is the same as that given in the proof of Theorem 3.10. Hence,
$\mu $
is a shift invariant measure. The uniqueness is a direct consequence of the following claim.
Claim. Let E be a measurable subset of
$\Omega _\sigma $
such that
$\mu (E)>0$
. For all
$ x \in E$
, we have
$$ \begin{align} \lim_{N \to \infty} \frac{1}{N} \; \mathrm{card} \{ 0 \leq k \leq N-1, S^k (x) \in E\} = \mu(E). \end{align} $$
It remains to prove the claim. First, assume that
$E=[i_0]$
. Suppose
$x= u= \sigma (u)= u_0u_1 \ldots $
and
$N= |\sigma ^n (u_0)|$
. Then
$$ \begin{align*}\lim_{n \to \infty} \frac{1}{N} \; \mathrm{card} \{ 0 \leq k \leq N-1, S^k (x) \in E\} = \lim_{n \to \infty} \frac{| \sigma^{n} (u_0 )|_{ i_0 }}{| \sigma^{n} (u_0)|} = \mu (E). \end{align*} $$
Now, let
$x \in \Omega _\sigma $
and
$N \in \mathbb {N} $
. Let
$V = u_k \ldots u_{k+N-1} \in F_u,\; k \in \mathbb {Z}_+$
be a prefix of x. As seen before, the word V can be written as a concatenation of at most
$2n+1$
words
$v_0, \sigma (v_1), \ldots ,\sigma ^{n}(v_{n}),\sigma ^{n-1}(w_{n-1}) \ldots w_0$
that is
$$ \begin{align*} V= v_0\sigma (v_1) \ldots \sigma^{n-1}(v_{n-1})\sigma^{n}(v_{n})\sigma^{n-1}(w_{n-1}) \ldots \sigma (w_1)w_0, \end{align*} $$
where
$n \geq 1$
is an integer and
$v_i, \; i \in \{0,\ldots , n\}, \; w_j,\; j \in \{ 0,\ldots , n-1\}$
are elements of
$F_u$
possibly empty words of lengths
$\leq K= \max \{ |\sigma (b)|,\; b \in A\} $
and
$v_n$
is not empty. Thus,
$$ \begin{align} &\frac{1}{N} \; \mathrm{card} \{ 0 \leq k \leq N-1, S^k (x) \in E\} = \frac{|V|_{i_0 }}{|V|} \nonumber \\ &\quad = \frac{| \sigma^n (v_n) |_{i_0 }+ \sum_{i=0}^{n-1} (| \sigma^i (v_i) |_{i_0 } + | \sigma^i (w_i) |_{i_0 })} {| \sigma^n (v_n) |+ \sum_{i=0}^{n-1} (| \sigma^i (v_i) | + | \sigma^i (w_i) |)}. \end{align} $$
Since
$M_\sigma $
is strongly ergodic, we have
$$ \begin{align*}\lim_{k \to \infty} \sup \bigg\{ \frac{| \sigma^k (j) |_{i_0}}{ | \sigma^k (j) |},\; j \in A \bigg\}= \lim_{k \to \infty} \sup \bigg\{ \frac{M^k_{j, i_0}}{ \sum_{i=0}^{+\infty}M^k_{j, i} } ,\; j \in A \bigg\} = \mu[ i_0 ].\end{align*} $$
We deduce that
$$ \begin{align} \lim_{k \to \infty} \sup \bigg\{ \frac{| \sigma^k (v) |_{i_0}}{ | \sigma^k (v) |},\;v \in F_u,\; |v| \leq K \bigg\}= \mu[ i_0 ]. \end{align} $$
Using equations (3.34), (3.35), and the Stolz–Cesaro theorem, we obtain that
$$ \begin{align*}\lim _{N \to \infty} \frac{1}{N} \; \mathrm{card} \{ 0 \leq k \leq N-1, S^k (x) \in E\} =\mu[ i_0 ]= \mu (E).\end{align*} $$
Hence, we obtain the claim for
$E= [i_0]$
.
Now, suppose that
$I=i_0 \ldots i_{t-1} $
and
$E=[I]$
. Proceeding as in the case
$E= [i_0]$
, we have
$$ \begin{align*} \frac{\mathrm{card} \{ 0 \leq k \leq N-1, S^k (x) \in E\}}{N} = \frac{| \sigma^n (v_n) |_{I }+ \sum_{i=0}^{n-1} (| \sigma^i (v_i) |_{I } + | \sigma^i (w_i) |_{I }) + C_n} {| \sigma^n (v_n) |+ \sum_{i=0}^{n-1} (| \sigma^i (v_i) | + | \sigma^i (w_i) |)}, \end{align*} $$
where
$C_n$
is the cardinality of times such that
$i_0 \ldots i_{t-1} $
occurs in the concatenation of at least two consecutive words among the
$2n+1$
words forming V. Observe that
$0 \leq C_n \leq 2n$
.
Now for all
$j \in A$
, we have
$$ \begin{align*} \lim_{k \to \infty} \frac{|\sigma^k (j)|_{i_0 \ldots i_{t-1}}} { | \sigma^k (j) |}= \lim_{k \to \infty} \frac{|\sigma_t ^k (j z_1 \ldots z_{t-1})|_{i_0 \ldots i_{t-1}}} { | \sigma_t^k (j z_1 \ldots z_{t-1}) |}= \mu[ i_0 \ldots i_{t-1}], \end{align*} $$
where
$j z_1 \ldots z_{t-1} \in F_u. $
We deduce by using the fact that
$\sigma _t$
is strongly ergodic that
$$ \begin{align*} \lim_{k \to \infty} \sup \bigg\{ \frac{|\sigma^k (j)|_{i_0 \ldots i_{t-1}}} { | \sigma^k (j) |},\; j \in \mathbb{Z}_+ \bigg\} = \mu[ i_0 \ldots i_{t-1}].\end{align*} $$
Thus,
$$ \begin{align} \lim_{k \to \infty} \sup \bigg\{ \frac{| \sigma^k (v) |_{i_0 \ldots i_{t-1}}}{ | \sigma^k (v) |}, \;v \in F_u,\; |v| \leq K \bigg\}= \mu[ i_0 \ldots i_{t-1}]. \end{align} $$
Using equation (3.36) and the Stolz–Cesaro theorem, we deduce that
$$ \begin{align*}\lim_{n \to \infty} \frac{| \sigma^n (v_n) |_{I}+ \sum_{i=0}^{n-1} (| \sigma^i (v_i) |_{I} + | \sigma^i (w_i) |_{I})} {| \sigma^n (v_n) |+ \sum_{i=0}^{n-1} (| \sigma^i (v_i) | + | \sigma^i (w_i) |)}= \mu[ i_0 \ldots i_{l-1}].\end{align*} $$
Since
$0 \leq C_n \leq 2n,\; \lim _{n \to \infty } \frac {|\sigma ^{n} (v_n)|_0}{\unicode{x3bb} ^n}>0$
and
$\unicode{x3bb}>1$
, we deduce that
$$ \begin{align*}\lim_{N \to \infty} \frac{1}{N} \; \mathrm{card} \{ 0 \leq k \leq N-1, S^k (x) \in E\} =\mu[ i_0 \ldots i_{t-1}],\end{align*} $$
and this finishes the proof.
Proposition 3.28. Let
$\sigma $
be a bounded length substitution on
$A= \mathbb {Z}_+$
such that
$\sigma $
has a periodic point
$u $
and
$M_{\sigma }$
is irreducible and aperiodic. Assume that there exists an integer n such that
$M_{\sigma }^n$
is scrambling. Then
$(\Omega _{\sigma }, S)$
is minimal.
Proof. Assume without loss of generality that
$u=u_0 u_1 \ldots $
is a fixed point and
$M_{\sigma }$
is scrambling. Let
$V= u_{k} \ldots u_{k+N}, \; k, N \in \mathbb {Z}_+$
be a factor of u. Let us prove that V occurs infinitely on u with bounded gaps. Indeed, let
$n_0 \in \mathbb {N}$
such that V occurs in
$\sigma ^k(u_0)$
for all
$k \geq n_0$
and put
$$ \begin{align*} \sigma (u_0)= t_0 \ldots t_s,\quad s \in \mathbb{N}.\end{align*} $$
Let
$m_0 \in \mathbb {N}$
such that
$u_0$
occurs on
$\sigma ^k (t_i)$
for all
$k \geq m_0$
and
$i=0,\ldots , s.$
Hence, V occurs in
$\sigma ^k (t_i)$
for all
$k \geq n_0+ m_0$
and
$i=0,\ldots , s.$
However, since
$M_\sigma $
is scrambling, then for all
$i \in \mathbb {N}$
, there exists
$j_i \in \{0,\ldots , s\}$
such that
$t_{j_{i}}$
occurs in
$\sigma (u_i).$
Hence, V occurs in
$\sigma ^k (u_i)$
for all
$k \geq n_0+ m_0$
and
$i \in \mathbb {Z}_+.$
Since
$u= \sigma ^k (u)= \sigma ^k (u_0) \sigma ^k (u_1) \ldots ,$
we are done.
Examples.
-
(1) Let
$\sigma $
(infinite Fibonacci) be given by We can prove by induction that
$$ \begin{align*}\sigma (2n)= 0 (2n+1),\ \sigma (2n+1)= 2n+2 \quad\mbox{for all } n \geq 0.\end{align*} $$
where
$$ \begin{align*}|\sigma^n(0)|= F_n \quad\mbox {and}\quad |\sigma^n(0)|_0= F_{n-1} \quad\mbox{for all } n \geq 1,\end{align*} $$
$(F_n)_{n \geq 0}$
is the Fibonacci sequence defined by The substitution matrix is given by
$$ \begin{align*}F_0=1, F_1=2, \; F_n= F_{n-1}+ F_{n-2} \quad \mbox{for all } n \geq 2.\end{align*} $$
It is irreducible, aperiodic, and its Perron eigenvector is the Golden number
$$ \begin{align*} M_{\sigma}= \begin{pmatrix} 1&1&0&0&0&0&\ldots\\ 0&0&1&0&0&0&\ldots\\ 1&0&0&1&0&0&\ldots\\ 0&0&0&0&1&0&\ldots\\ 1&0&0&0&0&1&\ldots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix}. \end{align*} $$
$\beta = ({1+ \sqrt {5}})/{2}= \lim _{n \to \infty } ({F_{n+1}})/{F_n}.$
A right Perron and a left Perron eigenvector are respectively Hence,
$$ \begin{align*}l = (1, 1/\beta,\ldots, 1/ \beta^n,\ldots) \textrm{ and } r= (1, 1/\beta, 1, 1/ \beta,1, 1/ \beta, \ldots).\end{align*} $$
$M_{\sigma }$
is positive recurrent. Furthermore,
$M^2_\sigma $
is scrambling,
$r \in l^{\infty }$
, and
$\sigma $
has a fixed point
$u= \lim _{n \to \infty } \sigma ^n (0)$
, thus Theorem 3.23 implies that the dynamical system
$(\Omega _\sigma , S)$
has a unique probability invariant measure.
-
(2) Let
$\tau $
be given by where
$$ \begin{align*}\tau(n)= 0^{a_{n}} (n+1) \quad\mbox{for all } n \geq 0,\end{align*} $$
$0\hspace{-0.5pt} \leq\hspace{-0.5pt} a_i\hspace{-0.5pt} \leq\hspace{-0.5pt} C$
for all
$i\hspace{-0.5pt} \geq\hspace{-0.5pt} 0$
for some fixed
$C\hspace{-0.5pt}>\hspace{-0.5pt}0$
and
$a_0\hspace{-0.5pt}>\hspace{-0.5pt}0$
, and
$\lim sup \; a_n\hspace{-0.5pt} \geq\hspace{-0.5pt} 1$
.
The substitution matrix is given by
The Perron eigenvalue of
$$ \begin{align*} M_{\tau}= \begin{pmatrix} a_0& 1& 0 & 0 & 0 & 0 &\ldots\\ a_1& 0& 1 & 0 & 0 &0&\ldots\\ a_2& 0& 0 & 1 & 0 &0&\ldots\\ a_3& 0& 0 & 0 & 1 &0 &\ldots\\ a_4& 0& 0 & 0 & 0 &1 &\ldots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix}. \end{align*} $$
$M_{\tau }$
is the unique real number
$\unicode{x3bb}>1$
satisfying A right Perron and a left Perron eigenvector are respectively
$$ \begin{align*}1= \sum_{i=0}^{\infty} a_i \unicode{x3bb}^{-i-1}.\end{align*} $$
where
$$ \begin{align*}l = (1, 1/\unicode{x3bb},\ldots, 1/ \unicode{x3bb}^n,\ldots) \quad\textrm{and}\quad r= (1, \alpha_1, \ldots, \alpha_n, \ldots),\end{align*} $$
Observe that
$$ \begin{align*}\alpha_n= \unicode{x3bb}^n- \sum_{i=0}^{n-1} a_i \unicode{x3bb}^{n-i-1} \quad\mbox{for all } n \geq 1.\end{align*} $$
Since
$$ \begin{align*}\alpha_n= \sum_{i=1}^{+\infty} a_{n+i-1} \unicode{x3bb}^{-i} \quad\mbox{for all } n \geq 1.\end{align*} $$
$l \cdot r $
is finite,
$M_\sigma $
is positive recurrent.
If there exists
$k\ge 1$
such that
$a_{kn} \geq 1$
for all
$n \in \mathbb {Z}_+$
, then
$ \inf \{\alpha _n,\; n \in \mathbb {Z}_+\}>0.$
. Moreover,
$M^k_\tau $
is scrambling. Furthermore,
$\tau $
has a fixed point
$u= \lim _{n \to \infty } \tau ^n (0)$
, thus Theorem 3.23 implies that the dynamical system
$(\Omega _u, S)$
has a unique probability invariant measure.
Question 3.4. It will be interesting to study dynamical properties of
$(\Omega _u, S)$
associated to
$\tau $
in the case where
$\inf \{\alpha _n,\; n \in \mathbb {Z}_+\} =0.$
3.3.3
$\star $
strong ergodicity for non-constant bounded length substitution
Definition 3.29. Let
$M= (M_{ij})_{i,j \geq 0}$
be a non-negative matrix such that M is irreducible, aperiodic, positive recurrent and
$\|M\| < + \infty .$
We say that M is
$\star $
ergodic if for all
$i, j \in \mathbb {Z}_+,$
$$ \begin{align} \lim_{n \to +\infty} \frac{M^{n}_{ij}}{\sum_{k=0}^{+\infty} M^{n}_{ik} } = z_{j}>0, \end{align} $$
where the vector
$(z_j)_{j \geq 0}$
has
$1$
as coordinates sum and that M is
$\star $
strongly ergodic if there exists a vector
$(z_{j})_{j \geq 0} $
of positive real numbers such that
$\sum _{j=0}^{+\infty } z_j= 1$
and
$$ \begin{align*}\lim_{n \to \infty} sup_{i \geq 0} \sum_{j = 0}^{\infty} \bigg| \frac{ M^{n}_{ij} }{\sum_{k=0}^{+\infty} M^{n}_{ik} } - z_{j} \bigg| = 0.\end{align*} $$
Remark 3.30. If M is
$\star $
strongly ergodic, then it is clear that M is
$\star $
ergodic.
Question 3.5. Is
$M= (M_{ij})_{i,j \geq 0}\ \star $
ergodic equivalent to M positive recurrent with right Perron eigenvector in
$l^1$
? The last question has a positive answer when M is a multiple of a stochastic matrix.
An important result is the following.
Proposition 3.31. Let
$M= (M_{ij})_{i,j \geq 0}$
be an irreducible, aperiodic matrix with finite Perron value
$\unicode{x3bb} $
. Assume that M has a right Perron eigenvector
$r= (r_i)_{i \geq 0} \in l^{\infty }$
satisfying
$\inf \{r_i,\; i \in \mathbb {Z}_+\}>0$
. If M is strongly ergodic, then M is
$\star $
strongly ergodic.
Proof. It is just Lemma 3.26.
Question 3.6. Does there exist a non-negative matrix
$M= (M_{ij})_{i,j \geq 0}$
which is strongly ergodic (respectively
$\star $
strongly ergodic), but not
$\star $
strongly ergodic (respectively strongly ergodic)?
Lemma 3.32. Let
$M= (M_{ij})_{i,j \geq 0}$
be a
$\star $
ergodic matrix with finite Perron value
$\unicode{x3bb} $
and with right Perron eigenvector
$r= (r_i)_{i \geq 0}$
, then any left Perron eigenvector of M belongs to
$l^1$
. Moreover,
$$ \begin{align} \lim_{n \to \infty } \sum_{k=0}^{+\infty} \frac{M^n_{i k}}{ \unicode{x3bb}^n}= \sum_{k=0}^{+\infty} \lim_{n \to \infty } \frac{M^n_{i k}}{ \unicode{x3bb}^n} = c \, r_i \quad\text{for all } i \in \mathbb{Z}_+ , \end{align} $$
for some
$c>0$
, and
$$ \begin{align} \lim_{n \to +\infty} \frac{M^{n}_{ij}} {\sum_{k=0}^{+\infty} M^{n}_{ik} } = \frac{l_j}{\sum_{k=0}^{+\infty} l_k}>0 \quad \text{for all } i,j \in \mathbb{Z}_+. \end{align} $$
Proof. By
$\star $
ergodicity,
$$ \begin{align*} \lim_{n \to +\infty} \frac{M^n_{ij}}{\sum_{k=0}^{+\infty} M^{n}_{ik} } = z_j. \end{align*} $$
Moreover, since M is positive recurrence, we have that
$$ \begin{align} \lim_{n \to +\infty} \frac{M^n_{ij}}{\unicode{x3bb}^n} = l_j r_i , \end{align} $$
where
$l = (l_j)_{j\ge 1}$
is a left Perron eigenvector such that
$l \cdot r = 1$
. Thus,
$$ \begin{align*} \lim_{n \to +\infty} \sum_{k=0}^{+\infty} \frac{M^{n}_{ik} }{\unicode{x3bb}^n} = \lim_{n \to +\infty} \frac{\sum_{k=0}^{+\infty} M^{n}_{ik}}{M^{n}_{ij}} \frac{M^{n}_{ij}}{\unicode{x3bb}^n} = \frac{l_j}{z_j} r_i. \end{align*} $$
The left-hand side above does not depend on j, and thus l is a multiple of
$(z_j)_{j\ge 1} \in l^1$
. Thus,
$l \in l^1$
and we also have equation (3.39), and equation (3.38) follows from the last equality and equation (3.40).
Theorem 3.33. Let
$\sigma $
be a bounded length substitution on
$A= \mathbb {Z}_+$
with non-constant length such that
$\sigma $
has a periodic point u and
$M_{\sigma }$
is irreducible, aperiodic. If
$M_{\sigma }$
and
$M_{\sigma _t}, \; t \geq 2$
are
$ \star $
strongly ergodic, then the dynamical system
$(\Omega _{\sigma }, S)$
has a unique probability shift invariant measure.
Acknowledgements
Sébastien Ferenczi and Ali Messaoudi were partially supported by the Brazilian Federal Agency for Support and Evaluation of Graduate Education (CAPES), in the scope of the Program CAPES-PrInt, grant number 88887.310463/2018-00 and International Cooperation grant number 88881.310741/2018-01. Ali Messaoudi was partially supported by CNPq grant 310784/2021-2 and by Fapesp grant 2019/10269-3. Glauco Valle was supported by CNPq grant 307938/2022-0 and by FAPERJ grant 26/202.636/2019.
