可逆马氏链中文

可逆马氏链1TopicsTime-ReversalofMarkovChainsReversibilityTruncatingaReversibleMarkovChainBurke’sTheoremQueuesinTandemTime-ReversedMarkovChains假定{Xn:n=0,1,…}为遍历的马氏链,转移概率为

Pi,j,唯一的平稳分布为(πj>0).假定过程从－∞开始,

即{Xn:n=…,－n,…,-1,

0,1,…}

,

则系统在时刻n的状态概率Pr{Xn=j}=平稳分布πj.任意τ>0，定义Yn=Xτ-n,过程{Yn}是原马氏链的时间逆转过程.可以证明{Yn}也是马氏链，转移概率为而且和{Xn}有相同的平稳分布

πj通过逆向链可看出正向链的某些性质；Time-ReversedMarkovChainsProofofProposition1:Reversibility马氏链{Xn}称为可逆的如果正向链和逆向链有相等的转移概率:Pi,j=Pi,j*,等价于{Xn}满足DBE.

定理1.如果能找到一组正数{πj},

其和为1,且满足:

πiPi,j=πjPj,i,则该马氏链是可逆的且以{πj}为平稳分布.

Reversibility–Discrete-TimeChainsExample:Discrete-timebirth-deathprocessesarereversible,sincetheysatisfytheDBE重要定理Theorem1:对转移概率为

Pij.的不可约马氏链，如果存在:一组转移概率Qij,满足∑j

Qij=1,i≥0,和一组整数{πj},其和为1,并且下式成立则:Qij

为其逆向链的转移概率{πj}同时既是正向链也是逆向链的平稳分布Remark:上述定理常用来计算平稳分布：根据马氏链的结构性质猜出两组数Qij,和{πj},验证是否满足(1)：如果满足，则该马氏链是可逆链且以{πj}为平稳分布，而Qij

为逆链的转移概率.Continuous-TimeMarkovChains设{X(t):-∞<t<∞}是不可约的遍历的连续时间马氏链，转移率为

qij,i≠j设(pi

>0)为它的唯一的平稳分布:仍假定过程从-∞开始，则在有穷时间t链处于平稳态:P{X(t)=j}=pj令Y(t)=X(τ-t)，则以下命题成立:ReversedContinuous-TimeMarkovChainsProposition2:{Y(t)}也是连续时间马氏链，转移率为:{Y(t)}和正向链有相同的平稳分布:{pj}

Remark:

逆向链离开i

的转移率等于正向链离开i

的转移率：这是GBE的另一表达形式:逆向链的“出”＝正向链的“入”Reversibility–Continuous-TimeChains马氏链称为可逆的如果：

或等价的:此即DBETheorem3:

如果有一组正数{pj},其和为1且满足:

则:{pj}是唯一的平稳分布该马氏链是可逆的Birth-DeathProcess转移率为满足DBEProof:GBEwithS={0,1,…,n}give:M/M/1,M/M/c,M/M/∞是可逆马氏链01n+1n2SSc重要的定理Theorem4:

对有转移率qij.的不可约马氏链，如果存在:一组转移率,满足∑j≠i

φij=∑j≠i

qij,i≥0,和一组正数{pj},其和为1,使得以下方程成立:则:φij

是逆向链的转移率,且{pj}是正向和逆向链的相同的平稳分布上述定理用来解马氏链：guess两组数φij和{pj}，验证上述条件状态转移率图是树结构的马氏链Theorem5:状态转移率图有树结构的马氏链是可逆的.01263745Burke’s定理假设N(t)为一生灭过程,有平稳分布{pj}N(t)的向上跳跃点为到达点.

N(t)的向下跳跃点为离开点.

N(t)包括了系统的到达和离开过程ArrivalsDeparturesBurke’sTheorem如λj=λ,forall,则到达为Poisson.这时称此过程为(λ,μj)-过程M/M/1,M/M/c,M/M/∞为(λ,μj)-过程Poissonarrivals→LAA:

Foranytimet,futurearrivalsareindependentof{X(s):s≤t}(λ,μj)-processatsteadystateisreversible:forwardandreversedchainsarestochasticallyidenticalArrivalprocessesoftheforwardandreversedchainsarestochasticallyidenticalArrivalprocessofthereversedchainisPoissonwithrateλThearrivalepochsofthereversedchainarethedepartureepochsoftheforwardchainDepartureprocessoftheforwardchainisPoissonwithrateλBurke’sTheoremReversedchain:arrivalsaftertimetareindependentofthechainhistoryuptotimet(LAA)Forwardchain:departurespriortotimetandfutureofthechain{X(s):s≥t}areindependentBurke’sTheoremTheorem10:ConsideranM/M/1,M/M/c,orM/M/∞systemwitharrivalrateλ.Supposethatthesystemstartsatsteady-state.Then:ThedepartureprocessisPoissonwithrateλAteachtimet,thenumberofcustomersinthesystemisindependentofthedeparturetimespriortotFundamentalresultforstudyofnetworksofM/M/*queues,whereoutputprocessfromonequeueistheinputprocessofanotherBurkes定理说两件事情:处于平稳态的M/M/＊排队系统的离开过程是Poisson，而且参数为λ.处于平稳态的M/M/＊排队系统内客户数N(t)独立于t以前,即(0,t)时间内的离开过程应用Burkes定理可以推出级联队列的平稳客户数分布有乘积形式:P(n1,n2)=P(n1)P(n2).Burkes定理Figure3.31(a)Forwardsystemnumberofarrivals,numberofdepartures,andoccupancyduring[0,T].Figure3.31(b)Reversedsystemnumberofarrivals,numberofdepartures,andoccupancyduring[0,T].根据Burkes定理,不能从客户接连不断的离开推断系统内有大量的客户,因为这两者之间没相关性.(反直觉,counterintuitive)

Single-ServerQueuesinTandem（级联）Customersarriveatqueue1accordingtoPoissonprocesswithrateλ.Servicetimesexponentialwithmean1/μi.Assumeservicetimesofacustomerinthetwoqueuesareindependent.Assumeρi=λ/μi<1WhatisthejointstationarydistributionofN1andN2–numberofcustomersineachqueue?Result:insteadystatethequeuesareindependentandPoissonStation1Station2Single-ServerQueuesinTandemQ1isaM/M/1queue.AtsteadystateitsdepartureprocessisPoissonwithrateλ.ThusQ2isalsoM/M/1.Marginalstationarydistributions:Tocompletetheproof:establishindependenceatsteadystateQ1atsteadystate:attimet,N1(t)isindependentofdeparturespriortot,whicharearrivalsatQ2uptot.ThusN1(t)andN2(t)independent:Lettingt→∞,thejointstationarydistributionPoissonStation1Station2如果排队系统组成的网络是有向无环图,每个系统的客户服务时间是指数分布,外部到达是Poisson,则每个内部排队系统的到达过程是Poisson.QueuesinTandemTheorem11:NetworkconsistingofKsingle-serverqueuesintandem.Servicetimesatqueueiexponentialwithrateμi,independentofservicetimesatanyqueuej≠i.ArrivalsatthefirstqueuearePoissonwithrateλ.Thestationarydistributionofthenetworkis:Atsteadystatethequeuesareindependent;thedistributionofqueueiisthatofanisolatedM/M/1queuewitharrivalandserviceratesλandμiQueuesinTandem:State-DependentServiceRatesTheorem12:NetworkconsistingofKqueuesintandem.Servicetimesatqueueiexponentialwithrateμi(ni)whentherearenicustomersinthequeue–independentofservicetimesatanyqueuej≠i.ArrivalsatthefirstqueuearePoissonwithrateλ.Thestationarydistributionofthenetworkis:

where{pi(ni)}isthestationarydistributionofqueueiinisolationwithPoissonarrivalswithrateλExamples:./M/cand./M/∞queuesIfqueueiis./M/∞,then:MultidimensionalMarkovChainsTheorem8:

{X1(t)},{X2(t)}:independentMarkovchains{Xi(t)}:reversible{X(t)},withX(t)=(X1(t),X2(t)):vector-valuedstochasticprocess{X(t)}isaMarkovchain{X(t)}isreversibleMultidimensionalChains:Queueingsystemwithtwoclassesofcustomers,eachhavingitsownstochasticproperties–trackthenumberofcustomersfromeachclassStudythe“joint”evolutionoftwoqueueingsystems–trackthenumberofcustomersineachsystemExample:TwoIndependentM/M/1QueuesTwoindependentM/M/1queues.Thearrivalandserviceratesatqueueiareλiandμirespectively.Assumeρi=λi/μi<1.{(N1(t),N2(t))}isaMarkovchain.Probabilityofn1customersatqueue1,andn2atqueue2,atsteady-state“Product-form”distributionGeneralizesforanynumberKofindependentqueues,M/M/1,M/M/c,orM/M/∞.Ifpi(ni)isthestationarydistributionofqueuei:Stationarydistribution:DetailedBalanceEquations:VerifythattheMarkovchainisreversible–KolmogorovcriterionExample:TwoIndependentM/M/1Queues02122232011121310010203003132333Example:TwoIndependentM/M/1Queues02122232011121310010203003132333TruncationofaReversibleMarkovChainTheorem9:{X(t)}reversibleMarkovprocesswithstatespaceS,andstationarydistribution{pj:jS}.TruncatedtoasetES,suchthattheresultingchain{Y(t)}isirreducible.Then,{Y(t)}isreversibleandhasstationarydistribution:Remark:Thisistheconditionalprobabilitythat,insteady-state,theoriginalprocessisatstatej,giventhatitissomewhereinEProof:Verifythat:Twoexamples:例1M/M/m/m是M/M/∞的截断,S={0,1,…,m},G=1+ρ

+…+ρm/m!,p(n)=(ρn/n!)/G,ρ=(λ/μ)例2M/M/1/K是M/M/1的截断(习题3.21)M/M/1有平稳分布ρn(1-ρ),截断链的状态集为S={0,1,…,K},

G=∑ρn

(1-ρ)=1-ρK+1,截断链的平稳分布为:p(n)=ρn(1-ρ)/G=ρn(1-ρ)/(1-ρK+1).Example:TwoQueueswithJointBufferThetwoindependentM/M/1queuesofthepreviousexampleshareacommonbufferofsizeB–arrivalthatfindsBcustomerswaitingisblockedStatespacerestrictedtoE={(n1,n2)|n1+n2<=B}Distributionoftruncatedchain:Normalizing:TheoremspecifiesjointdistributionuptothenormalizationconstantCalculationofnormalizationconstantisoftentedious02120111210010203003132231

StatediagramforB=2多维马氏链-在电路交换网中的应用Example：3.12考虑具有m个独立电路，每个电路都具有相同的传输能力系统中存在两类会话，到达率分别是λ1和λ2的泊松分布当一个会话到达系统时，若发现所有电路都处于繁忙状态，这个会话将被封锁，继而被丢弃。相反，系统将会话分配给任意一个可用的电路。