In this paper, we establish a class of strong limit theorems, represented by inequalities, for the arbitrary random field with respect to the product binomial distributions indexed by the infinite tree on the generalized random selection system by constructing the consistent distribution and a nonnegative martingale with pure analytical methods. As corollaries, some limit properties for the Markov chain field with respect to the binomial distributions indexed by the infinite tree on the generalized random selection system are studied.
AMS Mathematics Subject Classification : 60F15, 65F15.
1. Introduction
A tree is a graph
S
= {
T
,
E
} which is connected and contains no circuits. Given any two vertices
σ
,
t
(
σ
≠
t
∈
T
), let
be the unique path connecting
σ
and
t
. Define the graph distance
d
(
σ
,
t
) to be the number of edges contained in the path
.
Let
T
be an arbitrary infinite tree that is partially finite (i.e. it has infinite vertices, and each vertex connects with finite vertices) and has a root
o
. For a better explanation of the infinite root tree
T
, we take Cayley tree
T_{C,N}
for example. It’s a special case of the tree
T
, the root
o
of Cayley tree has
N
neighbors and all the other vertices of it have
N
+ 1 neighbors each (see
Fig.1
).
An infinite tree T_{C,2}
Let
σ
,
t
be vertices of the infinite tree
T
. Write
t
≤
σ
(
σ
,
t
≠ −1) if
t
is on the unique path connecting
o
to
σ
, and 
σ
 for the number of edges on this path. For any two vertices
σ
,
t
of the tree
T
, denote by
σ
∧
t
the vertex farthest from
o
satisfying
σ
∧
t
≤
σ
and
σ
∧
t
≤
t
.
The set of all vertices with distance
n
from root
o
is called the
n
th generation of
T
, which is denoted by
L_{n}
. We say that
L_{n}
is the set of all vertices on level
n
. We denote by
T
^{(n)}
the subtree of the tree
T
containing the vertices from level 0(the root
o
) to level
n
. Let
t
(≠
o
)be a vertex of the tree
T
. We denote the first predecessor of
t
by 1
_{t}
, the second predecessor of
t
by 2
_{t}
, and denote by
n_{t}
the
n
th predecessor of
t
. Let
X^{A}
= {
X_{t}
,
t
∈
A
}, and let
x^{A}
be a realization of
X^{A}
and denote by 
A
 the number of vertices of
A
.
Suppose that
S
= {0, 1, 2, 3,⋯,
N
} is a finite state space. Let Ω =
S^{T}
,
ω
=
ω
(·) ∈ Ω, where
ω
(·) is a function defined on
T
and taking values in
S
, and
F
be the smallest Borel field containing all cylinder sets in Ω,
μ
be the probability measure on (Ω,
F
) . Let
X
= {
X_{t}
,
t
∈
T
} be the coordinate stochastic process defined on the measurable space (Ω,
F
), that is, for any
ω
= {
ω
(
t
),
t
∈
T
}, define
Now we give a definition of Markov chain fields on the tree
T
by using the cylinder distribution directly, which is a natural extension of the classical definition of Markov chains (see
[4]
).
Definition 1.
Let {
p_{t}
,
t
∈
T
^{(n)}
} be a sequence of positive real numbers, denote
p_{t}
∈ (0, 1),
t
∈
T
^{(n)}
. If
Then
μ_{P}
will be called a random field which obeys the product binomial distributions (2) indexed by the homogeneous tree
T
.
Definition 2.
Let {
f_{n}
(
x
_{1}
,⋯,
x_{n}
),
n
≥ 1} be a sequence of realvalued functions defined on
S^{n}
(
n
= 1, 2,⋯ ), which will be called the generalized selection functions if {
f_{n}
,
n
≥ 1} take values in a nonnegative interval of [0,
b
]. We let
where 
t
 stands for the number of the edges on the path from the root
