可逆馬氏鏈中文

可逆馬氏鏈中文1第1頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月TopicsTime-ReversalofMarkovChainsReversibilityTruncatingaReversibleMarkovChainBurke’sTheoremQueuesinTandem2第2頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Time-ReversedMarkovChains假定{Xn:n=0,1,…}為遍歷的馬氏鏈,轉(zhuǎn)移概率為Pi,j,唯一的平穩(wěn)分布為(πj>0).假定過(guò)程從－∞開(kāi)始,即{Xn:n=…,－n,…,-1,

0,1,…}

,則系統(tǒng)在時(shí)刻n的狀態(tài)概率Pr{Xn=j}=平穩(wěn)分布πj.任意τ>0，定義Yn=Xτ-n,過(guò)程{Yn}是原馬氏鏈的時(shí)間逆轉(zhuǎn)過(guò)程.可以證明{Yn}也是馬氏鏈(見(jiàn)書(shū)215頁(yè)),轉(zhuǎn)移概率為而且和{Xn}有相同的平穩(wěn)分布πj通過(guò)逆向鏈可看出正向鏈的某些性質(zhì)；3第3頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Reversibility馬氏鏈{Xn}稱(chēng)為可逆的如果正向鏈和逆向鏈有相等的轉(zhuǎn)移概率:

Pi,j=Pi,j*,等價(jià)于{Xn}滿(mǎn)足DBE.定理1.如果能找到一組正數(shù){πj},

其和為1,且滿(mǎn)足:

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

4第4頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Reversibility–Discrete-TimeChainsExample:Discrete-timebirth-deathprocessesarereversible,sincetheysatisfytheDBE5第5頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月重要定理Theorem1:對(duì)轉(zhuǎn)移概率為

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

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

為其逆向鏈的轉(zhuǎn)移概率{πj}同時(shí)既是正向鏈也是逆向鏈的平穩(wěn)分布Remark:上述定理常用來(lái)計(jì)算平穩(wěn)分布：根據(jù)馬氏鏈的結(jié)構(gòu)性質(zhì)猜出兩組數(shù)Qij,和{πj},驗(yàn)證是否滿(mǎn)足(1)：如果滿(mǎn)足，則該馬氏鏈?zhǔn)强赡骀溓乙詛πj}為平穩(wěn)分布，而Qij為逆鏈的轉(zhuǎn)移概率.6第6頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Continuous-TimeMarkovChains設(shè){X(t):-∞<t<∞}是不可約的遍歷的連續(xù)時(shí)間馬氏鏈，轉(zhuǎn)移率為qij,i≠j設(shè)(pi

>0)為它的唯一的平穩(wěn)分布:仍假定過(guò)程從-∞開(kāi)始，則在有窮時(shí)間t鏈處于平穩(wěn)態(tài):P{X(t)=j}=pj令Y(t)=X(τ-t)，則以下命題成立:7第7頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月ReversedContinuous-TimeMarkovChainsProposition2:{Y(t)}也是連續(xù)時(shí)間馬氏鏈，轉(zhuǎn)移率為:{Y(t)}和正向鏈有相同的平穩(wěn)分布:{pj}

Remark:逆向鏈離開(kāi)i的轉(zhuǎn)移率等于正向鏈離開(kāi)i的轉(zhuǎn)移率：這是GBE的另一表達(dá)形式:逆向鏈的“出”＝正向鏈的“入”8第8頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Reversibility–Continuous-TimeChains馬氏鏈稱(chēng)為可逆的如果：或等價(jià)的:此即DBETheorem3:如果有一組正數(shù){pj},其和為1且滿(mǎn)足:

則:{pj}是唯一的平穩(wěn)分布該馬氏鏈?zhǔn)强赡娴?第9頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Birth-DeathProcess轉(zhuǎn)移率為滿(mǎn)足DBEProof:GBEwithS={0,1,…,n}give:M/M/1,M/M/c,M/M/∞是可逆馬氏鏈01n+1n2SSc10第10頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月重要的定理Theorem4:對(duì)有轉(zhuǎn)移率qij.的不可約馬氏鏈，如果存在:一組轉(zhuǎn)移率,滿(mǎn)足∑j≠i

φij=∑j≠i

