Advanced
SOME SMALL DEVIATION THEOREMS FOR ARBITRARY RANDOM FIELDS WITH RESPECT TO BINOMIAL DISTRIBUTIONS INDEXED BY AN INFINITE TREE ON GENERALIZED RANDOM SELECTION SYSTEMS†
SOME SMALL DEVIATION THEOREMS FOR ARBITRARY RANDOM FIELDS WITH RESPECT TO BINOMIAL DISTRIBUTIONS INDEXED BY AN INFINITE TREE ON GENERALIZED RANDOM SELECTION SYSTEMS†
Journal of Applied Mathematics & Informatics. 2015. Sep, 33(5_6): 517-530
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : December 12, 2014
  • Accepted : August 03, 2015
  • Published : September 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
FANG LI
KANGKANG WANG

Abstract
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 distri-bution 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.
Keywords
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
PPT Slide
Lager Image
be the unique path connecting σ and t . Define the graph distance d ( σ , t ) to be the number of edges contained in the path
PPT Slide
Lager Image
.
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 TC,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 ).
PPT Slide
Lager Image
An infinite tree TC,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 Ln . We say that Ln 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 nt the n -th predecessor of t . Let XA = { Xt , t A }, and let xA be a realization of XA and denote by | A | the number of vertices of A .
Suppose that S = {0, 1, 2, 3,⋯, N } is a finite state space. Let Ω = ST , ω = ω (·) ∈ Ω, 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 = { Xt , t T } be the coordinate stochastic process defined on the measurable space (Ω, F ), that is, for any ω = { ω ( t ), t T }, define
PPT Slide
Lager Image
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 { pt , t T (n) } be a sequence of positive real numbers, denote pt ∈ (0, 1), t T (n) . If
PPT Slide
Lager Image
Then μP will be called a random field which obeys the product binomial distributions (2) indexed by the homogeneous tree T .
Definition 2. Let { fn ( x 1 ,⋯, xn ), n ≥ 1} be a sequence of real-valued functions defined on Sn ( n = 1, 2,⋯ ), which will be called the generalized selection functions if { fn , n ≥ 1} take values in a nonnegative interval of [0, b ]. We let
PPT Slide
Lager Image
where | t | stands for the number of the edges on the path from the root o to t . Then { Yt , 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 { Yn , 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 real-valued functions fn ( x 1 ,⋯, xn ) defined on Sn ( n = 1, 2,⋯ ), which will be called the random selection function if they take values in a two-valued set {0, 1}. Then let
PPT Slide
Lager Image
where { Yn , 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 { Xn , n ≥ 0} be an independent sequence of random variables, and { gn (x), n ≥ 1} be a real-valued function sequence defined on S . Interpret Xn as the result of the n th trial, the type of which may change at each step. Let μ n = Yngn ( Xn ) denote the gain of the bettor at the n th trial, where Yn represents the bet size, gn ( Xn ) is determined by the gambling rules, and { Yn , n ≥ 0} is called a gambling system or a random selection system. The bettor’s strategy is to determine { Yn , n ≥ 1} by the results of the previous trials. Let the entrance fee that the bettor pays at the n th trial be bn . Also suppose that bn depends on Y n−1 as n ≥ 1, and b 0 is a constant. Thus
PPT Slide
Lager Image
represents the total gain in the first n trials,
PPT Slide
Lager Image
the accumulated entrance fees, and
PPT Slide
Lager Image
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
PPT Slide
Lager Image
, the accumulated net gain in the first n trial is to be of smaller order of ma gn itude than the accumulated stake
PPT Slide
Lager Image
as n tends to infinity, that is
PPT Slide
Lager Image
Definition 4. Let { Xt , t T } be an arbitrary random field defined by (1), and { pt , t T } be a sequence of positive real numbers, pt ∈ (0, 1). We set
PPT Slide
Lager Image
PPT Slide
Lager Image
for the likelihood ratio and the logarithmic likelihood ratio of { Xt , t T }, relative to the product binomial distribution.
PPT Slide
Lager Image
where log is natural logarithm. ω is the sample point. Let
PPT Slide
Lager Image
Then it will be shown in (31) that r ( ω ) ≤ 0 a.s. in any case. Hence, rn ( ω ) 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
PPT Slide
Lager Image
. Roughly speaking, this deviation may be regarded as the one between X T(n) and the independent case. The smaller rn ( ω ) is, the smaller the deviation is.
There have been some works on limit theorems for tree-indexed stochastic processes. Benjamin i and Peres have given the notion of the tree-indexed homogeneous Markov chains and studied the recurrence and ray-recurrence for them (see [1] ).Liu and Ma have studied strong limit theorem for the average of ternary functions of Markov chains in bi-infinite random environments. (see [2] ). Yang proved some strong laws of large numbers for asymptotic even-odd 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 PPG-invariant 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 Shannon-McMillan 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
PPT Slide
Lager Image
then
PPT Slide
Lager Image
In particular, if σn = | T (n) | , we have
PPT Slide
Lager Image
Proof . See reference [15] . □
Theorem 1. Let X = { Xt , 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
PPT Slide
Lager Image
Denote α > 1, β > 0, 0 ≤ c < ( α − 1) 2 αbbN , then
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof . Consider the probability space (Ω, F , μ ), let λ be an arbitrary real number, δi ( j ) be Kronecker function. We construct the following product distribution.
PPT Slide
Lager Image
By (12) we can write
PPT Slide
Lager Image
Therefore, we know μQ ( x T(n) , λ ), n ≥ 0 are a family of consistent distribution functions defined on S T(n) . Denote
PPT Slide
Lager Image
By (4) and (12), we can rewrite (14) as
PPT Slide
Lager Image
Since μ and μQ are two probability measures, it is easy to see that { Un ( λ , ω ), Fn , n ≥ 1} is a nonnegative martingale according to Doob’s martingale convergence theorem(see [12] ). Hence, we have
PPT Slide
Lager Image
By the first inequality of (9), Lemma 1 and (14), we can write
PPT Slide
Lager Image
According to (5) and (15), we can rewrite (17) as
PPT Slide
Lager Image
By the limit property of superior limit, we can obtain by the second inequality of (9) and (18) that
PPT Slide
Lager Image
Letting λ ∈ (1, α ) and dividing both sides of (19) by ln λ , we have
PPT Slide
Lager Image
According to the property of superior limit
PPT Slide
Lager Image
By (20) and the inequality
PPT Slide
Lager Image
noticing that 0 ≤ Yt b , t T , we can writ
PPT Slide
Lager Image
It is easy to show that in the case 0 < c < ( α − 1) 2 αbbN , the function
PPT Slide
Lager Image
attains its smallest value
PPT Slide
Lager Image
. Hence by (21), we have
PPT Slide
Lager Image
In the case c = 0, we choose λi ∈ (1, α )( i = 1, 2,⋯ ) such that λi → 1 + (as i → ∞), by (21) we have
PPT Slide
Lager Image
It implies that (22) is also valid when c = 0.
Letting λ
PPT Slide
Lager Image
, dividing both sides of (19) by ln λ , we get
PPT Slide
Lager Image
In virtue of the property of inferior limit,
PPT Slide
Lager Image
By (24) and inequality 1 − 1/ x ≤ ln x x − 1, ( x > 0) , we can write
PPT Slide
Lager Image
When 0 < c < ( α − 1) 2 αbbN , we can get the function
PPT Slide
Lager Image
attains its smallest value
PPT Slide
Lager Image
. Hence, it can follows from (25) that
PPT Slide
Lager Image
In the case c = 0, we select λi
PPT Slide
Lager Image
( i = 1, 2,⋯ ) such that λi → 1 (as i → ∞), by (25) we attain
PPT Slide
Lager Image
It means that (26) also holds in the case c = 0. □
Corollary 1. Under the assumption of Theorem 1, we have
PPT Slide
Lager Image
Proof . Letting c = 0 in Theorem 1, (28) follows from (10), (11) immediately. □
Corollary 2. Let X = { Xt , 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
PPT Slide
Lager Image
where D ( ω ) is defined as (30) .
Proof . At the moment, we know that μP μ . Therefore, we obtain rn ( ω ) ≡ 0, D (0) = D ( ω ). (29) follows from (28) immediately. □
Corollary 3. Let X = { Xt , t T } be an arbitrary random field indexed by an infinite tree. rn ( ω ) is defined by (5). Denote β > 0,
PPT Slide
Lager Image
Then
PPT Slide
Lager Image
Proof . Letting λ = 1 in (17), we get by (18)
PPT Slide
Lager Image
(31) follows from (32) immediately. □
Corollary 4. Under the assumption of Theorem 1, we have
PPT Slide
Lager Image
Proof . Letting c = 0 in Theorem 1, we obtain
PPT Slide
Lager Image
(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, { Xt , t T } be a collection of S −valued random variables defined on the measurable space {Ω, F }. Let
PPT Slide
Lager Image
be a distribution on S , and
PPT Slide
Lager Image
be a strictly positive stochastic matrix on S 2 . If for any vertices t , τ ,
PPT Slide
Lager Image
{ Xt , 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
PPT Slide
Lager Image
PPT Slide
Lager Image
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 = { Xt , t T } be a Markov chain field indexed by an infinite tree with the initial distribution (36) and the joint distribution (37). Denote Yt ∈ [ a , b ], ( a > 0) t T. If
PPT Slide
Lager Image
Then
PPT Slide
Lager Image
PPT Slide
Lager Image
Proof . Let μ = μQ , by (4), (5) and (38) we can write
PPT Slide
Lager Image
Hence, we obtain by (41)
PPT Slide
Lager Image
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.
e-mail: 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, Zhen-jiang 212003, China.
e-mail: wkk.cn@126.com
References
Benjammini I. , Peres Y. (1994) Markov chains indexed by trees Ann. Probab. 22 219 - 243    DOI : 10.1214/aop/1176988857
Liu W. , Ma C. , Li Y. , Wang S. (2015) A strong limit theorem for the average of ternary functions of Markov chains in bi-infinite random environments Statist. Probab. Letts. 100 12 - 18    DOI : 10.1016/j.spl.2015.01.029
Liu W. , Yang W. (2004) Some strong limit theorems for Markov chain fields on trees Probab. Eng. Inform. Sci. 18 411 - 422    DOI : 10.1017/S0269964804183083
Liu W. , Yang W. (1996) An extension of Shannon-McMillan theorem and some limit properties for nonhomogeneous Markov chains Stochastic Process. Appl. 61 129 - 145    DOI : 10.1016/0304-4149(95)00068-2
Yang W. , Zhao Y. , Pan H. (2014) Strong laws of large numbers for asymptotic even-odd Markov chains indexed by a homogeneous tree J. Math. Anal. Appl. 410 179 - 189    DOI : 10.1016/j.jmaa.2013.08.009
Li R. , Yang W. (2008) Strong convergence of pairwise NQD random sequences J. Math. Anal. Appl. 15 741 - 747    DOI : 10.1016/j.jmaa.2008.02.053
Yang W. (2003) Some limit properties for Markov chains indexed by a homogeneous tree Statist. Probab. Letts. 65 241 - 250    DOI : 10.1016/j.spl.2003.04.001
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 Shannon-McMillan 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