（计算数学专业论文）mg1队列中的taboo概率及其相关计算.pdf

马尔可夫链( m a r k o vc h a i n ) 描述了一个系统在不同时刻处于不同状态 以及从一种状态向另一种状态发生状态转移的情况马尔可夫链模型被应用 于许多领域，其中不仅包括计算机科学和工程学，还有概率与统计，工业工 程，电子工程，生物，基因与农业，经济，教育等同样马尔可夫链可用于 定位通信网络的瓶颈问题，以及评估在多处理系统种增加c p u 的数量带来 等等马尔可夫链是一种在许多领域都非常有用的分析工具 尔可夫链数值求解在马尔可夫链问题中占有非常重要的位置对于有 可夫链的算法分析现在已经相当成熟 1 2 ，1 3 现在许多作者对于无 限情形特别是结构马尔可夫链的数值求解问题进行了大量的研究，同时也提 出了很多具体算法在过去的十多年里由于应用的广泛性和重要性，许多关 于结构马尔可夫链的数值研究得到了极大的推动，其中具有里程碑意义的工 作是由n e u t s 完成的n e u t s 在其著作2 ，3 1 中提出和研究了求解一类马 尔可夫链m g 1 ( 或g i m 1 ) 的新方法在此基础上发展许多具体算法 函数迭代方法( f u n c t i o n a li t e r a t i o n ) 实现简单，但收敛速度是线性的 而另类方法如循环消去( c y c l i cr e d u c t i o n ) 实现相对复杂，但具有二次收 敛速度1 4 | 通常，以前的算法都是对于( 关于层) 齐次结构马尔可夫链提出的，很 少( 关于层) 对于非齐次情形进行讨论在 1 i 中， j s t e w a r t 提到非齐次 q b d 马尔可夫链( al o a d d e p e n da r r i v a lp r o c e s s ) 是很难用迭代法求出矩 阵 r ( “) ，“h o w e v e r , e v e ni n t h i ss i m p l ec a s e ，i ti sn o te v i d e n tt h a tt h e s e m a t r i c e sc a nb ec o m p u t e di t e r a t i v e l 矿f 1 1 但t a b o o 概率意义下的算法不但 可以很容易的计算出 r ( “) ) ，而且可以应用到更一般的情形中。沪一 在这篇文章中，我们分析了t a b o o 概率在求解稳定分布中的重要意义， 并在此基础上提出具有二次收敛速度的算法，使得原来在齐次m g l ( 或 o i m 1 ，q b d ) 马尔可夫链下的算法更具有普遍性，从而把二次收敛速度的 算法推广到非齐次情形 关键词：马尔可夫链，t a b o o 概率，q b d ，齐次帆非齐次飙循环消去， 稳定分布，数值解 。 2 甓臻的限 、l a b s t r a c t m a r k o vc h a i ni sap o w e r f u lt o o lf o rs o l v i n gaw i d ev a r i e t yo fp r o b l e m s o ft h er e a lw o r l d i ti so f t e np o s s i b l et or e p r e s e n tt h eb e h a v i o ro fap h y s i c o ls y s t e mb yd e s c r i b i n ga l lt h ed i f f e r e n ts t a t e st h a ti tc a no c c u p ya n db y i n d i c a t i n gh o wi tm o v e sf r o mo n es t a t e t oa n o t h e ri nt i m e m a r k o vc h a i n m o d e l l i n gi su s e di nm a n yd i v e r s ea r e a s ，n o to n l yi nc o m p u t e rs c i e n c ea n d e n g i n e e r i n gb u ta l s oi no t h e rd i s c i p l i n e ss u c ha sm a t h e m a t i c s ，p r o b a b i l i t ya n d s t a t i s t i c s ，o p e r a t i o n sr e s e a r c h ，i n d u s t r i a le n g i n e e r i n g ，e l e c t r i c a le n g i n e e r i n g ， b i o l o g y ，g e n e t i c sa n da g r i c u l t u r e ，e c o n o m i c s ，e d u c a t i o n ，a n ds oo n t h e r ei sag r e a td e m a n df o re f f i c i e n tm a t h e m a t i c a lt e c h n i q u e sa n df a s t a l g o r i t h m sf o rs o l v i n gm a r k o vc h a i n sn u m e r i c a l l y ac l a s so fi a da l g o r i t h m s h a sb e e nd e v e l o p e df o rs o l v i n gt h ef i n i t em a r k o vc h a i n se t t i c i e n t l y 1 2 ，1 3 i n t h el a s td e c a d e ，t h er e s e a r c hi nt h ea r e ao ft h e o r e t i c a la n dn u m e r i c a ls o l u t i o n o fi n f i n i t es t r u c t u r e dm a r k o vc h a i n sh a sh a dag r e a tp r o g r e s s am i l e s t o n e o ft h ew o r ki sd o n eb yn e u t s 2 ，3 l ，w h e r en e wt o o l sf o rs o l v i n gt h ec l a s so f h o m o g e n e o u sm g 1t y p em a r k o vc h a i n s ( a n dt h ed u a lo fg i m 1t y p e ) a r e i n t r o d u c e da n di n v e s t i g a t e dd e e p l y m a n ya l g o r i t h m sa r ed e v e l o p e do nt h e b a s i so fn c u t s t h e o r e m a si sw e l lk n o w n ，f u n c t i o n a li t e r a t i o nt e c h n i q u e sa r ec o m m o n l yu s e d ，b u t t h ec o n v e r g e n c eo ft h e s en u m e r i c a ls c h e m e sr e m a i n sl i n e a r am e t h o db a s e d o nc y c l i cr e d u c t i o ni sn u m e r i c a l l ys t a b l ea n dq u a d r a t i c a l l yc o n v e r g e n t 4 i ng e n e r a l ，a l lt h ep r e v i o u sa l g o r i t h m sa r en o ts u i t a b l ef o rn o n h o m o g e n e o u s m a r k o vc h a i n si n 1 ) n e u t ss h o w e dt h a ti ti sd i f f i c u l tt oc o m p u t e r ( “) i t e r a t i v e l y i nt h en o n h o m o g e n e o u sq b dc a s e “h o w e v e r , e v e n 锄t h i ss i m p l ec a s e i ti s n o te v i d e n tt h a tt h e s em a t r i c e sc a nb ec o m p u t e di t e r a t i v e l 矿” b u ti n t h i sp a p e r ，b yt h ea n a l y s i so ft a b o op r o b a b i l i t y , w ep r o p o s ea n e wm e t h o df o rs o l v i n gt h en o n h o m o g e n e o u sq b d ，w h i c hi sq u a d r a t i c a l l y c o n v e r g e n t e s p e c i a l l y ，b yt h en e wm e t h o d ，w ec a nc o m p u t e r ( “) ) i t e r a - t i v e l yi nt h en o n h o m o g e n e o u sq b d c a s e k e y w o r d s ：m a r k o vc h a i n ，t a b o op r o b a b i l i t y ，q b d ，h o m o g e n e o u s ，n o n h o m o g e n e o u s ，c r s t a t i o n a r yd i s t r i b u t i o n ，n u m e r i c a ls o l u t i o n 3 1 引言 马尔科夫链( 简称马氏链，m a r k o vc h a i n s ) 是一种特殊的随机过程， 最初由aam a p k o b 所研究马氏链模型被广泛应用于各个领域如计算机科 学、概率统计、经济等它是一种解决现实问题的强有力工具，它有如下直 观背景： 设想有一个系统，我们可以通过描述该系统可能处的状态，以及在某时 刻系统怎样从一个状态转到另一个状态来表示该系统的行为如果在任一 个状态上的时间是指数分布的，系统可以表示为马尔科夫过程由此可以知 道，马尔科夫过程可以被表示为一个有限或无限的状态集合，而系统在某一 时刻只处于其中唯一的一个状态系统状态发生改变可以表示为马尔科夫过 程从一个状态向另一个状态发生转移这些状态转移过程本身是不需要时间 的马尔科夫系统有一个最基本的性质称为马尔科夫性质：系统将要发生的 状态改变只与当前系统所处的状态相关，而与过去发生的状态无关，即无记 忆性 下面给出马氏链的一般定义 在给定的一个概率空间里，定义随机过程为一系列随机变量i x ( t ) ，t t ，其中t 通常是在区间( 一o o ，+ o 。) 上表示时间的一个指标集合x ( t ) 表示随机过程在t 时刻所处的状态，一系列的状态构成状态空间状态空间 可分为连续和离散的 定义1 1 ( 马尔可夫过程) 马尔可夫过程可定义为条件概率分布函数( p r o b a b i l i t yd i s t r i b u t i o nf u n c t i o n ) 满足? 马尔可夫性质”的随机过程 设x ( t ) 是连续时间随机过程，x ( t ) 是连续时间马尔可夫过程当且仅 当对任何序列t o t 1 e u = u + a o ( i a 1 ) 一1 4 2 a o = a o ( i a 1 ) 一1 a o a l = a 1 + a o ( i 一4 1 ) 一1 a 2 a 2 = a 2 ( ，一a 1 ) “a 2 从上可以看出，算法每步迭代只需6 个矩阵乘法，而在l r ( l a t o u c h e & r a m a s w a m i ) 算法中每步迭代需要8 个矩阵乘法 下面我们利用t a b o o 概率求解非齐次q b d 马氏链问题 在非齐次马氏链( 1 5 ) 中，设r 表示( 女+ 1 ) + 1 ) 主子矩阵可 以简单验证，对于p 的k + l 阶随机补曜除了右下角分块外其余都与矩阵 r 相同而这个不同的分块就是t a b o o 概率矩阵u ( 同样可以验证矩阵 难。就是主子矩阵r 一- 相对曜的随机补 于是当= 0 时， 瑶= a l o + a 铲( ，一( 1 ) 一1 a ， 显然，豸满足昂e = e ，是随机矩阵设贯的稳定分布设为粕，由引理2 1 可以知道西。与马氏链p 的随机分布第一个分量7 1 0 只相差一个常量因子， 吼= 褊 1 7 下面，我们运用t a b o o 概率计算t a b o o 矩阵u ( 斛为了方便描述我们 先给出= 1 时计算u ( 1 ) 的算法 记非齐次q b d 初始转移矩阵为 l e v e l 0k+ 1k + 2 p ( o ) = a ( 0 a 铲 。a 2 ( 1 , o a 1 ，o a 铲 a a i 2 ， a 字 其中a p o = a p ，i = 0 ，1 ，2 ，j2l ，j 矩阵p ( o ) 一i 我们作一步循环消去法 去第女+ i 层状态，其中i = 1 ，3 ，5 ， a 5 2 ，0 ) a 5 3 ，0 ) ( 3 1 ) 表示层数，0 表示消去的步数对于 ( c y l i cr e d u c t i o n ) ，对应于马氏链是消 可以看出，在经过一步消去法后，矩 阵前行k 列的分块以及其余部分分块在消去过程中都没有改变如果我 们只显示改变了的部分，则得到一个新的矩阵，记为p ( 1 ) 其中算法为 f e v e l p ( 1 ) = a i l a 5 1 a 字 a ( 2 a 4 k + a 5 l a c 2 a 圹 2k + 4k + 6 1 ) 1 a 铲， 1 卵， a 铲， a 5 3 ，1 ) a a 5 1 ，o + a 5 1 ，o ( ，一a ( 2 o ) 一1 a 字o a 5 1 ，o ( ，一a ( 2 o ) 一1 a 铲叭， a 字，o ( ，一a ( 2 0 1 ) 一1 a 字叭， a 1 3 ，o ) + a 字，o ( ，一a i 2 o ) 一1 a 乎o 4 扩，o ( ，一a i 4 o ) 一1 a m ， a 扩，o ( ，一a i 4 ，o ) 一1 a 铲叭， a 字t o ( j a ( 4 o ) 一1 a 铲叭， ( 3 2 ) ( 33 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) ( 3 7 ) ( 3 8 ) o 卵管 我们可以看出，当马氏链是齐次q b d 时，算法就简化为m e t n i 在f 4 1 中的算法 同样，齐次q b d 马氏链是s k i p f f e et ot h er i g h t 4 表示系统从状态 ( ，i ) ，这里( = 1 ) ，出发到达状态( ，j ) 的概率，中间过程可能到达第a + 1 层的某些状态，除此之外不会处于其它任何状态而4 5 1 , 1 表示系统从状态 ( k ，i ) 出发到达状态( k + 2 ，j ) 的概率，中间过程可能到达第七+ l 层的某些 状态，除此之外不会处于其它任何状态 重复上述消去过程，我们得到矩阵序列 p ( i ) 如马氏链是正常返的， 可以得到 4 ) _ o ，a i - - + u ( n ，i _ 。 由此得到计算t a b o o 概率矩阵u ( ) 的算法如下， 算法n q b d c r u ：对于给定非齐次q b d 马氏链( 1 5 ) ，通过上述消去算 法，可以求出满足等式 u ( n ) = a i “) 十a s 佗( ，一u ( n + 1 ) 一1 a 妒+ ， 的最小非负解u ( 舢，女l j i n i t i a l i z a t i o n ? a i 叭= a ”g i v e ne 0 d ow h i l e1 1 a p ) ，迭代算法( 3 3 ) 一( 3 8 ) 等 通过t a b o o 概率，算法把无限的马氏链变为有限的当j _ + o 。时 p o ) 一 a o a 扩 a 5 1 a 1 a 5 1 ) a 孑a 1 2 a 铲 a ( 2 a ) a 3 a 垆d 。 矿( ) = c ，( 3 9 ) 如果我们把马氏链的状态空间分为两部分： s 1 ，表示从第0 层到第k 层的状态集合，是有限的 岛，表示所有剩余的其它状态，是无限的 由此，算法的主要思想是把系统在无限状态集合岛中的概率加到有限集合 s t 中则无限的马氏链变为一个适当的有限马氏链在( 3 9 ) 中，设g = a r + e 则c 表示为如下两部分： 1 9 1 系统在状态集合s - 中直接从( k ，z ) 到达( k ，j ) ，中间不会处于岛以及其 它任何状态 2 系统从状态( ，i ) 出发，经过状态集合岛最终到达( ，j ) ，中间不会处于 s l 中任何状态 3 2 非齐次g i m 1 马氏链计算 从上一节可以看出，t a b o o 概率在对于齐次或者非齐次q b d 马氏链 计算中的作用在这一节中，我们将把t a b o o 概率扩展到求解齐次或非齐次 g i m i i ( m g 1 ) 情形 首先考虑非齐次g i m 1 马氏链( 1 4 ) ，设+ 1 阶主子矩阵为r ，对应 随机补为则可以验证，矩阵r 与曜除了最后一行分块外，其余都相 同当= 0 时，昂是随机矩阵由引理2 1 知道瑶的稳定分布与p 的 相对应稳定分布第一分量丌。只相差一个常量因子 下面我们用迭代法求t a b o o 概率矿( 斛为了方便起见，我们给出= 1 时计算u ( 1 ) 的算法设非齐次g i m 1 马氏链初始转移矩阵为 f e v e z0k ，a f 0 )a 5 0 ) ja 4 i 1 。) p ( 。) ：fa 孑埘a 孑，。j i4 5 3 ，o ) a k + l 0 a 3 i ，o ) a 2 o ) a 女+ 2 0 a a i 3 0 ) ( 3 1 0 ) 其中a = 4 妙类似于非齐次q b d 马氏链，我们对矩阵p - i 作一步循环 消去法，对应马氏链为消去第+ i 层状态，其中i = 1 ，3 ，5 ，由此一步消 去后得到一个新矩阵，按照原来的结构并只显示没有改变的分块，记为p ( 1 ) f e v e l p o ) ： 0 a p a 5 l ，1 ) a 4 1 3 ，l 3 a 铲0 a a 5 1 a a p a 5 3 ，1 硝 2 0 5 0 a 掣 a ( 3 1 1 ) 其中算法如下 a 1 a 5 1 4 1 1 a 孑 a 7 ，1 ) a 2 1 1 ) a = a ；) 十a 5 1 ，。( ，一a 2 o ) a 铲，o ) = a 3 1 川( j a 宁1 0 ) 一1 a 铲o = a 9 o + a 3 1 ，o ( 一a i 2 ，o ) 一1 a 乎，o ) = 4 扩o + a 扩o ( ，一a ( 2 o ) 一1 a 孑，o ) + 4 5 3 】o ( ，一a i 4 ，o ) 一1 a f o = a 字，o ) + a 字，o ( ，一a 铲，o ) 一1 a 字，o ) + a 扩，o ( 一a ；4 ，o ) 一1 a 铲o = a 驴o + a 字o ( ，一m 1 2 ，o ) 一1 a 铲o ) + 4 扩o ( ，一a 1 4 ，o ) 一1 a 笋o ) = a 铲o ( f a p o ) 一1 a 铲，o ) ( 3 1 2 ) ( 31 3 ) ( 3 1 4 ) ( 3 1 5 ) ( 3 1 6 ) ( 3 1 7 ) ( 3 1 8 ) 显然齐次g w m 1 马氏链a ia ；只是算法