Markov approximation of arbitrary random field on homogeneous trees

By a tree, T we mean an infinite, locally finite, connected graph with a distinguished vertex o called the root and without loops or cycles. We only consider trees without leaves. That is, the degree of each vertex (except o) is required to be at least two. Let σ, τ be vertices of a tree. Write τ ≤ σ if τ is on the unique path connecting o to σ, and |σ| for the number of edges on this path. For any two vertices, σ, τ, denote by σ ∧ τ the vertex farthest from o satisfying σ ∧ τ ≤ σ,σ ∧ τ ≤ τ.

Some tree models have been introduced in the literature. We say a homogeneous tree, namely, a Bethe tree, on which each vertex has N + 1 neighboring vertices. Another homogeneous tree is a rooted Cayley tree T _C,N --the root has N neighbors, and the other vertices have N + 1 neighbors.

The set of all vertices with distance n from the root o is called the n th generation (or n th level) of T, which is denoted by L _n , L₀ = {o}. We denote by T ( m ) ( n ) the subtree of a tree T containing the vertices from level m to level n, especially T⁽ⁿ⁾the subtree of a tree T containing the vertices from level 0 to level n. Let t be a vertex of T, predecessor of the vertex t is another vertex which is the nearest from t on the unique path from root o to t. We denote the predecessor of t by 1 _t , the predecessor of 1 _t by 2 _t , the predecessor of n _t by (n + 1) _t , and 0 _t = t, where n = 0,1, 2,.... We also say that n _t is the n th predecessor of t. X ^A = {X _t , t ∈ A} is a stochastic process indexed by a set A, and denoted by |A| the number of vertices of A; x ^A is the realization of X ^A .

Let ( Ω , ℱ ) be a measurable space, and {X _t , t ∈ T} be a collection of random variables defined on ( Ω , ℱ ) and take value in states space S.

Definition 1 (Tree-indexed Markov chains ) Let T be a tree, S be a finite space, and {X _σ , σ ∈ T} be a collection of S-valued random variables defined on the probability space ( Ω , ℱ , P ). Let

be a distribution on S, and

be stochastic matrices on S². If for each vertex t ∈ T,

and

then {X _t , t ∈ T} will be called S- value Markov chains indexed by tree with the initial distribution (1) and transition matrix (2), or called tree-indexed Markov chains.

The above definition is the extension of the definitions of Tree-indexed homogeneous Markov chains [1].

We say a distribution p > 0 if p(x) > 0 for all x ∈ S; a stochastic matrix (P(y|x))_x,y∈Sis positive if P(y|x) > 0 for all x,y ∈ S. Denote the distribution of {X _t ,t ∈ T} under the probability measure P by P ( x T ( n ) ) = P ( X T ( n ) = x T ( n ) ). It is easy to see that if {X _t , t ∈ T} is a S-valued Markov chains indexed by a tree defined as above, then

Definition 2 [2] Let {X _σ , σ ∈ T} be a collection of S-valued random variables defined on ( Ω , ℱ ) , p > 0 , ( P ( y x ) ) x , y ∈ S be a positive stochastic matrix, μ, P be two probability measure on ( Ω , ℱ ), and {X _σ , σ ∈ T} be Markov chains indexed by tree T under probability measure P. Assume that μ ( x T ( n ) ) is always strictly positive. Let

then φ(ω) will be called the asymptotic logarithmic likelihood ratio.

Remark 1 If μ = P, φ(ω) ≡ 0 holds. Lemma 1 will show that in general case φ(ω) ≥ 0 μ- a.e.; hence, φ(ω) can be regarded as a measure of the Markov approximation of the arbitrary random field on T.

