可逆馬氏鏈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的泊松分布當一個會話到達系統時，若發現所有電路都處于繁忙狀態，這個會話將被封鎖，繼而被丟棄。相反，系統將會話分配給任意一個可用的電路。