o
to
t
. Then {
Y_{t}
,
t
∈
T
^{(n)}
} is called the generalized gambling system or the generalized random selection system indexed by an infinite tree with uniformly bounded degree. The traditional random selection system {
Y_{n}
,
n
≥ 0}
[10]
takes values in the set of {0, 1}.
We first explain the conception of the traditional random selection, which is the crucial part of the gambling system. We give a set of realvalued functions
f_{n}
(
x
_{1}
,⋯,
x_{n}
) defined on
S^{n}
(
n
= 1, 2,⋯ ), which will be called the random selection function if they take values in a twovalued set {0, 1}. Then let
where {
Y_{n}
,
n
≥ 1} be called the gambling system (the random selection system).
In order to explain the real meaning of the notion of the random selection, we consider the traditional gambling model. Let {
X_{n}
,
n
≥ 0} be an independent sequence of random variables, and {
g_{n}
(x),
n
≥ 1} be a realvalued function sequence defined on
S
. Interpret
X_{n}
as the result of the
n
th trial, the type of which may change at each step. Let
μ
n
=
Y_{n}g_{n}
(
X_{n}
) denote the gain of the bettor at the
n
th trial, where
Y_{n}
represents the bet size,
g_{n}
(
X_{n}
) is determined by the gambling rules, and {
Y_{n}
,
n
≥ 0} is called a gambling system or a random selection system. The bettor’s strategy is to determine {
Y_{n}
,
n
≥ 1} by the results of the previous trials. Let the entrance fee that the bettor pays at the
n
th trial be
b_{n}
. Also suppose that
b_{n}
depends on
Y
_{n−1}
as
n
≥ 1, and
b
_{0}
is a constant. Thus
represents the total gain in the first
n
trials,
the accumulated entrance fees, and
the accumulated net gain. Motivated by the classical definition of ”fairness” of game of chance (see Kolmogorov
[10]
), we introduce the following definition.
Definition 3.
The game is said to be fair, if for almost all
, the accumulated net gain in the first
n
trial is to be of smaller order of ma
g_{n}
itude than the accumulated stake
as
n
tends to infinity, that is
Definition 4.
Let {
X_{t}
,
t
∈
T
} be an arbitrary random field defined by (1), and {
p_{t}
,
t
∈
T
} be a sequence of positive real numbers,
p_{t}
∈ (0, 1). We set
for the likelihood ratio and the logarithmic likelihood ratio of {
X_{t}
,
t
∈
T
}, relative to the product binomial distribution.
where log is natural logarithm.
ω
is the sample point. Let
Then it will be shown in (31) that
r
(
ω
) ≤ 0
a.s.
in any case. Hence,
r_{n}
(
ω
) can be used as a random measure of the deviation between the true joint distribution function
μ
(
X
^{T(n)}
) and the reference product binomial distribution function
. Roughly speaking, this deviation may be regarded as the one between
X
^{T(n)}
and the independent case. The smaller
r_{n}
(
ω
) is, the smaller the deviation is.
There have been some works on limit theorems for treeindexed stochastic processes. Benjamin
i
and Peres have given the notion of the treeindexed homogeneous Markov chains and studied the recurrence and rayrecurrence for them (see
[1]
).Liu and Ma have studied strong limit theorem for the average of ternary functions of Markov chains in biinfinite random environments. (see
[2]
). Yang proved some strong laws of large numbers for asymptotic evenodd Markov chains indexed by a homogeneous tree (see
[5]
). Li and Yang have studied strong convergence properties of pairwise NQD random sequences (see
[6]
). Ye and Berger, by using Pemantle’s result and a combinatorial approach, have studied the asymptotic equipartition property (AEP) in the sense of convergence in probability for a PPGinvariant and ergodic random field on a homogeneous tree(see
[9

10]
). Peng and Yang have studied a class of small deviation theorems for functionals of random field and asymptotic equipartition property (AEP) for arbitrary random field on a homogeneous trees (see
[8]
). Recently, Yang have studied some limit theorems for countable homogeneous Markov chains indexed by a homogeneous tree and strong law of large numbers and the asymptotic equipartition property (AEP) for finite homogeneous Markov chains indexed by a homogeneous tree (see
[7]
and
[11]
). Wang has also studied some ShannonMcMillan approximation theorems for arbitrary random field on the generalized Bethe tree (see
[12]
). Zhong and Yang (see
[14]
) have studied some asymptotic equipartition properties (AEP) for asymptotic circular Markov chains. Wang (see
[15]
) has also discussed some small deviation theorems for stochastic truncated function sequence for arbitrary random field indexed by a homogeneous tree.
It is known to all that the binomial distribution is one of the classical probability distributions. It has comprehensive applications in all fields of the economical life. In this paper, our aim is to establish a class of strong limit theorems represented by the inequalities for the arbitrary random field with respect to the product binomial distributions indexed by the infinite tree by constructing the consistent distribution and a nonnegative martingale with pure analytical methods. As corollaries, some limit theorems for the Markov chain field and the random field which obeys binomial distributions indexed by the infinite tree are generalized.
2. Main results
Lemma 1
(
[15]
).
Let μ
_{1}
and μ
_{2}
be two probability measures on
(Ω,
F
),
D
∈
F, denote α
> 0.
Let
{
σ_{n}
,
n
≥ 0}
be a nonnegative stochastic sequence such that
then
In particular, if σ_{n}
= 
T
^{(n)}

