可逆馬氏鏈中文

可逆馬氏鏈1TopicsTime-ReversalofMarkovChainsReversibilityTruncatingaReversibleMarkovChainBurke’sTheoremQueuesinTandemTime-ReversedMarkovChains假定{Xn:n=0,1,…}為遍歷的馬氏鏈,轉(zhuǎn)移概率為

Pi,j,唯一的平穩(wěn)分布為(πj>0).假定過程從－∞開始,

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

0,1,…}

,

則系統(tǒng)在時(shí)刻n的狀態(tài)概率Pr{Xn=j}=平穩(wěn)分布πj.任意τ>0，定義Yn=Xτ-n,過程{Yn}是原馬氏鏈的時(shí)間逆轉(zhuǎn)過程.可以證明{Yn}也是馬氏鏈，轉(zhuǎn)移概率為而且和{Xn}有相同的平穩(wěn)分布

πj通過逆向鏈可看出正向鏈的某些性質(zhì)；Time-ReversedMarkovChainsProofofProposition1:Reversibility馬氏鏈{Xn}稱為可逆的如果正向鏈和逆向鏈有相等的轉(zhuǎn)移概率:Pi,j=Pi,j*,等價(jià)于{Xn}滿足DBE.

定理1.如果能找到一組正數(shù){πj},

其和為1,且滿足:

πiPi,j=πjPj,i,則該馬氏鏈?zhǔn)强赡娴那乙詛πj}為平穩(wěn)分布.

Reversibility–Discrete-TimeChainsExample:Discrete-timebirth-deathprocessesarereversible,sincetheysatisfytheDBE重要定理Theorem1:對(duì)轉(zhuǎn)移概率為

Pij.的不可約馬氏鏈，如果存在:一組轉(zhuǎn)移概率Qij,滿足∑j

Qij=1,i≥0,和一組整數(shù){πj},其和為1,并且下式成立則:Qij

為其逆向鏈的轉(zhuǎn)移概率{πj}同時(shí)既是正向鏈也是逆向鏈的平穩(wěn)分布Remark:上述定理常用來計(jì)算平穩(wěn)分布：根據(jù)馬氏鏈的結(jié)構(gòu)性質(zhì)猜出兩組數(shù)Qij,和{πj},驗(yàn)證是否滿足(1)：如果滿足，則該馬氏鏈?zhǔn)强赡骀溓乙詛πj}為平穩(wěn)分布，而Qij

為逆鏈的轉(zhuǎn)移概率.Continuous-TimeMarkovChains設(shè){X(t):-∞<t<∞}是不可約的遍歷的連續(xù)時(shí)間馬氏鏈，轉(zhuǎn)移率為

qij,i≠j設(shè)(pi

>0)為它的唯一的平穩(wěn)分布:仍假定過程從-∞開始，則在有窮時(shí)間t鏈處于平穩(wěn)態(tài):P{X(t)=j}=pj令Y(t)=X(τ-t)，則以下命題成立:ReversedContinuous-TimeMarkovChainsProposition2:{Y(t)}也是連續(xù)時(shí)間馬氏鏈，轉(zhuǎn)移率為:{Y(t)}和正向鏈有相同的平穩(wěn)分布:{pj}

Remark:

逆向鏈離開i

的轉(zhuǎn)移率等于正向鏈離開i

的轉(zhuǎn)移率：這是GBE的另一表達(dá)形式:逆向鏈的“出”＝正向鏈的“入”Reversibility–Continuous-TimeChains馬氏鏈稱為可逆的如果：

或等價(jià)的:此即DBETheorem3:

如果有一組正數(shù){pj},其和為1且滿足:

則:{pj}是唯一的平穩(wěn)分布該馬氏鏈?zhǔn)强赡娴腂irth-DeathProcess轉(zhuǎn)移率為滿足DBEProof:GBEwithS={0,1,…,n}give:M/M/1,M/M/c,M/M/∞是可逆馬氏鏈01n+1n2SSc重要的定理Theorem4:

