广义Bethe 树上关于随机选择系统的一类极限定理.pdf

http:/ 广义广义Bethe 树上关于随机选择系统的一类极限定理树上关于随机选择系统的一类极限定理1 陈鹏飞2，魏杰1，李兵21南开大学信息技术科学学院,（300071）2军事交通学院基础部,（300161）1 E-mail（）摘摘 要：要：本文将随机选择系统的概念在广义 Bethe 树上进行了推广,同时研究了广义 Bethe树上选择子序列的状态序偶出现频率的一类极限定理,它是 Bernoulli 序列无规则性概念的进一步推广。关键词：关键词：随机选择系统,广义 Bethe 树,极限定理。1.引引 言言 近随机选择系统(有时称为赌博系统函数)的概念源于赌博(参见1)。考虑一个普通的掷硬币的赌博，其中赌徒按照某种依赖于以前的投掷结果的规则选定赌金。逐次的赌金不再是独立的随机变量了，但赌博仍然是绝对公平的，公平的思想是，过去的知识不能使赌徒改善他的运气，即其成功的概率不变。自 Von Mises 以来，不少作者对这一问题进行了研究(参见2-4)。本文的目的是将随机选择系统的概念推广到广义Bethe树上，研究广义Bethe树上选择子序列的状态序偶出现频率的一类极限定理。首先简单介绍一下与本文相关的树的概念和记号。设是一个无限树,是中任两个顶点，则存在唯一的从到的路径，其中互不相同，且与为相邻两顶点，称为 到的距离。为给T中的顶点编号，我们选定一个顶点作为根顶点（简称根）,并记之为 O。如果一个顶点与根顶点的距离为n,则称此顶点为第n层上的顶点。为统一起见，根顶点也称为位于第层上的顶点。Tyx Txyyzzzxm=,21Lmzzz,21Liz1+iz1mxy0定义定义 1 设是一个具有根顶点 O 的无限树，是一列正整数。如果第层上的每个顶点均与第层上的个顶点相邻，则称T为广义 Bethe 树或广义Cayley 树。T1,nNnn0n1+n1+nN设是正整数。如果N11+=NN且对所有的NNnn=,2，则称T为 Bethe 树，记为；如果对所有的)1(2,所示如图BNBTTNNnn=,1则称T是 Cayley 树，记为。以下T恒表示广义 Bethe 树或广义 Cayley 树，NCT,)(nT 表示含有从第0层(根顶点)到第层n -1-http:/ 的所有顶点的子图。设表示|BT的子图B的顶点数，并令10=N，则=nknnNNT00L)(|（1）用表示第层上的第个顶点,为统一起见,也记根顶点 O 为。)1,1(),(1nNNjjnnLnj)1,0(设b是正整数,，其中=)(,2,1TSbSL)(是定义在T上在 中取值的函数,是Sh的所有有限维柱子集产生的最小代数,是可测空间(上的概率测度。是定义在),h,TtXXt=),(h上的坐标随机过程,即对任何=)(，定义 TttXt=),()(（2）记 若B是T的有限连通子集，定义B上的一个简单序,1kxxBL=满足如下性质，记为：对每一个有唯一的一个(*)Bxjxjj),1(,11jixxxL是其相邻顶点，记为，考虑)(jii=TB=的序(此序满足性质)。与该序相对应的，状态空间为的随机变量),(),1,(,),1(,),1,1(),1,0(11LLLLLnNNnnN(*)S,TtXt的序为 下面我们直接利用柱集的分布给出树$T$上的马氏链场的一种定义,它是马氏链场古典定义-2-http:/ 的自然推广。定义 2定义 2 设是上严格为正的随机矩阵,),(jipP=S)(,),1(bqqqL=,是上的严格为正的分布,SP是上的概率测度。如果),(h （3）（4）则称P为随机矩阵及分布q决定的树上的马氏链场。),(jipP=T注 1 注 1 由(3)与(4)定义的P也依赖于q，在 Spitzer 及 Berger 与叶中行 给出的定义中被取为由决定的平稳分布q),(jipP=)(,),1(bL=故此处的定义稍有推广。注 2注 2 设对所有的，并记为则由(3)与(4)有,1,0=nNn)1,(nn （5）这就是马氏链柱集的分布。定义 3定义 3 给定定义在上且在中取值的函数列 TS1,0 ),3,2,2,1(),(,111,1,0,1,0mtmtmNNtmXXfffLLLL=，)1,1,0(),(11,1,01,1+=+mtmmNNtmXXffLLL 称为树,2,1,1,01,ijiNNjnifLLL=T上的随机选择系统。根据的值来选取序列,2,1,1,01,ijiNNjnifLLL=（6）和序列),(,),(,),(,),(1111,11,1,1,11,01,11,0nnNNnNNnnnNXXXXXXXXLLLLL（7）的 子 序 列:当 且 仅 当1,=jif时,取(6)中 的和(7)中 的 jiX,),(,),(11,1,1)1(,1,+iijNijiNjijiXXXXL这样选出的序列分别称为(6)和(7)的被选取子序列。设)(),(,klkSlknn分别表示(7)的被选取子序列中状态序偶和出现的次数,易知),(lk),(k （8）（9）-3-http:/ 其中)(k是上的 KroneckerS函数。引理引理 设1与2是可测空间上的两个概率测度,),(hhD，1,nn是一列正值随机变量使得 （10）则 （11）特别地,如果取，则有|)(nnT=（12）证明证明 设，易知)(/)()()(12nnTTnXXZ=1)(1nZE，其中表示关于1)(1nZE1的数学期望.由 Markov 不等式有 （13）因为0是任意的,故根据 Borel-Cantelli 引理由(13)知(12)成立,显然(10)与(12)蕴含(11).以下恒假定P是由随机矩阵及分布q决定的树上的马氏链场.),(jipP=T定理定理 设,TtXXt=是具有分布P的马氏链场,)(),(klknn分别由(8),(9)所定义,令 )(lim:)(+=kkDnn，（14）)(.,0|)(inflim)(kDsaTkPnnn于，（15）)(.),()(),(limkDsalkpklkPnnn于=，（16）证明证明 为以下证明的需要,构造另一转移概率矩阵如下 SyxyxrR=,),()(设0是一给定的实数,固定Slk,。(1)当,且时,令 1,=jifkXji=,),()1(1),(),(Slklkplkplkr+=（17）-4-http:/ ,),()1(1),(),(ltlkplkptkr+=（18）(2)当,且时,令 0,=jifkXji,),(),(Syxyxpyxr=（19）把由选择函数所得到的序列(6)的子序列记为 jif,（20）其中则对应的(7)的被选子序列记为)(,),(,njiijjiTjiXfY=（21）显然(20)式中的序也满足性质,假定(*)R是由随机矩阵SyxyxrR=,),()(及分布决定的树qT上的马氏链场.于是由(17)-(19),(4),(8),(9)得 （22）利用(15)式,引理和(22)式,得 （23）利用(23)和上极限性质,得 （24）当1时,(24)式两边同除以ln得 （25）令,利用不等式+1)0()1ln()1/(+xxxxx,得),(ln/),()1(1lnlkplkp+，再由(25)式,得 （26）当10时,(24)式两边同除以ln由上极限的性质,得 （27）-5-http:/ 令 利用不等式1)01()1ln()1/(+xxxxx得),(ln/),()1(1lnlkplkp+再由(27)式,得 （28）由(26),(28)得(16)。定理证毕 注 3注 3 定理在几乎处处收敛意义下给出了树上马氏链场转移概率的一种频率解释，且考虑的频率)(/),(klknn是相对随机选择系统所确定的任意子列而言的，故定理结果比已知结果参见5更为深刻。注 4注 4 当L,2,1,2=mNm时，即T是有根 Cayley 树，定理结果即是二元树上的无规则性定理(参见6)。推论 推论 设),(,lkSSlkn和),(kSn分别是随机变量序偶 中状态序偶和的个数,即),(lk),(k （29）（30）在定理条件下 （31）证明证明 对，取)(),(nTji1),(jif推论即得证。参考文献参考文献 1 Billingsley P.Probability and Measure，New York，Wiley，1986。2 KolmogorovA.N.On logical foundation of probability theory，Lecture Notes in Mathematics，1021 1982。3 Liu Wen，Wang Zhongzhi.An extension of a theorem on gambling syatem.J.Multivarite Ayalysis,55 No.1,125132 1995 4 刘文,王金亭，关于赌博策略的一个强极限定理的推广，应用概率统计，15 No.3，302309，1999 5 刘文，关于可列齐次马氏链转移概率的强大数定律，数学学报，21 No.3，231242；1978。6 赵静，魏杰，二元树上的无规则性定理，河北工业大学学报，32 No.4，103107，2003。The Extention of Random Selection System on Extended Bethe Tree and a Class of Limit Theorems -6-http:/ Wei jie College of Information Technology and Sciences,Nankai University,Tianjin 300071 Chen peng-fei,Li bing Department of Basic Sciences,Military Traffic Institute,Tianjin 300161 Abstract In this paper,the author extend the notion of random selection system on the extended Bethe tree and give a class of limit theorems on frequencies of occurrence of ordered couples of states of selection subsequencies on the extended Bethe tree.It is an extension of the concept on the irregularity of Bernoulli sequence.Keywords:Random selection system,Extended Bethe tree,Limit theorems.-7-