论文部分内容阅读
随机游动理论是随机过程理论的重要研究方向之一,应用非常广泛,它也是其他很多数学分支的重要基础.关于图上随机游动特别是网络上随机游动的研究是现代概率论的热门研究课题,在国内外研究都较为活跃.本文的主要工作是研究树上随机游动的相关问题,特别是基于前人的研究基础上对树上随机游动的平均首中时进行了新探究和拓展.全文共分为五章. 第一章为绪论部分.主要分五块内容,首先对随机过程理论(特别是随机游动理论和马尔可夫链理论)的一些基本定义和概念以及符号进行了梳理和讨论,重点强调了图上随机游动与马尔可夫链的相互关系及经典结论,同时介绍了图上随机游动研究的经典研究方法,特别是电网络在无向图上的随机游动中的应用与结论. 第二章主要探讨了图上随机游动平均首次通过时与平均首中时之间的区别与联系,运用矩阵分析法给出两者的计算表达式及矩阵表达式,还研究了与平均首中时相关的其他参数(如:差时间、往返时间等)给出了几个比较有用的计算定理,同时给出了树上随机游动平均首中时计算表达式及得出了平均首次通过时的方差为整数这一结论. 第三章首先给出图上随机游动平均首次通过时的逆问题与逆M矩阵的联系,给出相应的经典结论;其次利用矩阵分析法和Sherman-Morrison公式首次探讨了树上随机游动平均首中时的逆问题与逆H矩阵的联系,给出了树上随机游动平均首中时矩阵H的逆矩阵求算表达式. 第四章主要探讨了树上随机游动的覆盖时间成本和反向覆盖时间成本的区别与联系,给出两者在树上随机游动的计算表达式和结论,并在加权图上对这两个变量进行了推广,还探讨了树上随机游动平均首中时、覆盖时间成本与反向覆盖时间成本三者的范围,并给出取到相应上下界的极限情况. 第五章总结了全文的内容,并对下一步的研究工作做了展望.