, we have
Proof
. See reference
[15]
. □
Theorem 1.
Let X
= {
X_{t}
,
t
∈
T
}
be an arbitrary random field defined by (1) taking values in S
= {0, 1, 2, 3,⋯,
N
}
indexed by the infinite tree T. We put
Denote α
> 1,
β
> 0, 0 ≤
c
< (
α
− 1)
^{2}
α^{b}bN
, then
Proof
. Consider the probability space (Ω,
F
,
μ
), let
λ
be an arbitrary real number,
δ_{i}
(
j
) be Kronecker function. We construct the following product distribution.
By (12) we can write
Therefore, we know
μ_{Q}
(
x
^{T(n)}
,
λ
),
n
≥ 0 are a family of consistent distribution functions defined on
S
^{T(n)}
. Denote
By (4) and (12), we can rewrite (14) as
Since
μ
and
μ_{Q}
are two probability measures, it is easy to see that {
U_{n}
(
λ
,
ω
),
F_{n}
,
n
≥ 1} is a nonnegative martingale according to Doob’s martingale convergence theorem(see
[12]
). Hence, we have
By the first inequality of (9), Lemma 1 and (14), we can write
According to (5) and (15), we can rewrite (17) as
By the limit property of superior limit, we can obtain by the second inequality of (9) and (18) that
Letting
λ
∈ (1,
α
) and dividing both sides of (19) by ln
λ
, we have
According to the property of superior limit
By (20) and the inequality
noticing that 0 ≤
Y_{t}
≤
b
,
t
∈
T
, we can writ
It is easy to show that in the case 0 <
c
< (
α
− 1)
^{2}
α^{b}bN
, the function
attains its smallest value
. Hence by (21), we have
In the case
c
= 0, we choose
λ_{i}
∈ (1,
α
)(
i
= 1, 2,⋯ ) such that
λ_{i}
→ 1
^{+}
(as
i
→ ∞), by (21) we have
It implies that (22) is also valid when
c
= 0.
Letting
λ
∈
, dividing both sides of (19) by ln
λ
, we get
In virtue of the property of inferior limit,
By (24) and inequality 1 − 1/
x
≤ ln
x
≤
x
− 1, (
x
> 0) , we can write
When 0 <
c
< (
α
− 1)
^{2}
α^{b}bN
, we can get the function
attains its smallest value
. Hence, it can follows from (25) that
In the case
c
= 0, we select
λ_{i}
∈
(
i
= 1, 2,⋯ ) such that
λ_{i}
→ 1
^{−}
(as
i
→ ∞), by (25) we attain
It means that (26) also holds in the case
c
= 0. □
Corollary 1.
Under the assumption of Theorem 1, we have
Proof
. Letting
c
= 0 in Theorem 1, (28) follows from (10), (11) immediately. □
Corollary 2.
Let X
= {
X_{t}
,
t
∈
T
}
be a random field taking values in S
= {0, 1, 2, 3,⋯,
N
}
which obeys the product binomial distributions (2) indexed by the infinite tree T. Then
where D
(
ω
)
is defined as (30)
.
Proof
. At the moment, we know that
μ_{P}
≡
μ
. Therefore, we obtain
r_{n}
(
ω
) ≡ 0,
D
(0) =
D
(
ω
). (29) follows from (28) immediately. □
Corollary 3.
Let X
= {
X_{t}
,
t
∈
T
}
be an arbitrary random field indexed by an infinite tree. r_{n}
(
ω
)
is defined by (5). Denote β
> 0,
Then
Proof
. Letting
λ
= 1 in (17), we get by (18)
(31) follows from (32) immediately. □
Corollary 4.
Under the assumption of Theorem 1, we have
Proof
. Letting
c
= 0 in Theorem 1, we obtain
(33) follows from (31) and
D
(0) directly. □
3. Some limit theorems for Markov chain field with respect to the binomial distributions.
Definition 5
(see
[7]
). Let
T
be an infinite tree,
S
= {0, 1, 2,⋯,
N
} be a finite state space, {
X_{t}
,
t
∈
T
} be a collection of
S
−valued random variables defined on the measurable space {Ω,
F
}. Let
be a distribution on
S
, and
be a strictly positive stochastic matrix on
S
^{2}
. If for any vertices
t
,
τ
,
{
X_{t}
,
t
∈
T
} will be called
S
−valued Markov chains indexed by an infinite tree with the initial distribution (34) and transition matrix (35).
Definition 6.
Let
Q
=
Q
(
j

i
) and
q
= (
q
(0),
q
(1) · · · ,
q
(
N
)) be defined as before,
μ_{Q}
be another probability measure on (Ω,
F
). If
then
μ_{Q}
will be called a Markov chain field on the infinite tree
T
determined by the stochastic matrix
Q
and the initial distribution
q
.
Theorem 2.
Let X
= {
X_{t}
,
t
∈
T
}
be a Markov chain field indexed by an infinite tree with the initial distribution (36) and the joint distribution (37). Denote Y_{t}
∈ [
a
,
b
], (
a
> 0)
t
∈
T. If
Then
Proof
. Let
μ
=
μ_{Q}
, by (4), (5) and (38) we can write
Hence, we obtain by (41)
It means that
D
(
c
) =
D
(
ω
). (39), (40) follow from (10), (11) immediately. □
4. Conclusion.
In this paper, we mainly investigate a kind of small deviation theorems, represented by inequalities, for the arbitrary random field with respect to the product binomial distributions indexed by the infinite tree on the generalized random selection system by constructing a series of consistent distributions and a nonnegative martingale with pure analytical methods. As results, some limit properties for the Markov chain field with respect to the binomial distributions indexed by the infinite tree on the generalized random selection system are obtained.
BIO
Fang Li received M.Sc. from Jiangsu University. Since 2005 she has been at Anhui Normal University. Her research interests include limit theory in probability theory and information theory.
College of Mathematics and Computer Science, Anhui Normal University, Wuhu 241000, China.
email: lifangahnu@aliyun.com
Kangkang Wang received M.Sc. from Jiangsu University and Ph.D at Nanjing University of Aeronautics and Astronautics. Since 2005 he has been at Jiangsu University of Science and Technology. His research interests include limit theory in probability theory and information theory.
School of Mathematics and Physics, Jiangsu University of Science and Technology, Zhenjiang 212003, China.
email: wkk.cn@126.com
Liu W.
,
Ma C.
,
Li Y.
,
Wang S.
(2015)
A strong limit theorem for the average of ternary functions of Markov chains in biinfinite random environments
Statist. Probab. Letts.
100
12 
18
DOI : 10.1016/j.spl.2015.01.029
Liu W.
,
Yang W.
(1996)
An extension of ShannonMcMillan theorem and some limit properties for nonhomogeneous Markov chains
Stochastic Process. Appl.
61
129 
145
DOI : 10.1016/03044149(95)000682
Yang W.
,
Zhao Y.
,
Pan H.
(2014)
Strong laws of large numbers for asymptotic evenodd Markov chains indexed by a homogeneous tree
J. Math. Anal. Appl.
410
179 
189
DOI : 10.1016/j.jmaa.2013.08.009
Peng W.
,
Yang W.
,
Wang B.
(2010)
A class of small deviation theorems for functionals of random fields on a homogeneous tree
J. Math. Anal. Appl.
361
293 
301
DOI : 10.1016/j.jmaa.2009.06.079
Ye Z.
,
Berger T.
(1996)
Ergodic regularity and asymptotic equipartition property of random fields on trees
J. Combin. Inform. System Sci.
21
157 
184
Ye Z.
,
Berger T.
1998
Information Measures for Discrete Random Fields
Science Press
New York
Yang W.
,
Ye Z.
(2007)
The asymptotic equipartition property for nonhomogeneous Markov chains indexed by a homogeneous tree
IEEE Trans. Inform. Theory
53
3275 
3280
DOI : 10.1109/TIT.2007.903134
Wang K.
,
Zong D.
2011
Some ShannonMcMillan approximation theoems for Markov chain field on the generalized Bethe tree
J. Ineq. and Appl.
Article ID 470910
18 
DOI : 10.1155/2011/470910
Kemeny J.G.
,
Snell J.L.
,
Knapp A.W.
1976
Denumerabl Markov chains
Springer
New York
Zhong P.
,
Yang W.
,
Liang P.
(2010)
The asymptotic equipartition property for asymptotic circular Markov chains
Probab. Eng. Inform. Sci.
24
279 
288
DOI : 10.1017/S0269964809990271
Wang K.
,
Peng W.
(2012)
Some small deviation theorems for the sequence of binary random truncated functions on a homogeneous tree
Newzealand Journal of Mathematics
42
91 
106