足球比分直播

图上的随机游动问题.pdf

返回
图上的随机游动问题.pdf_第1页
第1页 / 共37页
图上的随机游动问题.pdf_第2页
第2页 / 共37页
图上的随机游动问题.pdf_第3页
第3页 / 共37页
图上的随机游动问题.pdf_第4页
第4页 / 共37页
图上的随机游动问题.pdf_第5页
第5页 / 共37页
点击查看更多>>
资源描述:
;塑釜圭堂态翌壅圭堂簦燕塞 iiKey wordsrandom environment;Random walk;Markov chain;Recurrenceexpected hitting time.原创性声明本人声明;所呈交的论文是本人搬导师的指导下进行的研究工作.除了文中特弱翻戮椽注季羁致瓣的鳃方辨,论文牵不包含萁毽入穗发表或撰写道酶雾}究残聚,参与同~工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示丁谢意.签名日期 年 月 日本论文使用授权说明零人完全了解上海大学有关保留,使用学位论文驹规定,邵;学校有权保留论文及送交论文复印件;允许论文被畿阅和借阅;学校可以公布论文的全部或部分内容,保密的论文谯解密后应遵港此觏定签名;, 7日瓤沙6年导灏签名月7垆日荔岛旷飞力甜呵2006年上海大学硕士学位论文第一章 绪论随机游动作为随机过程的一个重要分支一直受到人们的关注,随机游动问题由于其重要的理论价值和应用前景一直是概率论中研究的热点问题.随机游动是研究图论、组合论、随机算法以及生物、经济等问题的重要工具.经典的随机游动理论产生于简单的数学和物理模型中,经典的随机游动即简单随机游动可以视为独立同分布随机变量的部分和序列,简单随机游动即为一齐次马氏链.因此,我们可以借助马氏链的理论和方法来研究随机游动问题,反之,随机游动也可以用来研究马氏链的性质.近年来,随着随机游动理论的发展和实际问题的需要,产生了各种模型上的随机游动问题.随机游动理论同概率论的其它分支,以及随机游动同图论、群论和统计物理等学科的交叉。产生了一些新的更复杂的随机游动问题.借助于其它学科和方向中的理论和方法,我们可以用随机游动来研究各种实际问题,如生物模型中的DNA序列排序问题,经济中股票的走势等.随机游动理论同其它学科的交叉也使得随机游动成为研究其它学科中自身理论问胚的有力工具.例如,我们可以借助随机游动来设计随机算法,以提高算法的有效性和收敛速度等.可以借助随机游动来对样本进行随机抽样,提高统计结果的精度.在研究随机游动的性质时,特别是利用随机游动来研究实际问题时,许多情况下需要考虑随机的因素,如粒子的波动,人口模型的种族繁衍等,必须考虑外在环境的影响.一般说来,环境的变化不是没有规律的,而是遵循一定的概率分布,这就是所谓的随机环境.随机环境的引入使得随机环境中的随机游动能够更好地反映现实中的问题,随机环境中的随机游动自身也产生了一些新的理论问题,随机环境的引入使得随机环境中的随机游动成为概率论中的热点问题.对于随机环境中的随机游动,Zeitouni还在ICM2002上作了精彩的报告f321直线上随机环境中的随机游动最早由Solomon提出[27】,在这篇原始文献塑璺鱼生上浚鑫堂亟圭芏照鲶塞 羔孛,傺移营次gl入了Z1上RWRE懿壤念,著秘謦费达嚣于分解戆方法,遥遘掰宠到达时的性状而得到游动本身的规律,重点讨论了环境独立同分布时的常返暂留的充要条件和遍历理论.毕秋香等[3l讨论了在0点具有反射壁的右半直线上陡褪嚣j爨中缱税游甏秘露返毪,透嚣磷究了箕歪常遨豫秘毂聚整菝。秘彝东、载隶激等『221研究了独立I司分布随机环境下,半直线上随机环境中可逋留的随机游动,得出了常返性准则,并通过构造Lyapuaov函数和利用鞅理论,得出了随机游动的一个黧对数律霸一个岛牧馥薛结祭。Kalicow[17】将RWRE黎广至犁孛,蠢予空问维数的扩大,即使对首重时分解的方法加以修正,得到的部分遍历性结果通不如一维情形完美.援攀论霹群沦鹣交叉产生了群羔豹溉事沦,群上戆概率论荧心翡是这弹一樊概率测度和随机过程它们所蕴含着的群的结构部分的决定了它们的性质.人们发现无涂是复杂的理论还屉具体问题的分析,群上的概率论都是一个变化多端的镢蠛群上的随机游动瑚论作为群上的概率论的一个熏要研究方向,最早可以追溯到洗牌游戏。由于其对研究群的结构以及在代数、分析、几何上的黧要应用引起人匍蘸广泛关注。翻熬,一拿綮流行麴万有覆盖上鹃Laplace方稷懿蒸扩散方赣戆解的性质与基本群上的随机游动的行为有关.群上的随机游动自身基本行为的分析也魑一个重要的研究领域.随机游动的应用非常广泛,这也赵我们要研究群上蘧辊游动静一个主要藤嚣.爨翔,大多数戆往薄方浚都可疆看成对称群n52上的随机游动模型,即把洗牌看成谯一系列置换中随机地选取一种.当髓帆游动有更多的对称性时,例如,对称群群表示论可蚪帮助我们更好的醑究麓槐游交,研究一个夫秘有隈群上曲夔撬游凌丐馥看俸磁囊尼令夫懿矩黪,即随机游动的概率转移阵.群表示论通过矩阵的偏对角化可以使问题得以简化.例如,对称群&,开始时是n越阶短阵,根据不可约表示论,农崩溃后矩阵的最夫敦为√nl西l狯。对有限群上的睫瓿游动撩剐燕在,l、集合豹生残元上定义2006年上海大学硕士学位论文 3的随机游动还有许多问题有待进一步的研究.1958年,Kosten在他的博士论文一一由Kac的一个关于22随机矩阵的乘积的问题所引起的一一建立了有限生成群上的随机游动这一课题.对任意有限生成群上的随机游动,另≯n代表随机游动2n步后返回到起始点的概率,则随机游动翌I论中咖n的极限性质,以及它同有限生成群的结构的关系是有限生成群上随机游动理论中研究的基本问题.同一般图上随机游动研究的内容有许多相似的地方,对有限群生成的有限图上随机游动问题也包括首达时间hitting timel、返回时问commute time、以及f昆合时间mixing time的研究.对有限群生成的图上的随机游动问题首达时问的研究是对群上随机游动理论自身性质的研究.David Gluck对首达时问的分布函数进行了研究11 3,得出了有限群生成的图上随机游动首次到达群的单位元的首达时问的分布是指数型的.M.Kang对单割点有限群生成的有限图上的随机游动进行了研究『181,得出了首达时问的概率母函数的解析表达式,进而得出了平均首达时间的解析表达式.在前人工作的基础之上,我们的主要工作可以分为以下几章第一章,也就是绪论部分,主要介绍研究课题的背景、特点、历史发展和本文的主要结构.第二章,主要是一些预备知识,介绍了随机游动和随机环境的基本知识,以及所要用到的图论和群表示论的知识.笫三章,主要是对半直线上随机环境中可逗留随机游动的研究.直线可以视为~种简单的图,我们主要研究了在独立但不同分布环境下,半直线上随机环境中可逗留的随机游动的常返性和非常返性,给出了一个常返性的判别准则.进一步研究了常返性中的正常返和零常返。给出了正常返和零常返的充要条件.第四章,是对由有限群生成的图上的随机游动问题的研究.我们研究了一类由有限群生成的多割点有限图上的随机游动问题,我们利用概率论、群表示论、图论中的理论和方法,得出了由有限群生成的多割点有限图上随机游动的首达时塑生』鲞盘堂塑±堂焦监塞 间的概率母函数的明确表达式。进而得出其r甲.均首达时间的解析表达式,推广了前人研究的Fh有限群生成的单割点有限图上的随机游动问题的结果.第五章,是本文的总结和未来的研究展望.2006年上海大学硕士学位论文 5第二章预备知识本章主要介绍马氏链、随机游动和随机环境的基本知识,以及所要用到的图论和群论的知识.本章主要参考了[51112][15][19][21】【301§2.1马尔科夫链定义2.1.1称定义在概率空问n,,,P上的随机序列XO,zl,-为离散时间的马尔可夫链,如果它满足下列二条件1{‰,n0,1,的状态空间E为可列集;2对任意的n及状态io,i z,,i,州,只要Pxoin,X1i1,,X。i。0,就有JJ∞卜}l2。ll跏io,。Iiz,·..,z。i。P4件lin1I。。i。条件2称为马尔可夫性或无后效性,它是马氏链的特性定义2.1.2马氏链X‰,n≥0称为齐次的,如果对任意的m和n及任意状态i和J,只要.Pz。i0,Pz。i0,就有尸{2。1jlx。母P{x。l引z。班在齐次的情形,记Pipx。IJ Jz。i,并称%为马氏链的转移概率,由Pij;i,j∈E为元素所成的矩阵PPlj称为马氏链的转移矩阵.转移概率时齐次马氏链最重要的特征量.定义2.1.3设齐次马氏链{。。的转移概率矩阵为扫Ⅱ,称p’P{xn1JlXoi’为n步转移概率,臂。1P{z。,,。k≠J,k1,2,.一,n一1Izot生』塑盔堂亟圭堂焦堡塞 为从状态i出发,经过n步首次到达状态J的概率.定义2.1.41如果局1,则称J为常返的,南0的最大公约数为d,通常把d1称为周期的,dl成为非周期的.4非周期的正常返的状态称为遍历状态,相应的,不可约非周期正常返的马氏链称为遍历链.定义2.1.7随机过程X{x£,T≥o称为是可逆的,如果对所有的tl,t2,t,r∈T,其中T是指标记。 xt1,x如,,xt。和XTt1,xr一£z,,xp一㈦具有相同的分布.具体一点的定义就是定义2.1.8过程Xxt,T≥o称为是可逆的,如果对于任意的0≤tl0为一以为状态空问,其转移慨率为有由下式决定的随机变量序列只X州ⅣI%z%yz我们用,苫表示仅“,9上分布律,它满足巧Xoz1,其中9是由全体柱集{f对所有i∈D,置xi]D∈D,%∈x其中口表示N的非空有限子集全体所产生的一一代数.易知对任何G∈岱,。∈x,映射uJF苫G足,一可测的,因此我们可以在Qx”,,g上定义概率测度pPo圪,它由下式扩张而成,ⅡMFG/,孑GP反J F∈,,G∈g.JF令蟛。上。圪Pdw为俨在[“上的边际分布,则在分布律P‰下,RWREX并不一定是马氏链i为方便起见,以下在没有混淆的情况下,我们也用p表示畔。§2.3图论中的基本概念本文所讨论的图均是无孤立点、无环无多重边的有限简单图.凡是文中未加定义的术语和符号,可参看文献[5].为了叙述方便,我们首先引入一些定义和记号.设GKE是简单图,yG,EG分别表示图G的顶点集和边集,G鳗垒占堡盔芏塑±堂焦堡塞 的点的数日nIyGi称为图G的阶数.如果图Ⅳ满足条件VH∈VO和E日垦EG,则称H为图G的一个子图对s∈yG,用cis]表示由s导出的子图.图G中点z的开邻域定义为Ⅳ。,G{ⅣI xy∈EG,z的闭邻域为N[x,G】Nx,Gu{z更一般地,对任意的x∈yG,我们定义NX,Gu∈xNx,G,NIX,qNX,GU X在不引起混淆的情况下,上述符号可分别简记为Ⅳz,ⅣH,NX和ⅣⅨ】.我们称dxI.vzI为点。的度数,度数为1和0的点分别被称为图的悬挂点和孤立点.特别地,树中的悬挂点也叫叶子.分别用dG和AG表示图G的最小度和最大度.图G中度为奇数和偶数的点分别称为奇度点和偶度点.所有顶点的度都等于k的图G称为k.正则图.在图G中如果两个不同的顶点在G中是不邻接的,则称它们是独立的.如果点集s∈VC中所有点都是相互独立的,则称S是G的独立集.由n个顶点构成的路和圈一般记作R和Ck.若图G中的任意两个相异点之间都有边相连,则称G为完全卧I“/个顶点的完全图记作%.用GM,%,,KiE表示顶点集是u坠1Ⅵ,边集足{xy∈EGl z∈K,Y∈K,l≤iJ≤k的≈一部图.特别地,当≈2时,G称为二部图,若IⅥIm,Iv2In,且Ⅵ的每个顶点都与K的每个顶点相连。则称此二部图为完全二部图,记作正~§2.4群表示论中的基本概念令扩为复数域C上的d维向量空问,令GLV为秩为d的线性可逆空间的集合,它表示V到V的线性可逆映射.P称为G的线性表示,如果PGGLV是一个连续映射,并且满足pxyPzp∥,对任意的X,Y∈G显然,pe即为单位矩阵,并且有pz“p。~V的维数就称为P的维数,记作dp.如果对所有的z∈G,有p≈1,则称线性P表示是平凡的.对任意的。∈G,如果没
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播