The tree models have recently drawn increasing interest from specialists in physics, probability, and information theory. Benjamini and Peres [1] have given the notion of the tree-indexed homogeneous Markov chains and studied the recurrence and ray-recurrence for them. Berger and Ye [3] have studied the existence of entropy rate for some stationary random fields on a homogeneous tree. Ye and Berger [4] have studied the asymptotic equipar-tition property (AEP) in the sense of convergence in probability for a PPG-invariant(A PPG is the group of graph automorphisms of T that preserve the parities of all vertices. A random field is said to be PPG-invariant if the probability of any finite cylinder set remains invariant under any automorphism of PPG) and ergodic random field on a homogeneous tree. Recently, Yang [5] have studied some strong limit theorems for countable homogeneous Markov chains indexed by a homogeneous tree and the strong law of large numbers and the AEP for finite homogeneous Markov chains indexed by a homogeneous tree. Yang and Ye [6] have studied strong theorems for countable nonhomogeneous Markov chains indexed by a homogeneous tree and the strong law of large numbers and the AEP for finite nonhomogeneous Markov chains indexed by a homogeneous tree. Small deviation theorems are a class of strong limit theorems expressed by inequalities. They are the extensions of strong limit theorems expressed by equalities. It is a new research topic introduced by Professor Liu Wen [7]. Later, Liu and Yang [8] studied the small deviation theorems for the averages of the bivariate functions of {X _n , n ≥ 0}. Liu and Wang [2] studied the small deviation between the arbitrary random fields and the Markov chain fields on Cayley tree. Peng et al [9] established the small deviation theorems for functional of the random fields on homogeneous trees; some of the theorems partly generalized the result of [2].

In this article, the main result can completely generalize the result in [2](Corollary 3). We obtain the small deviation theorems for the random fields and the frequencies of state-ordered couples for random fields on homogeneous trees. Both the result and the method are apparently different from [9]. We arrange the rest of the article as follows:

First, we introduce the asymptotic logarithmic likelihood ratio as a measure of Markov approximation of the arbitrary random field on a homogeneous tree. Second, by constructing a non-negative supermartingale, we obtain a class of small deviation theorems for functionals of random fields on a homogeneous tree. Finally, we establish the small deviation theorems for the frequencies of occurrence of states and ordered couple of states for random fields on a homogeneous tree.

Lemma 1 [2] Let μ₁, μ₂ be two probability measures on ( Ω , ℱ ), and D ∈ ℱ , { τ n , n ≥ 1 } be a sequence of positive random variables such that

Then,

Remark 2 Let μ₁ = μ, μ₂ = P, by (9) there exists A ∈ ℱ , μ ( A ) = 1 such that

and hence we have φ(ω) ≥ 0, ω ∈ A.

Let k, l ∈ S, S _n (k, ω) (denoted by S _n (k)) be the number of k in the set of random variables X T ( n ) = { X t : t ∈ T ( n ) }, and S _n (k, l,ω)(denoted by S _n (k, l)) be the number of couple (k, l) in the set of random couples: { ( X 1 t , X t ) , t ∈ T }, i.e.,

where δ _k (.)(k ∈ S) is Kronecker δ-function:

Lemma 2 [2] Let μ be a probability measure on ( Ω , ℱ ), and φ(ω) be denoted by (7), 0 ≤ c < ln(1 - a _k )^-1 be a constant, and

where a _k = max{P(k|i), i ∈ S}, b _k = min{P(k|i), i ∈ S}. Then,

Lemma 3 Let 0 <f _n (x, y) ≤ 1 be real functions. Then for all λ > 0, we have

Proof It is easy to verify that λ f n ( x , y ) - ( λ - 1 ) f n ( x , y ) - 1 ≤ 0 for all λ > 0, the above inequality holds immediately.

Lemma 4 Let μ, P be two probability measures on ( Ω , ℱ ) , p > 0 , ( P ( y x ) ) x , y ∈ S be a positive stochastic matrix, {X _σ ,σ ∈ T} be Markov chains indexed by T under probability measure P, 0 <f _n (x, y) ≤ 1 be real functions defined on S², L₀ = {o}(o is the root of the tree T), ℱ n = σ ( X T ( n ) ), and λ be a real number. Let