對(duì)有轉(zhuǎn)移率qij.的不可約馬氏鏈，如果存在:一組轉(zhuǎn)移率,滿足∑j≠i

φij=∑j≠i

qij,i≥0,和一組正數(shù){pj},其和為1,使得以下方程成立:則:φij

是逆向鏈的轉(zhuǎn)移率,且{pj}是正向和逆向鏈的相同的平穩(wěn)分布上述定理用來解馬氏鏈：guess兩組數(shù)φij和{pj}，驗(yàn)證上述條件狀態(tài)轉(zhuǎn)移率圖是樹結(jié)構(gòu)的馬氏鏈Theorem5:狀態(tài)轉(zhuǎn)移率圖有樹結(jié)構(gòu)的馬氏鏈?zhǔn)强赡娴?01263745Burke’s定理假設(shè)N(t)為一生滅過程,有平穩(wěn)分布{pj}N(t)的向上跳躍點(diǎn)為到達(dá)點(diǎn).

N(t)的向下跳躍點(diǎn)為離開點(diǎn).

N(t)包括了系統(tǒng)的到達(dá)和離開過程ArrivalsDeparturesBurke’sTheorem如λj=λ,forall,則到達(dá)為Poisson.這時(shí)稱此過程為(λ,μ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定理說兩件事情:處于平穩(wěn)態(tài)的M/M/＊排隊(duì)系統(tǒng)的離開過程是Poisson，而且參數(shù)為λ.處于平穩(wěn)態(tài)的M/M/＊排隊(duì)系統(tǒng)內(nèi)客戶數(shù)N(t)獨(dú)立于t以前,即(0,t)時(shí)間內(nèi)的離開過程應(yīng)用Burkes定理可以推出級(jí)聯(lián)隊(duì)列的平穩(wěn)客戶數(shù)分布有乘積形式:P(n1,n2)=P(n1)P(n2).Burkes定理Figure3.31(a)Forwardsystemnumberofarrivals,numberofdepartures,andoccupancyduring[0,T].Figure3.31(b)Reversedsystemnumberofarrivals,numberofdepartures,andoccupancyduring[0,T].根據(jù)Burkes定理,不能從客戶接連不斷的離開推斷系統(tǒng)內(nèi)有大量的客戶,因?yàn)檫@兩者之間沒相關(guān)性.(反直覺,counterintuitive)

Single-ServerQueuesinTandem（級(jí)聯(lián)）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如果排隊(duì)系統(tǒng)組成的網(wǎng)絡(luò)是有向無環(huán)圖,每個(gè)系統(tǒng)的客戶服務(wù)時(shí)間是指數(shù)分布,外部到達(dá)是Poisson,則每個(gè)內(nèi)部排隊(duì)系統(tǒng)的到達(dá)過程是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/∞的截?cái)?S={0,1,…,m},G=1+ρ

+…+ρm/m!,p(n)=(ρn/n!)/G,ρ=(λ/μ)例2M/M/1/K是M/M/1的截?cái)?習(xí)題3.21)M/M/1有平穩(wěn)分布ρn(1-ρ),截?cái)噫湹臓顟B(tài)集為S={0,1,…,K},

G=∑ρn

(1-ρ)=1-ρK+1,截?cái)噫湹钠椒€(wěn)分布為: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多維馬氏鏈-在電路交換網(wǎng)中的應(yīng)用Example：3.12考慮具有m個(gè)獨(dú)立電路，每個(gè)電路都具有相同的傳輸能力系統(tǒng)中存在兩類會(huì)話，到達(dá)率分別是λ1和λ2的泊松分布當(dāng)一個(gè)會(huì)話到達(dá)系統(tǒng)時(shí)，若發(fā)現(xiàn)所有電路都處于繁忙狀態(tài)，這個(gè)會(huì)話將被封鎖，繼而被丟棄。相反，系統(tǒng)將會(huì)話分配給任意一個(gè)可用的電路。