qij,i≥0,和一組正數(shù){pj},其和為1,使得以下方程成立:則:φij是逆向鏈的轉(zhuǎn)移率,且{pj}是正向和逆向鏈的相同的平穩(wěn)分布上述定理用來(lái)解馬氏鏈：guess兩組數(shù)φij和{pj}，驗(yàn)證上述條件11第11頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(tài)轉(zhuǎn)移率圖是樹(shù)結(jié)構(gòu)的馬氏鏈Theorem5:狀態(tài)轉(zhuǎn)移率圖有樹(shù)結(jié)構(gòu)的馬氏鏈?zhǔn)强赡娴?0126374512第12頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Burke’s定理假設(shè)N(t)為一生滅過(guò)程,有平穩(wěn)分布{pj}N(t)的向上跳躍點(diǎn)為到達(dá)點(diǎn).

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

N(t)包括了系統(tǒng)的到達(dá)和離開(kāi)過(guò)程ArrivalsDepartures13第13頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Burke’sTheorem如λj=λ,forall,則到達(dá)為Poisson.這時(shí)稱(chēng)此過(guò)程為(λ,μj)-過(guò)程M/M/1,M/M/c,M/M/∞為(λ,μj)-過(guò)程Poissonarrivals→LAA:

Foranytimet,futurearrivalsareindependentof{X(s):s≤t}(λ,μj)-processatsteadystateisreversible:forwardandreversedchainsarestochasticallyidenticalArrivalprocessesoftheforwardandreversedchainsarestochasticallyidenticalArrivalprocessofthereversedchainisPoissonwithrateλThearrivalepochsofthereversedchainarethedepartureepochsoftheforwardchainDepartureprocessoftheforwardchainisPoissonwithrateλ14第14頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Burke’sTheoremReversedchain:arrivalsaftertimetareindependentofthechainhistoryuptotimet(LAA)Forwardchain:departurespriortotimetandfutureofthechain{X(s):s≥t}areindependent15第15頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Burke’sTheoremTheorem10:ConsideranM/M/1,M/M/c,orM/M/∞systemwitharrivalrateλ.Supposethatthesystemstartsatsteady-state.Then:ThedepartureprocessisPoissonwithrateλAteachtimet,thenumberofcustomersinthesystemisindependentofthedeparturetimespriortotFundamentalresultforstudyofnetworksofM/M/*queues,whereoutputprocessfromonequeueistheinputprocessofanother16第16頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Single-ServerQueuesinTandemCustomersarriveatqueue1accordingtoPoissonprocesswithrateλ.Servicetimesexponentialwithmean1/μi.Assumeservicetimesofacustomerinthetwoqueuesareindependent.Assumeρi=λ/μi<1WhatisthejointstationarydistributionofN1andN2–numberofcustomersineachqueue?Result:insteadystatethequeuesareindependentandPoissonStation1Station217第17頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Single-ServerQueuesinTandemQ1isaM/M/1queue.AtsteadystateitsdepartureprocessisPoissonwithrateλ.ThusQ2isalsoM/M/1.Marginalstationarydistributions:Tocompletetheproof:establishindependenceatsteadystateQ1atsteadystate:attimet,N1(t)isindependentofdeparturespriortot,whicharearrivalsatQ2uptot.ThusN1(t)andN2(t)independent:Lettingt→∞,thejointstationarydistributionPoissonStation1Station218第18頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Networksof./M/1QueuesNetworkofKnodes;Nodeiis./M/1-FCFSqueuewithservicerateμi

ExternalarrivalsindependentPoissonprocessesγi:rateofexternalarrivalsatnodeiMarkovianrouting:customercompletingserviceatnodei

isroutedtonodejwithprobabilityrijorexitsthenetworkwithprobabilityri0=1-∑jrijRoutingmatrixR=[rij]irreducibleexternalarrivalseventuallyexitthesystem19第19頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Jackson定理當(dāng)以(n1,…,nK)為系統(tǒng)狀態(tài)時(shí)，指數(shù)的服務(wù)時(shí)間和Poisson到達(dá)使其具有Markov性質(zhì).如果至少存在一個(gè)節(jié)點(diǎn)有正的外部Poisson到達(dá)率，同時(shí)至少有一個(gè)節(jié)點(diǎn)使得客戶(hù)能從該節(jié)點(diǎn)離開(kāi)網(wǎng)絡(luò)，則排隊(duì)網(wǎng)絡(luò)是穩(wěn)定的，存在穩(wěn)定的節(jié)點(diǎn)吞吐率.解上述多維馬氏鏈的思路：Guess逆過(guò)程的狀態(tài)轉(zhuǎn)移率和馬氏鏈的平穩(wěn)分布驗(yàn)證滿(mǎn)足前面提到的條件我們猜測(cè)逆過(guò)程也是一個(gè)排隊(duì)網(wǎng)絡(luò)，一切都和原網(wǎng)絡(luò)反過(guò)來(lái).20第20頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Networksof./M/1QueuesDefinition:AJacksonnetworkisthecontinuoustimeMarkovchain{N(t)},withN(t)=(N1(t),…,NK(t))thatdescribestheevolutionofthepreviouslydefinednetworkPossiblestates:n=(n1,n2,…,nK),ni=1,2,…,i=1,2,..,KForanystatendefinethefollowingoperators:TransitionratesfortheJacksonnetwork:

Whileq(n,m)=0forallotherstatesm21第21頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Jackson’sTheoremforOpenNetworksλi:totalarrivalrateatnodeiOpennetwork:forsomenodej:γj>0Linearsystemhasauniquesolutionλ1,λ2,…,λKTheorem13:ConsideraJacksonnetwork,whereρi=λ/μi<1,foreverynodei.Thestationarydistributionofthenetworkis

whereforeverynodei=1,2,…,K22第22頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Jackson’sTheorem(proof)GuessthereverseMarkovchainanduseTheorem4Claim:ThenetworkreversedintimeisaJacksonnetworkwiththesameservicerates,whilethearrivalratesandroutingprobabilitiesareVerifythatforanystatesnandm≠n,

Needtoproveonlyform=Ain,Din,Tijn.Weshowtheproofforthefirsttwocases–thethirdissimilar

23第23頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Jackson’sTheorem(proofcont.)Finally,verifythatforanystaten:Thus,weneedtoshowthat∑iγi=∑iλiri024第24頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Non-PoissonInternalFlowsExample:Singlequeuewithμ>>λ,whereuponservicecompletionacustomerisfedbackwithprobabilityp≈1,joiningtheendofthequeueThetotalarrivalprocessdoesnothaveindependentinterarrivaltimes:Ifanarrivaloccursattimet,thereisaveryhighprobabilitythatafeedbackarrivalwillfollowin(t,t+δ]Atarbitraryt,theprobabilityofanarrivalin(t,t+δ]issmallsinceλissmallArrivalprocessconsistsofbursts,eachbursttriggeredbyasinglecustomerarrivalPoissonQueuePoisson25第25頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月例題3.12兩類(lèi)sessions共享一條有m個(gè)相同容量的獨(dú)立電路的傳輸線(xiàn)類(lèi)型1sessions的到達(dá)率為λ1,長(zhǎng)度為1/μ1類(lèi)型1sessions的到達(dá)率為λ1,長(zhǎng)度為1/μ1類(lèi)2sessions的到達(dá)率為λ2,長(zhǎng)度為1/μ2我們關(guān)心blocking概率(電路交換系統(tǒng)最重要的性能指標(biāo))需計(jì)算傳輸線(xiàn)上有n1個(gè)類(lèi)型1session和n2個(gè)類(lèi)型2sessions概率

P(n1,n2),當(dāng)μ1和μ2不相等時(shí)，需建立多維馬氏鏈26第26頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月例題3.13類(lèi)型1session有較高優(yōu)先級(jí)類(lèi)型2session只允許最多使用k條電路,即使到達(dá)時(shí)有閑電路27第27頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月3.4.4多維馬氏鏈如果：滿(mǎn)足DBE平穩(wěn)分布有乘積形式不可約截?cái)鄤t截?cái)噫溣虚]形式的解證明:對(duì)原馬氏鏈的平穩(wěn)解在截?cái)嗖糠诌m當(dāng)歸一化,截?cái)噫溔詽M(mǎn)足DBE見(jiàn)(3.39)和(3.40)28第28頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月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–trackthenumberofcustomersineachsystem29第29頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Example: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:30第30頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Stationarydistribution:DetailedBalanceEquations:VerifythattheMarkovchainisreversible–KolmogorovcriterionExample:TwoIndependentM/M/1Queues0212223201112131001020300313233331第31頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月Example:TwoIndependentM/M/1Queues0212223201112131001020300313233332第32頁(yè)，課件共38頁(yè)，創(chuàng)作于2023年2月TruncationofaReversibleMarkovChainTheorem9:{X(t)}reversibleMarkovprocesswithstatespaceS,andstationarydistribut