where E _P is the expectation under probability measure P. Then, ( t n ( λ , ω ) , ℱ n , n ≥ 1 ) is a non-negative supermartingale under probability measure μ.

Proof By Lemma 3, we have

and hence ( t n ( λ , ω ) , ℱ n ) is a non-negative supermartingale under probability measure μ.

Small deviation theorems are a class of strong limit theorems expressed by inequalities. They are the extensions of strong limit theorems expressed by equalities. It is a new research topic proposed by Professor Liu Wen [9].

In this section, we will establish a class of small deviation theorem for functionals of random fields on homogenous trees. As corollary, we obtain the frequencies of state-ordered couples for random fields on homogeneous trees.

Theorem 1 Let T be a homogeneous tree (Bethe tree or Cayley tree), μ, P be two probability measures on ( Ω , ℱ ) , p > 0 , ( P ( y x ) ) x , y ∈ S be a positive stochastic matrix, {X _σ ,σ ∈ T} be Markov chains indexed by T under probability measure P, 0 <f _n (x, y) ≤ δ _l (x)δ _k (y) be real functions defined on S², and λ be a real number. Let φ (ω) and F _n (ω) be denoted by (7) and (15), respectively. Let c ≥ 0,

Then,

When 0 <c <P (l|k)M _k ,

Proof Let t _n (λ, ω) be defined by (16). By Lemma 4, ( t n ( λ , ω ) , ℱ n , n ≥ 1 ) is a non-negative supermartingale under probability measure μ. By Doob's martingale convergence theorem, we have

Hence,

By (14), we get

We have by (15), (16) and (21)

By (6), (7), (17), (22), and 0 ≤ c < ln(1 - a _k )^-1, we have

By (23) and the inequality lim sup n → ∞ ( a n + b n ) ≤ lim sup n → ∞ a n + lim sup n → ∞ b n, we have

Let λ > 1, we have by (24),

By (17), (25) and inequality 1 - 1/x ≤ ln x ≤ x - 1 (x > 0), we have

By 0 <f _n (x, y) ≤ δ _l (x) δ _k (y), we have lim sup n → ∞ G n ( ω ) / [ N S n - 1 ( k ) ] ≤ P ( l k ). By (26) we get

Let g(λ) = (λ - 1)P(l|k) + λc/[(λ - 1)M _k ] (λ > 1). In the case c > 0, (19) holds by (27) because g(λ) attains its smallest value g ( 1 + c / [ P ( l k ) M k ] ) = 2 P ( l k ) c / M k + c / M k on the interval (1,+∞); In the case c = 0, (19) also holds by choosing λ _i → 1 + 0(i → ∞) in (27).

Let 0 <λ < 1, we have by (24) then

By (17), (28), and inequality 1 - 1/x ≤ ln x ≤ x - 1 (x > 0), we have

Let h(λ) = (λ-1)P(l|k)+c/[(λ - 1)M _k ] (0 <λ < 1). In the case c > 0, (20) holds by (29) because h (λ) attains its largest value h ( 1 - c / [ P ( l k ) M k ] ) = - 2 c P ( l k ) / M k on the interval (0,1); In the case c = 0, (20) also holds by choosing λ _i → 1 - 0(i → ∞) in (29). This is the end of the proof.

Corollary 1 Under the assumption of Theorem 1, we have

Proof (30) holds by setting c = 0 in Theorem 1.

Corollary 2 Under the assumption of Theorem 1, we have

Proof Let μ = P in Theorem 1, then φ _n (ω) ≡ 0, D (0) = Ω, and (31) follows immediately.

Corollary 3 (see [2]) Under the assumption of Theorem 1, we have

and when 0 ≤ c ≤ M _k P(l|k), we have

Proof Let f _n (x, y) = δ _l (x) δ _k (y) in Theorem 1, then F _n (ω) = S _n (k, l), G _n (ω) = NS_n-1(k)P(l|k), and (32) and (33) hold obviously.