This work is licensed under the Creative Commons Attribution 4.0 International License.
Introduction
A well-known classification of the infinite loaded graphs, or, which is the same, the infinite non-negative matrices, is very close to that of the Markov chains with infinitely many states: there are recurrent and transient loaded graphs, null recurrent and positive recurrent ones, while the latter can be stable positive and unstable positive. Distinctions between the last two classes (for details see [1]) justify their names. The aim of this note is to show by simple examples what happens if one deletes some edges of the graph, using a random mechanism. It turns out that some of the above classes are stable with respect to small random perturbations, while the others are not.
Basic definitions, description of the model
Consider a directed graph G = (V, E), where V = V (G) is the set of its vertices and E = E(G) ⊂ V × V the set of edges. A path of length n in G is a sequence γ = e1,...,en of edges such that the beginning of the edge ei+1 coincides with the end of the edge ei, 1 ≤ i < n. Every function 𝒲 : E → (0, ∞) is called a weight function, and the pair (G, 𝒲) is said to be a loaded graph. The weight 𝒲 (γ) of a path γ is defined as the product of the weights over the edges forming γ. The graph G is assumed to be connected: for every pair of vertices u, v ∈ V (G) there exists a path from u to v.
Recall a classification of the loaded graphs (see [1], [2] for details). For every vertex v ∈ V (G), let Γv,v denote the set of all v-cycles, i.e., the paths γ from v to v, and Γv, v |v denote the set of those γ ∈ Γv, v in which v is only the first and last vertex. We refer to elements of Γv, v|v as primitive v-cycles.
For a fixed v ∈ V (G), denote by qn = qn(G,𝒲,v) the sum of the weights over all primitive v-cycles of length n, and assume that qn < ∞ for all n. Introduce the generating function
{\Phi _{v,v|v}}(G,{\cal W},t): = \sum\limits_{n = 1}^\infty {q_n}{t^n}.
Let Rv = R(G, 𝒲, v) be the radius of convergence of this power series; assume that Rv > 0.
Definition 1
A loaded graph (G, 𝒲) is said to be stable positive, unstable positive, and null recurrent if there is a vertex v ∈ V (G) such that
{\Phi _{v,v|v}}(G,{\cal W},{R_v}) > 1,{\Phi _{v,v|v}}(G,{\cal W},{R_v}) = 1,\;{d \over {dt}}{\Phi _{v,v|v}}(G,{\cal W},t{)|_{t = {R_v}}} < \infty,
and
{\Phi _{v,v|v}}(G,{\cal W},{R_v}) = 1,\;{d \over {dt}}{\Phi _{v,v|v}}(G,{\cal W},t{)|_{t = {R_v}}} = \infty,
respectively. Stable positive and unstable positive loaded graphs form the set of positive recurrent loaded graphs, while positive recurrent and null recurrent loaded graphs form the set of recurrent ones. The remaining loaded graphs with Rv > 0 are said to be transient.
Since G is connected, the following is true: if Rv > 0 for some v, then Rv > 0 for all v ∈ V (G), and if some of the conditions (2)–(4) holds for a given v, then it does for all v ∈ V (G).
In [1], §3 several characteristic properties of stable recurrent and unstable recurrent loaded graphs are collected and this terminology is justified.
Let us now describe the loaded graphs (G, 𝒲) that will be the subject of further studies in this paper. For V = V (G) we take ℕ, the set of positive integers, and for E = E(G) the union E1 ∪ E2 ∪ E3, where E1 is the collection of all pairs (i, i + 1), i ∈ ℕ; E2 is the collection of the pairs (i, 1), i ∈ ℕ, and E3 is formed by some pairs of the form (i, j), where i, j ∈ ℕ, i < j − 1. We will refer to such a graph as linear. Suppose the following bounded forward jump (BFJ) condition is satisfied: there is d > 0 such that j − i ≤ d for all (i, j) ∈ E3.
Notice that in [4], Example 5.6, a close class of loaded graphs was introduced in other terms and for another purpose.
Given an arbitrary linear graph G, one can chose, for each of the above classes of loaded graphs, a weight function 𝒲 in such a way that the loaded graphs (G, 𝒲) will fall into this class.
For a fixed loaded graph (G, 𝒲) we consider a random loaded graph (G, 𝒲, ξ) that differs from (G, 𝒲) in that the weight of every edge of the form (i, 1) ∈ E2 is multiplied by a random variable ξi with values in {0,1}, i.e., remains intact or disappears under the action of some stochastic mechanism. Let us assume that this mechanism is described by a stationary random sequence ξ := (ξi, i ∈ ℤ) with decay of long-range dependence.
Classes of random linear loaded graphs
We begin with the following notion from ergodic theory.
An invertible measure preserving transformation T (automorphism) of a probability space (Ω, ℱ, P) is said to be lightly mixing (see [5]) if
\mathop {\lim\inf}\limits_{n \to \infty} {\bf{P}}(A \cap {T^{- n}}B) > 0
for all A, B ∈ ℱ with P(A) > 0, P(B) > 0. The next lemma is due to Blum, Christiansen and Quiring [6], who used another terminology.
Lemma 1
If T is a lightly mixing automorphism of a probability space (Ω, ℱ, P), then for every infinite increasing sequence of positive integers nk, k = 0, 1,..., and every set F ∈ ℱ withP(F) > 0, we have{\bf{P}}(\cup _{k = 0}^\infty {T^{- {n_k}}}F) = 1.
Remark 1
(see [6]) The automorphisms for which (5) holds are sometimes called sequence mixing or sweeping out. This property is known to be equivalent to the lightly mixing one.
If the shift in the sample space of a stationary process is lightly mixing, we say that the process itself is lightly mixing.
Corollary 2
If a stationary random process ξ = {ξi, i ∈ ℤ+} with values 0 and 1 is lightly mixing, then for every increasing infinite sequence of positive integers ri and every r ∈ ℕ, there exists with probability 1 an i such that ri > r and ξri = 1.
Proof
Let Ω be the sample space of the process ξ (Ω consists of the double-sided infinite sequences of zeroes and ones), T the one step left shift in Ω, ℱ the cylinder σ-algebra in Ω and P the probability measure on (Ω, ℱ) induced by the process ξ. Let us assume the process ξ is defined on (Ω, ℱ P) as follows: if ω = (ωi, i ∈ ℤ) ∈ Ω, then ξn(ω) = ωn, n ∈ ℤ. Put F := {ω ∈ Ω : ω0 = 1}. Suppose that the automorphism T of the space (Ω, ℱ, P) is lightly mixing. Then the desired statement follows from Lemma 1 applied to F and the numbers nk := ri0+k, where i0 = min{i : ri > r}.
We now come back to the random linear loaded graph described in Section 2. For such a graph we will write
\Phi _{v,v|v}^{(\xi)}(G,{\cal W})
,
R_v^{(\xi)}
, and qn(ξ) instead of Φv, v|v(G, 𝒲), Rv and qn, respectively. Below it is assumed that v = 1.
Theorem 3
Let 1) a linear graph G satisfies the BFJ condition, 2) a weight function 𝒲 is bounded, and 3) a stationary random process ξ with values 0, 1 induces a lightly mixing shift. Then for the random linear loaded graph (G, 𝒲, ξ) we have{\bf{P}}(R_v^{(\xi)} = {R_v}) = 1
.
Proof
Let us first consider the linear loaded graph (G, 𝒲). By the Cauchy-Hadamard formula there is a sequence of positive integers nk such that
1/{R_v} = \mathop {\lim\sup}\limits_{n \to \infty} {({q_n})^{1/n}} = \mathop {\lim}\limits_{k \to \infty} {({q_{{n_k}}})^{1/{q_{{n_k}}}}}.
The last expression will not change if we take an arbitrary infinite subsequence of {nk} instead of {nk} itself. By Corollary 2 there exists with probability one an infinite subsequence {
n_k^{'}
} such that
{\xi_{n_k^{'}}} = 1
for every k. Hence, by (6), with probability one
1/R_v^{(\xi)} = \mathop {\lim\sup}\limits_{k \to \infty} {({q_n}(\xi))^{1/n}} \ge 1/{R_v}.
But it is clear that the converse inequality holds, since qn(ξ) ≤ qn for all n. Hence
R_v^{(\xi)} = {R_v}
with probability 1, which proves the theorem.
Let us now find out how
\Phi _{v,v|v}^{(\xi)}(G,{\cal W},R_v^{(\xi)})
behaves when the process ξ can be treated as a small random perturbation of the process that identically equals one. Consider a sequence of stationary random processes
{\xi ^{(k)}} = \{\xi _i^{(k)},{\kern 1pt} i \in \mathbb {Z}\}
defined on the above-described sequence space (Ω, ℱ), and for k = 1, 2,..., introduce the probability measure P(k), corresponding to ξ(k). Assume that there exists an increasing sequence of positive integers rk such that
\mathop {\lim}\limits_{k \to \infty} {{\bf{P}}^{(k)}}(\xi _1^{(k)} = \ldots = \xi _{{r_k}}^{(k)} = 1) = 1.
This will be referred to as the dominating 1 (D 1) condition. If
\xi _i^{(k)}
, for every k, are independent random variables such that
\xi _i^{(k)} = 1
with probability pk and
\xi _i^{(k)} = 0
with probability 1 − pk, then the D 1 condition is satisfied when limk → ∞pk=1. It is easy to define a sequence of stationary Markov chains for which it is also obeyed. But there are Markov chains, even mixing ones, without this property. On the other hand, it is obeyed by some non-Markovian stationary processes.
Theorem 4
Let (G, 𝒲) be a stable positive loaded graph, where G is a linear graph defined in § 2, {ξ(n)} a sequence of lightly mixing stationary random processes with values 0 and 1 satisfying the D 1 condition, and {(G, 𝒲, ξ(n)‘)} the corresponding sequence of random loaded graphs. Then the random loaded graph (G, 𝒲, ξ(n)) is stable positive with probability one as n is large enough.
Proof
In what follows we mean that all relations between random variables hold with probability one. Since (G, 𝒲) is stable positive, we have
\sum\nolimits_{n = 1}^\infty {q_n} \cdot {({R_v})^n} > 1
(see (1) and Definition 1), and one can choose an n0 ∈ ℕ such that
\sum\nolimits_{n = 1}^{{n_0}} {q_n} \cdot {({R_v})^n} > 1
. The D 1 condition enables one to find k with rk ≥ n0 (see (7)). Then qn(ξ(k)) = qn for all n ≥ n0, and hence
\sum\nolimits_{n = 1}^{{n_0}} {q_n}({\xi ^{(k)}}) \cdot {({R_v})^n} > 1
. From Theorem 3 we know that
R_v^{({\xi ^{(k)}})} = {R_v}
. Therefore,
{\Phi _{v,v|v}}(G,{\cal W},R_v^{({\xi ^{(k)}})}) = \sum\limits_{n = 1}^\infty {q_n}({\xi ^{(k)}}) \cdot {(R_v^{({\xi ^{(k)}})})^n} > 1,
i.e., the random loaded graph (G, 𝒲, ξ(k)) is stable positive with probability one.
Remark 2
It is easy to see that if (G, 𝒲) is unstable positive, null recurrent, or transient, while ξ = (ξi, i ∈ ℤ) is a lightly mixing stationary random process with values 0 and 1 such that P(ξi = 0) > 0, then the random loaded graph (G, 𝒲, ξ) is transient with probability one (in view of Theorem 3). Thus among the linear loaded graphs we defined in Section 2 only the stable positive and transient classes are stable with respect to the small random perturbations of the above type.
The author is indebted to V.I. Oseledets and V.V. Ryzhikov for critical information relating to Lemma 1 and thanks the referee for useful suggetions.
