贪婪格点路径的一些性质.pdfVIP

高校应用数学学报A辑 Appl.Math.J.ChineseUniv.Ser.A 2006，21(2):174-182 贪婪格点路径的一些性质 何建军，沈 鸿 (中国计量学院数学系，浙江杭州310034) 摘 要:设 {X:vEZd}是一族独立同分布的随机变量序列，对Zd上的任意一 路径兀，定义S(r)一EX,，记M一m ax S(二),17,(n )表示从原点出发大小为n的 wEnocn 自不相交的路径的全体.论文讨论Mn的性质，得到了类似完全收敛性的结果，即对 从 __}_ )- -，-‘、·-·一-，，，，--一”’‘ 任意”·0,}nP丁一州夕￡).j99rit-T7*JAvXitJPXIQItFT 形，得到类似的结果，从而推广了Gandolfi和Kesten所研究的贪婪格点路径 模型. 关键词:贪婪格点路径;线性增长;完全收敛性 中图分类号:0211.4 文献标识码:A 文章编号:1000-4424(2006)02-0174-09 1 引言和主要结果 设d1,Zd为d维整数格点图，对任意两点v=(v(1),v(2)9...,v(d)),W=(wcll,w2..., W(d))，它们的欧氏距离为1，称它们是相邻的，用一条边。=(v,w)表示，Z“上大小为n的自 不相交的路径二定义为点边相间的序列{(vi,el,v2,e2,...,e。一，,v.) ，每边e*的端点恰为v*一，， vk，即。k=(vk_i,vk)，且vi,v2,...,v。全不相同，记二二(v。，vl，v:，…，v、一1)，二所含的顶点的个 = m ax 数记为}川,no(n)表示从原点出发大小为n的自不相交的路径的全体，11v11 {vu)}. 1丈 i n 假设{Xv.vEZd}为一族独立同分布的随机变量，任给一条路径二，记S(7r)一艺Xv, 本文主要研究Mn=maxS(7r)的渐近大小.X。可直观地解释为位于某点v处的食物重量， aEHo(n) 这样一条路径上的食物总重量为S(7)，而从 则是从原点出发行走n步所能获取最大可能 的食物量，该模型首先由Cox等[〕提‘出，并称为贪婪格点路径模型.Gandolfi,KestenEZ1, Demb。等[[3]进一步研究了该模型，并在PERT网络和P--渗流模型领域有着广泛的应用.下 收稿日期:2005-04-18 何建军等:贪婪格点路径的一些性质 175 面的结果表明在一定的矩条件下，Mn随着n的增加而线性增长. 定理A12]设{X,,vEZd}是一族独立同分布的随机变量阵列，如果X__0，存在aO, 使得EXd0((1，0。9g,Xx·。)d+a一则存在常数、ER，使得二{等一、，…· 当d=1时，上述定理为强大数律结果，并且M=EXo，对于d2情形，由于M二所包含 的路径个数随着n指数增加，从而M.渐近性质的研究变得相当复杂.一个容易的讨论表明 M严格大于EX,(，即MEX,，既然从 是线性增长的，一个自然的问题是Mn的增长速度如 _ 、，二_.__， _____.__ _日M __}_ 、、，、______，__ 何?为此对任意的‘。，考虑尾概率尸}}n州)‘，并证明了下列定理· 定理1 设{X,,:VEZd}是一族独立同分布的随机变量阵列，如果Xv0，存在a0，使 得E{Xd(log+Xo)d+a}00，则对任意的:0，有 叠_n1P(】Mnn一“一)6}一