（概率论与数理统计专业论文）随机网络最短路径的概率分布.pdf

摘要 本文研究了随机网络的最短路径问题，给出了一种基于马尔可夫骨 架过程理论的最短路径算法。作为网络分析中的一个经典问题，随机网 络最短路径问题引起了许多学者的兴趣，提出了一些算法，用以求解随 机网络最短路径长度的概率分布。但这些算法都对随机网络弧长的分布 加以限制，如要求其为连续分布或假定其为负指数分布等。当弧长的分 布不满足这些条件时，这些算法就不再有效了，因此有必要对弧长服从 一般分布的随机网络最短路径问题进行研究，给出其最短路径算法，这 正是本文要解决的问题。本文假设网络弧长为服从一般分布的随机变量， 利用马尔可夫骨架过程理论求解网络最短路径长度的概率分布。文中构 造了一个马尔可夫骨架过程，使得从该骨架过程的初始状态首次转移到 吸收状态的时间正好等于随机网络最短路径的长度，从而可以利用向后 方程求解网络最短路径长度的概率分布。 本文第一章介绍了问题的历史背景及研究现状。第二章介绍了马尔 可夫骨架过程的定义和一些基本性质。第三章构造马尔可夫骨架过程， 并给出其状态集。第四部分给出最短路径算法。第五部分给出两个具体 的例子。 关键词：随机网络，最短路径，马尔可夫骨架过程，向后方程 a b s t r a c t t h i sp a p e ri n v e s t i g a t e st h es h o r t e s tp a t hp r o b l e mo fs t o c h a s t i cn e t w o r k s a n dd e v e l o p san e wa l g o r i t h mb a s e do nm a r k o vs k e l e t o np r o c e s s e st oo b t a i n t h ed i s t r i b u t i o nf u n c t i o no ft h es h o r t e s tp a t h a so n eo fc l a s s i c a li s s u e si n s t o c h a s t i cn e t w o r ka n a l y s i s ，t h es h o r t e s tp a t hp r o b l e mh a sm o t i v a t e dm a n y r e s e a r c h e r st od e v e l o pm e t h o d st oc o m p u t et h ed i s t r i b u t i o no ft h el e n g t ho f s h o r t e s tp a t h b u tt h e s em e t h o d sh a v ep u tr e s t r i c t i o n so nt h ed i s t r i b u t i o n f u n c t i o n so ft h ea r cl e n g t h ( f o re x a m p l e , a s s u m et h a tt h ea r cl e n g t h sa r e c o n t i n u o u s l yo re x p o n e n t i a l l yd i s t r i b u t e dr a n d o mv a r i a b l e s ) w h e nt h e d i s t r i b u t i o nf u n c t i o n so fa r cl e n g t hd o n ts a t i s f yt h o s er e s t r i c t i o n s t h em e t h o d s a r en ol o n g e ra p p l i c a b l e a n dw em u s td os o m er e s e a r c hi n t ot h ec a s et h a tt h e a r cl e n g t h sa r eg e n e m l l yd i s t r i b u t e d t h i sp a p e ru s e st h et h e o r yo fm a r k o v s k e l e t o np r o c e s s e st oc o m p u t et h ed i s t r i b u t i o no ft h el e n g t ho ft h es h o r t e s t p a t hi nas t o c h a s t i cn e t w o r kw i t hg e n e r a l l yd i s t r i b u t e da r cl e n g t h s am a r k o v s k e l e t o np r o c e s si sc o n s t r u c t e df i o mt h eo r i z j n a ln e t w o r k ，a n dt h et i m eu n t i l t h em a r k o vs k e l e t o np r o c e s sg e t sa b s o r b e di nt h ea b s o r b i n gs t a t ef r o mt h e i n i t i a ls t a t ei si u s te q u a lt ot h el e n g t ho ft h es h o r t e s tp a t hi nt h eo r i g i n a l n e t w o r k m o r e o v e r , t h eb a c k w a r de q u a t i o n sc a nb ea p p l i e dt oo b t a i nt h e d i s t r i b u t i o no ft h el e n g t ho ft h es h o r t e rp a t h c h a p t e rli n t r o d u c e st h e d e v e l o p m e n t a lh i s t o r ya n dp r e s e n tc o n d i t i o no ft h es h o r t e s tp r o b l e m c h a p t e r 2i n t r o d u c e st h em a r k o vs k e l e t o np r o c e s sm s p ) ，a n dp r e s e n t si t sd e f i n i t i o n a n ds o m eb a s i cp r o p e r t i e s c h a p t e r3c o n s t r u c t st h em a r k o vs k e l e t o np r o c e s s ， a n dp r e s e n t st h es t a t es p a c eo ft h em s pc h a p t e r4p r e s e n t st h ea l g o r i t h mt o c a l c u l a t et h ed i s t r i b u t i o no ft h el e n g t ho ft h es h o r t e s tp a t h i nc h a p t e r5 t h e m e t h o di si l l u s t r a t e dt h r o u g hs o l v i n gt w oe x a m p l e s k e yw o r d s ：s t o c h a s t i cn e t w o r k s ，s h o r t e s tp a t h ，m a r k o vs k e l e t o n p r o c e s s e s ，b a c k w a r de q u a t i o n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。论文主要是自己的研究所得，除了己注明的地方外， 不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学 或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研 究所作的贡献，已在论文的致谢语中作了说明。 “ 1 o 作者签名：壹赴互日期：2q 垒基午f 月缒日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的 全部或部分内容，可以采用复印、缩印或其他手段保存学位论文；学校 可根据国家或湖南省有关部门的规定，送交学位论文。对以上规定中的 任何一项，本人表示同意，并愿意提供使用。 作者签名：多长玄导师签名：馑主盔整日期：丝鲣年丝月丝日 中南大学硕士学位论文第一章绪论 第一章绪论 1 1 随机网络最短路问题的研究概况 最短路径问题是网络分析中的一个经典问题，它作为许多领域中选择最优问题的 基础，在通信、交通、物流网络分析中有着广泛应用。最短路径问题具体包括以下几 种形式：确定起点的最短路径问题、确定终点的最短路径问题、确定起点和终点的 最短路径问题( 即已知起点和终点，求两结点之间的最短路径) 、单源最短路径问题 ( 找出从某给定的源结点到图中的每个结点的最短路径) 等。用于解决最短路径问题 的算法被称作“最短路径算法”。 1 1 1 问题的背景及研究现状 图l l 令g = ( y ，彳1 表示一个有向非循环网络图( 如图1 - 1 ) ，其中y 和彳分别表示g 中的结点集、弧线集。假定g 只有一个源点( s o u r c en o d e ) ，记为s ，一个汇点( s i n k n o d e ) 记为t 。 令甲表示g 中从结点j 到结点，的所有路径( 即( s ，t ) 路径) 的集合， 痧= # ，p ) ，其中表示g 中第f 条( s ，f ) 路径，厂为( s ，f ) 路径的条数。令三( p ) 表 示p 的长度，则最短( s ，) 路径的长度t = m ，。i 。n ，l ( p , ) 。 当网络图的弧线长度是确定型时，可以利用许多成熟的算法计算其最短路径长 度。最常用的算法有：d i j k s t r a 算法、彳算法、b e l l m a n f o r d 算法、 f lo y d - w a r s h a ll 算法、j o h n s o n 算法等。 但是，在实际应用中，弧线的长度往往为随机变量，此时网络所有b ，) 路径的 长度都为随机变量，要在所有s ，t 1 路径中找到最小的随机变量。理论上这个问题很 简单，但是实际运算中问题就变的棘手了，因为( i ) 矽是一个很大的集合。例如， 对于一个有雅个结点的完全图而言， 例= t ( - 一2 ) ! e 1 ，( i i ) 虽然弧长是相互独立的 随机变量，但( s ，) 路径的长度往往是相关的，因为这些路径可能共用某些弧线( 见文 献 2 0 3 、 3 5 ) 。 中南大学硕士学位论文 第一章绪论 由此可知，当弧长为随机变量时，计算最短路径长度丁的概率分布函数就变得 非常困难了。在随机网络中，计算最短路径长度丁的分布函数的算法被称为“最短路 径算法。 迄今为止，已经有许多学者讨论了随机网络的最短路径问题，研究的主要问题 有：( a ) 最短路长度丁的概率分布；( b ) r 的距估计；( c ) 给定路径为最短路径的概率。 目前求解丁的概率分布的方法主要有以下三类： ( 1 ) 精确的分析计算。要计算丁“真正的”概率分布往往要进行一系列卷积和取 最小( m i n ) 运算，这将会牵涉到繁琐的多变量积分运算，还要处理路径的相关性问题。 这类的方法可以参看文献e 8 3 、 9 、 2 0 、 3 5 、 5 3 。m a r t i n 3 5 利用串并联简 化法求解随机网络最长( s ，f ) 路径长度的概率分布，这种方法也可以用来求解有向非 循环网络最短b ，1 路径长度的分布函数，其中弧长为相互独立的随机变量，且服从 多项式分布。k u l k a r n i 5 3 给出了一种求解最短( s ，) 路径长度丁的概率分饰的分析 算法，用以求解从随机网络从一个给定源点到一个给定汇点的最短路径长度的分布函 数，其中假设各弧长相互独立且均服从负指数分布。k u l k a r n i 构造了一个有限状态， 连续时i 旬马氏链，且是吸收链。使得从该马氏链初始状态转移到吸收状态的时间正好 等于随机网络最短路径的长度。马氏链的状态空间是网络图的所有最小( s ，1 割集的 集合，而生成矩阵是匕三角矩阵。故可以利用马氏链的向后方程求解最短路长度的分 布函数。c o r e a 和k u l k a r n i 2 0 假定弧长是相互独立、取整数值的非负随机变量，构 造了一个离散时间马氏链，给出了求解最短( s ，1 路径长度丁的分布函数的分析算法。 s k p e e r 4 9 等人将这一问题转化为线性规划问题，假定弧长均为服从负指数分布的 随机变量。h a y h u r s t 和s h i e r 3 8 推广了m a r t i n 的方法，简化了运算的复杂度。 s i g a l 8 利用一致有向割集的概念分析有向非循环网络的最短路径。 前面提到的这些方法都对弧长的分布加以限制，如m a r t i n a 5 要求弧长服从多 项式分布，k u lk a r n i 5 3 和s k p e e r 4 9 假定弧长均为服从负指数分布的随机变量。 ( 2 ) m o n t ec a r l o 模拟。 考虑到第一类分析方法计算的复杂性，一些学者利用m o n t ec a r l o 模拟方法估 计丁的分布函数。这类方法模拟随机网络，利用大量的确定型样本推导丁的“接近真 正的”概率分布。可以参看文献 8 、 1 9 中的m o n t ec a r l o 抽样模拟方法。尽管这 种模拟的方法简单且直观，但它得到的并不是真正的概率分布，而且大型的网络将导 致巨大的计算量。 ( 3 ) 逼近法。 从前面的讨论可知，分析计算t 的概率分布非常困难，而m o n t ec a r l o 模拟方 法又要求巨大的运算量，因此逼近的方法应运而生。几乎所有的逼近算法都使用了一 个关键假设，即假设所有的路径及弧长都是独立的。另外，一些算法给出进一步的假 2 中南大学硕士学位论文第一章绪论 设以简化计算。而在实际网络中，一些路径往往是相关的，因为这些路径共用某些弧 线。因此，这种逼近的方法将导致不必要的误差。 为了更清楚地阐述本文所提出的概率算法，下面简要介绍串并联简化法和马氏 链法的基本思想。 1 1 2 串并联简化法 m a r l ：i n 【3 5 j 假设弧长月艮从多项式分布且相互独立，利用串并联简化的方法计算 随机网络最长路径长度的概率分布，这种方法也可以用来求解最短路长度丁的概率分 布。 ( 1 ) 串联简化 幽 图 卜2 令巧和分别表示两串联弧线的长度，气( ，) 、f y j k ( ，) 为其分布函数i 则 瓦= 巧+ 。故瓦的分布为 f r , ( t ) = p ( t k ，) = j 气( ，一) 。( y j , ) d y j , ( 1 1 1 ) ( 2 ) 并联简化 图1 - 3 令k 和艺分别表示两串联弧线的长度，b 。( t ) 、气，( ，) 为其分布函数，则 乙= m i n ， 。故瓦的分布为 弓( ，) = 尸( 乙，) = l 一( 1 一只。o ) ) ( 1 一，( f ) ) ( 1 1 2 ) 网络图中有一类特殊的串并联网络，这种网络经过一系列串联和并联简化，演 变为由一条弧线和两个结点组成的简单网络。例如图l 一4 中的( a ) 经过一系列串联 和并联简化，演变为一条弧线和两个结点( 图1 4 中( b ) ) 当然，并不是所有的网络都可以直接经过一系列串联和并联简化演化为简单网 络，例如图l 一5 就不可以。对于这类网络m a r t i n 3 5 给出了一种转化方法，将这类 网络转化为串并联网络，但此串并联网络中的弧线不再相互独立。可以利用条件概率 3 中南大学硕士学位论文 第一章绪论 及多重积分给出计算最短路长度的分布函数的算法。 图 1 4 图 1 5 1 1 3k u i k a r n i 的马氏链方法 k u l k a r n i 在文献 5 3 中给出了一种求解最短路长度的分析算法，用以求解从随 机网络从一个给定源点到一个给定汇点的最短路径长度的分布函数，其中假设各弧长 相互独立且均服从负指数分布。 令g = ( v ，a ) 表示一个有向非循环随机网络图，其中y 和彳分别表示g 中的结 点集、弧线集。假定g 只有一个源点( s o u r c en o d e ) ，记为s ，一个汇点( s i n kn o d e ) 记为f 。k u l k a r n i 将随机网络视为一个传递信息的通信网络，结点看作信息的中转站， 中转站具有接收和传递信息的功能，弧长看作一条单向通信连接。假定信息在网络中 以单位速度传播，一旦一个结点接收到信息就立刻发送给它所有的后继结点，同时该 结点失去传输功能( 即不能再接收和发送信息) ，称失去传输能力的结点为失效结点。 传输过程持续到信息传递到汇点为止。在传输过程中，可能有些结点和弧线是“无用 的，即使信息经过了这些结点和弧线，因为经过这些结点和弧线的信息只能传送给失 效结点，我们也称这些“无用”的结点为失效结点( 见文 5 3 ) 。令x ( t ) 表示时刻t 失 效结点的集合，若将x ( t ) 看作时刻t 网络图的状念，k u l k a r n i 构建了一个连续时问 4 中南大学硕士学位论文第一章绪论 马尔可夫链 x ( f ) ，f 0 l ，且是一个吸收链，从该马氏链的初始状态首次转移到吸收 状态的时间正好等于随机网络最短路径的长度。 1 2 本文算法的基本思想 显然，前面提到的算法都对随机网络弧长的分布加以限制( 如要求其为连续分 布或假定其为某种特定分布) 。尽管k u l k a r n i 的分析方法简单且容易在计算机e 进行 运算，但弧长的分布是可以多样化的，不一定是负指数分布，它可以是其它任意一般 分布，即它可以是任意连续分布，例如伽玛分布、正态分布、贝塔分布、韦布尔分布 等，也可以有间断点。当弧长的分布不是负指数分布时，k u l k a r n i 的分析方法就不 再适用，因为此时随机网络中信息的传递过程不能转化为马尔可夫过程。为了能够准 确计算随机网络最短路径长度的分布函数，必须研究各弧长均服从一般分布的情况。 对于弧长均服从一般分布的随机网络，计算其最短路长度的概率分布要困难的 多了，而这j 下是本文要解决的问题。回顾k u l k a r n i 的分析方法，假定随机网络的弧 长是相互独立的随机变量，且均服从负指数分布。记x ( t ) 为时刻，失效结点的集合。 r ( t 1 表示时刻t 正在传递信息的弧线集合。因为弧线是相互独立的随机变量，且均 服从负指数，故 x ( ，) ，0 l 是一个有限状态，连续时间马氏链。该马氏链从初始状 态转移到吸收状态的时间正好等于随机网络最短路径的长度，利用马氏链的向后方程 可以求解最短路长度的概率分布。在一般情况下( 弧长不一定服从负指数分布) ，这 种方法之所以不再适用，是因为 肖( ，) ，0 l 不一定是一马尔可夫过程。但是利用添 加变量技术( 见文 1 ) ，可以将其马尔可夫化。例如，对于，( ，) = ( 6 l ，b 2 ，玩) ，我 们引入随机变量只( ，) ，令其表示时刻，信息已经在弧线眈上传输的时问。令 j ( f ) = ( x ( f ) ，吼( ，) ，( ，) ，鼠( f ) ) ，显然， j ( ，) ，0 为一连续时间马尔可夫过 程。由于其状态的复杂性，经典的马氏过程理论不能给出满意的结果。侯振挺、刘再 明及邹捷中于1 9 9 7 年提出一类新型的随机过程马尔可夫骨架过程( 见文 2 2 ) ， 并对其进行了深入的研究，得到了许多让人耳目一新的结果( 见文 2 3 ) 。马尔可夫骨 架过程不一定是马尔可夫过程，但存在一系列停时，过程在这些停时上具有马尔可夫 性。我们发现 j ( f ) ，r 0 是个马尔可夫骨架过程，而且可以利用马尔可夫骨架过 程的向后方程，求得随机网络最短路径长度的分布函数。 1 3 论文主要内容和结构 本文利用马尔可夫骨架理论研究随机网络的最短路径问题，推广k u l k a r n i 5 3 的马氏链法，将其应用到弧长服从般分布的随机网络。本文的结构如下： 第二章：介绍预备知识，包括马尔可夫骨架过程的定义和基本性质。 第三章：通过网络分析，结合图论的知识，构建马尔可夫骨架过程 j ( ，) ，0 ， 并给出 牙( r ) ，0 的状态集。 中南大学硕士学位论文 第一章绪论 第四章：利用马尔可夫骨架过程的向后方程，给出求解最短路径分布的算法。 第五章：给出两个具体的例子。 6 中南人学硕士学位论文 第二章预备知识 第二章预备知识 本章介绍马尔可夫骨架过程相关理论知识，给出它的定义和一些基本性质( 见 h o u 2 2 ) 。 2 1 马尔可夫骨架过程的概念 设( e ，s ) 是可测空间，x = x ( t ，c o ) ，0 f 是定义在完备概率空间 ( q ，尸) 上取值于( e ，占) 的随机过程 f _ ，f o ) 是x 自然盯一代数流。b 为 推移算子：( 只缈) 。= 彩m ， 。) 脚q 定义2 1 1 称随机过程x = x ( t ，c o ) ，0 f o o 为马尔可夫骨架过程，如果存在 一停i 对歹u r ，) 枷，满足 ( 1 ) f o = 0r r 。个0 0 ，并对任意的”o ，f 。 o ojf 。 o + l ： ( 2 ) 对于一切刀= 0 , 1 ，2 ，有f 川= t n + q ( 3 ) 对每一个t n 和任意定义在。 曲) 上的有界o 驯一可测函数，有 e f ( x ( r 。+ ) ) l ，：】2e f ( x ( r 。+ ) ) l x ( f 。) 】，p 一口s ， ( 2 1 1 ) 其中q b = ( c o ：t n ( 彩) ) ，f h x = 彳：v t o ，ac 、( c o ：o f ) f ) 是q “上的仃一 代数。我们把 f 。) 知叫做马尔可夫骨架过程x 的骨架时序列。进而，如果在q ，。上 e f ( x ( r 。+ ) ) l ，z 】= e f ( x ( r 。+ ) ) l x ( f 。) 】= e x ( “) 【厂( x ( r 。) ) 】尸一口j 成立， 则称是时齐的马尔可夫骨架过程，记为旌p 。这罩e ( ) 表示对应于p ( ix ( o ) = x ) 的 期望。 注2 1 1 在本文中，设e 为p o l i s h 空间，s 是b o r e l 盯一代数，q 定义在 倨+ = 【0 ，) 上取值于e 的右连续函数空间。 注2 1 2 由于p o l i s h 空间可度量化，可视x 是定义在度量空间上的右连续随机 过程，所以x 关于 z x ，f o ) 是循序可测的。故x o 。) _ j f f l f ( x ( r 。+ ) ) 是可测的， 这里是( e i 。，一，占【o p ) ) 上的可测函数。 命题2 1 1 如果= x ( ，c o ) ，0 t 二为骨架时序列的正规的马尔可夫骨 架过程，则对于任意的x e ，o ，a 占，有 尸( 砒彳) = 而( 砒么) + e ，：( 艺n = l g ( ( x ，出，咖) ) 办( y , t - s , a ) ( 2 - 2 1 ) 从而p ( x ，a ) 是如下非负方程的最小非负解： p ( x ，f ，么) = 矗( x ，r ，a ) + i i f q ( x , d s ，d y ) p ( y ，t - s ，彳) ，ie e , t o ，彳占 ( 2 2 2 ) e 证明：对任意的x e ，t 0 ，a 占，力n ， p ( x ( ，) 彳，乙， + ii x ( o ) = 工) = ，p ( x ( f ) a ，。f 的齐次性k x = x ( ，) ，0 ) 在r ，处的马尔可夫 性立得： p ( x ( t - s + r ) e 彳，t - - s _ l 彳( o ) = y ，l = s ，x ( o ) = x ) = p ( x ( t s ) a ，t - - s x ( o ) = 力= h ( y ，f j ，彳) 故 9 中南大学硕士学位论文 第二章预备知识 p ( x ( f ) 么，l ， 乙+ ll x ( o ) = x ) ) = ，( g ( x ，d s ，d y ) h ( y ，一s ，彳) e0 从而 p ( x ，彳) = p ( x ( ，) a l x ( o ) = x ) = p ( x ( ，) 彳，f 0 ，a 占，有 只( x ，彳) = ( 毛彳) + 压g ( x ，d y ) h 。( y ，彳) ( 2 2 5 ) fn = l 从而 只( x ，彳) ) 是如下方程的最小非负解。 只( x ，a ) = h 4 ( x ，a ) 4 - f q 工( x ，d y ) p 五( y ，彳) ( 2 2 6 ) 三 方程( 2 2 6 ) 也称为x 的向后方程。同样，我们也把与( 2 2 4 ) 等价的方程 只( x ，a ) = ( x ，a ) - 4 - 1 只( x ，d y ) 蜃z ( y ，a ) ( 2 2 7 ) 中南大学硕士学位论文第二章预备知识 称为x 的向前方程，其中毒。( x ，彳) = p m 香( x ，a ) d t 由定理2 2 1 知正规马尔可夫骨架过程是我们进一步研究的对象下面我们给出 马尔可夫骨架过程成为正规马尔可夫骨架过程的一个充分条件，这个充分条件就是过 程轨道以概率1 处处有左极限。在实际应用中，到目前为止，我们所遇到的马尔可夫 骨架过程都具有这个i 生质。 定理2 2 4 如果( e ，s ) 是p o l i s h 空间，x = x ( f ) ，t 0 ) 是取值于( e ，s ) 且具有右连续左极轨道的马尔可夫骨架过程，则x = x ( f ) ，t 0 ) 是正规的。 2 3 正则性淮则 为讨论方便，我们假定马尔可夫骨架过程x = x ( ，) ，t 0 ) 是不中断的( 或称正 则的) 。实际上，上面得到的定理2 2 1 2 2 4 对于中断马尔可夫骨架过程 x = x ( f ) ，0 t 0 i x ( 0 ) = x ) 0 1 2 中南大学硕士学位论文第二章预备知识 则x 正则 2 4 有限维分布 令d ”= ( f l ，2 ，r 。) ；f l ，f 2 ，t 。r + ，0 ，l ，2 ， ，。) 定义2 4 1 称时齐的马尔可夫骨架过程x = x ( f ) ，f 0 ) 是严j 下规的，如果对于 任意的珂n ，存在e xd ”x 占”上的函数h ( x ，l ，f 2 ，f 。，4 ，么2 ，a 。) 使得 ( i ) 对于固定的x ，l ，一，f 。，h ( x ，f 。，) 是( e ”，占”) 上的有限测度； ( i i ) 对于固定的a l 一，a 。g ，办( - ，4 ，a 。) 是e xd ”上的b o r e l 可测 的函数； ( i i i ) 对于任意的0 ，2 1 ，x e ，v ( t l ，f 。) d 伽) ，a 1 占，a 。占) ( 2 4 2 ) 下面我们不加以证明地给出马尔可夫骨架过程成为严正规马尔可夫骨架过程的 中南大学硕士学位论文 第二章预备知识 充分必要条件过程的轨道1 概率处处有左极限。 定理2 4 2 设x = 彳( f ) ，t o 是以 _ f 。) ：。为骨架时序列的马尔可夫骨架过 程。如果x 的轨道是左极的，则x = x ( f ) ，t 0 是严正规的马尔可夫骨架过程。 2 5 非负线性方程组的最小非负解理论 线性方程组的最小非负解理论是侯振挺( 2 9 和 3 0 ) 为了研究马氏过程的样 本函数提出的，在概率论特别是马氏过程研究中有十分重要的作用。这一节内容主要 来自文献 2 8 的第二章。 定义2 5 1 线性方程组 称为非负线性方程组，如果 一= c ，k x k + 6 ，( f e ) ( 2 5 1 ) 0 c , k 十( f ，k e ) ，0 匆+ o o ( f e ) e 为有限集( 1 ，2 ，胛) 或可列集( 1 ，2 ，) 下面总假设( 2 5 1 ) 是非负线性方程组 定义2 。5 2 ( 2 5 1 ) 的非负解o # 佃( f e ) 成为其最小非负解，如果对于 ( 2 5 1 ) 的任一非负解o 五佃( f e ) 恒有 今后我们常把个a ( n 个佃) 记为 f ( f e ) v l i m = a ” 定理2 5 1 ( 2 5 1 ) 的最小非负解存在唯一：若令 则极限 ( 2 5 2 ) 辩州刀0 , ie ) ) 弦5 3 ， i “d = 靠哪+ 匆( 刀e ) f u a 训 v l i m 毫”= # ( f e ) ( 2 5 4 ) 打斗 存在，且一( ，e ) 就是( 2 5 1 ) 的最小非负解 1 4 中南大学硕士学位论文第二章预备知识 若令 则 本节总以彳( f e ) 就是( 2 5 1 ) 的最小非负解( 2 5 2 ) 称为# ( f e ) 的最小性 推论2 5 1 若( 2 5 1 ) 是其次的，即包三0 ，( f e ) ，则 定理2 5 2 设 推论2 5 2 设 若令 则 则 推论2 5 3 若令 # 三o ( i e ) 研”0 ( n 1 ，i e ) y l i m 印”= 6 ( f e ) n - - - o o ( 2 5 5 ) ( 2 5 6 ) ( 2 5 7 ) 裂静峭圳衅ie ) 眨5 k + ( 聆1 ，e ) f u 7 y l i m 霹”兰彳( f e ) ( 2 5 9 ) 打- - - ) c o 西”0 ( n l , i e ) = 岛( f e ) n = i ( 2 5 1 0 ) ( 2 5 1 1 ) 要二i 霉孙州b l , i e ( 2 5 彰斛”= 或町+ 可” ( 力 e ) f 瞄内j 纠 = 彳( ，e ) ( 2 5 1 3 ) n = l 鬻茹1 纠棚ie 亿叭4 ， 肿”= 以町( 刀l ，e ) f u 闷1 钏 1 5 中南大学硕士学位论文第二章预备知识 一”= f ( f e ) ( 2 5 1 5 ) n = l 定理2 5 3 ( 2 5 1 ) 的满足不等式0 i p x ：i ( i e ，p 为常数) 的唯一非负解 是# ( f e ) ：从任何满足条件o 哥o p x ；( i e ) 的初始值考o ( f e ) 出发，用逐步 逼近法必然得到这个解 推论2 5 4 若# ( f e ) 有性质 则对应于( 2 5 1 ) 的齐次方程 无非零的有界解。 0 i n f f s u p g o 的负指数分布( ( “，v ) 彳) 。 由匕面的两条假设，可以得到下面的定理。 1 8 中南人学硕士学位论文第三章构造马尔可夫骨架过程 定理3 1 2 在a 1 、a 2 假设条件下， x ( ，) ，f o ) 是以d 为状态空间， q = q ( x ，r ) l ( x ，y e d + ) 为无穷小生成矩阵的连续时间马氏链，其中 f ( 州) ，若y = s ( x u l v ) q ( x ，l ，) = 一( 州) ，若y = x ( 3 1 5 ) r 眯q ，其它 随着过程 彳( f ) ，0 ) 的变化，失效结点的数量每次增加至少个，因此过程不 能访问任何一个状态两次。我们按照数量非降的方式给q 中的状态排序，即，若 d ，b q 。且i d l o ：x ( t ) = n lx ( o ) = 1 ) ( 3 1 6 ) 因此随机网络最短路径的长度等于 x ( ，) ，0 ) 从初始状态1 首次转移到吸收 状态的时问。最短路径长度的分布函数，( ，) = 尸 丁f 。我们可以利用 c h a p m a n - k o l m o g o r o v 向后方程求解f ( ，) 。定义 i o 中南大学硕士学位论文第二章构造马尔可夫骨架过程 ( ，) = 尸 x ( f ) = ix ( o ) = f ) ，1 f ( 3 1 7 ) 贝l j f ( t ) = 暑( ，) 。 令尸( f ) = 日( ，) ，e ( ，) ，r ( ，) r ，则有 尸( r ) = 9 p ( ，) ， ( 3 1 8 ) 尸( o ) = 【o ，o ，1 】7 由于无穷小生成矩阵9 为上三角矩阵，微分方程组( 3 1 8 ) 容易求解。 3 2 马尔可夫骨架过程的建立 假设随机网络图中弧长是相互独立的随机变量，且均服从一般分布。求解从源点 到汇点最短路径长度的概率分布。 令 2 ( 0 = ( x ( ，) ，气( ，) ，( ，) ，吃( ，) ) ( 3 2 1 ) 其中，x ( f ) 表示时刻t 失效节点的集合，c ( x ( f ) ) = 包，6 2 ，仇) ， 匆a ，i = 1 ，2 ，k 引入随机变量( t ) ，令其表示时刻，信息已经在弧线6 ，上的传 输时间，( ，) r + 。在以后的部分里，我们将( t ) 简记为。 显然， 2 ( 0 ，o ) 为一连续时间马尔可夫过程。令o 兰o ，l ( 甩1 ) 表示j ( ，) 在【o ，o o ) 的第刀个间断点，显然 牙( ，) ，o ) 是以( l ) 为骨架时序列的马尔可夫骨架 过程。 我们将 叉( 吐t 0 ) 的状态分成n 类，分别记为s ，是，s n s 表示第一类状 态，即( s ，气，吼) ，c ( s ) = ( 6 l ，6 2 ，玩) & 表示最后一类状态，即 ( y ，a ) ，n = i q | 3 3 举例构造 图3 2 中南大学硕+ 学位论文第三章构造马尔可夫骨架过程 这里以图3 - - 2 中的网络为例，构造其对应的马尔可夫骨架过程( t ) 。 q = ( 1 ) ，( 1 ，2 ) ，( 1 ，3 ) ，( 1 ，2 ，3 ) ，( 1 ，2 ，4 ) ，( 1 ，2 ，3 ，4 ) ，( 1 ，2 ，3 ，4 ，5 ) ) 表2 ( 图3 2 中的所有最小割集) 令 墨= ( 1 ，吃，耽：) ，是= ( 1 ，2 ，吃，吃) ，s = ( 1 ，3 ，气，气，气) 墨= ( 1 ，2 ，3 ，吃，气，气) ) ，墨= ( 1 ，2 ，4 ，吃，气) ( 3 3 1 ) 墨= ( 1 ，2 ，3 ，4 ，气，气) ，岛= ( 1 2 ，3 ，4 ，5 ，) ) 则 e = 1 ) 【o ，o o ) 【o ，o o ) u l 2 【o ，) x 【o ，) u 1 ) 3 【o ，) 【o ，o o ) 【o ，) u 1 2 x 3 【o ，o o ) 【o ，) 【o ，o o ) ( 3 3 2 ) u 1 2 4 ) 【o ，) 【o ，) u l 2 3 4 【o ，) 【o ，o o ) u 1 ) 2 3 ) 4 5 o 在图3 - 2 中， 贾( d ，f o 是状态空间为e 的马尔可夫骨架过程。 3 4 关于马尔可夫骨架过程状态的说明 关于 j (