可逆马氏链中文

《可逆马氏链中文》由会员分享，可在线阅读，更多相关《可逆马氏链中文（41页珍藏版）》请在装配图网上搜索。

1、可逆马氏链可逆马氏链1TopicsnTime-Reversal of Markov ChainsnReversibilitynTruncating a Reversible Markov ChainnBurkes TheoremnQueues in TandemTime-Reversed Markov Chainsn假定Xn:n=0,1,为遍历的马氏链,转移概率为 Pi,j,唯一的平稳分布为(j 0).假定过程从开始,即Xn:n=,n,-1,0,1,则系统在时刻n的状态概率 PrXn=j=平稳分布j.n任意 0，定义 Yn=X-n,过程Yn是原马氏链的时间逆转过程.n可以证明Yn也是马氏链，转

2、移概率为n而且和Xn 有相同的平稳分布 j n通过逆向链可看出正向链的某些性质；Time-Reversed Markov ChainsProof of Proposition 1:Reversibilityn马氏链Xn称为可逆的如果正向链和逆向链有相等的转移概率:Pi,j=Pi,j*,等价于Xn 满足DBE.n定理1.如果能找到一组正数 j,其和为1,且满足:iPi,j=jPj,i,则该马氏链是可逆的且以j为平稳分布.nReversibility Discrete-Time ChainsnExample:Discrete-time birth-death processes are rever

3、sible,since they satisfy the DBE重要定理nTheorem 1:对转移概率为 Pij.的不可约马氏链，如果存在:n一组转移概率 Qij,满足 j Qij=1,i 0,n和一组整数 j,其和为1,并且下式成立n则:nQij 为其逆向链的转移概率nj 同时既是正向链也是逆向链的平稳分布nRemark:上述定理常用来计算平稳分布：根据马氏链的结构性质猜出两组数Qij,和j,验证是否满足(1)：如果满足，则该马氏链是可逆链且以j为平稳分布，而Qij 为逆链的转移概率.Continuous-Time Markov Chainsn设X(t):-t 0)为它的唯一的平稳分布:n

4、仍假定过程从-开始，则在有穷时间t链处于平稳态:PX(t)=j=pjn令Y(t)=X(-t)，则n以下命题成立:Reversed Continuous-Time Markov ChainsnProposition 2:1.Y(t)也是连续时间马氏链，转移率为:2.Y(t)和正向链有相同的平稳分布:pj nRemark:逆向链离开i 的转移率等于正向链离开i 的转移率：n这是GBE的另一表达形式:逆向链的“出”正向链的“入”Reversibility Continuous-Time Chainsn马氏链称为可逆的如果：n或等价的:此即DBEnTheorem 3:如果有一组正数pj,其和为 1 且

5、满足:则:1.pj 是唯一的平稳分布2.该马氏链是可逆的Birth-Death Processn转移率为n满足DBEnProof:GBE with S=0,1,n give:M/M/1,M/M/c,M/M/是可逆马氏链01n+1n2SSc重要的定理nTheorem 4:对有转移率qij.的不可约马氏链，如果存在:n一组转移率,满足 ji ij=ji qij,i 0,和n一组正数pj,其和为 1,使得以下方程成立:n则:nij 是逆向链的转移率,且npj 是正向和逆向链的相同的平稳分布n上述定理用来解马氏链：guess两组数ij和pj，验证上述条件状态转移率图是树结构的马氏链Theorem 5:

6、状态转移率图有树结构的马氏链是可逆的.01263745Burkes 定理n假设N(t)为一生灭过程,有平稳分布pjnN(t)的向上跳跃点为到达点.N(t)的向下跳跃点为离开点.N(t)包括了系统的到达和离开过程ArrivalsDeparturesBurkes Theoremn如j=,for all,则到达为Poisson.n这时称此过程为(,j)-过程nM/M/1,M/M/c,M/M/为(,j)-过程nPoisson arrivals LAA:For any time t,future arrivals are independent of X(s):stn(,j)-process at st

7、eady state is reversible:forward and reversed chains are stochastically identicalnArrival processes of the forward and reversed chains are stochastically identicalnArrival process of the reversed chain is Poisson with rate nThe arrival epochs of the reversed chain are the departure epochs of the for

8、ward chainnDeparture process of the forward chain is Poisson with rate Burkes TheoremnReversed chain:arrivals after time t are independent of the chain history up to time t(LAA)nForward chain:departures prior to time t and future of the chain X(s):st are independentBurkes TheoremnTheorem 10:Consider

9、 an M/M/1,M/M/c,or M/M/system with arrival rate.Suppose that the system starts at steady-state.Then:1.The departure process is Poisson with rate 2.At each time t,the number of customers in the system is independent of the departure times prior to tnFundamental result for study of networks of M/M/*qu

10、eues,where output process from one queue is the input process of anothernBurkes定理说两件事情:n处于平稳态的M/M/排队系统的离开过程是Poisson，而且参数为.n处于平稳态的M/M/排队系统内客户数N(t)独立于t以前,即(0,t)时间内的离开过程n应用Burkes定理可以推出级联队列的平稳客户数分布有乘积形式:P(n1,n2)=P(n1)P(n2).Burkes定理nFigure 3.31 (a)Forward system number of arrivals,number of departures,an

11、d occupancy during 0,T.nFigure 3.31 (b)Reversed system number of arrivals,number of departures,and occupancy during 0,T.n根据根据Burkes定理定理,不能从客户接连不断的离开推断系统内有不能从客户接连不断的离开推断系统内有大量的客户大量的客户,因为这两者之间没相关性因为这两者之间没相关性.(反直觉反直觉,counterintuitive)Single-Server Queues in Tandem（级联）nCustomers arrive at queue 1 accord

12、ing to Poisson process with rate.nService times exponential with mean 1/i.Assume service times of a customer in the two queues are independent.nAssume i=/i1nWhat is the joint stationary distribution of N1 and N2 number of customers in each queue?Result:in steady state the queues are independent and

13、PoissonStation 1Station 2Single-Server Queues in TandemnQ1 is a M/M/1 queue.At steady state its departure process is Poisson with rate.Thus Q2 is also M/M/1.nMarginal stationary distributions:To complete the proof:establish independence at steady statenQ1 at steady state:at time t,N1(t)is independen

14、t of departures prior to t,which are arrivals at Q2 up to t.Thus N1(t)and N2(t)independent:nLetting t,the joint stationary distributionPoissonStation 1Station 2n如果排队系统组成的网络是有向无环图,每个系统的客户服务时间是指数分布,外部到达是Poisson,则每个内部排队系统的到达过程是Poisson.Queues in TandemnTheorem 11:Network consisting of K single-server qu

15、eues in tandem.Service times at queue i exponential with rate i,independent of service times at any queue ji.Arrivals at the first queue are Poisson with rate.The stationary distribution of the network is:nAt steady state the queues are independent;the distribution of queue i is that of an isolated

16、M/M/1 queue with arrival and service rates and iQueues in Tandem:State-Dependent Service RatesnTheorem 12:Network consisting of K queues in tandem.Service times at queue i exponential with rate i(ni)when there are ni customers in the queue independent of service times at any queue ji.Arrivals at the

17、 first queue are Poisson with rate.The stationary distribution of the network is:where pi(ni)is the stationary distribution of queue i in isolation with Poisson arrivals with rate nExamples:./M/c and./M/queues nIf queue i is./M/,then:Multidimensional Markov ChainsTheorem 8:nX1(t),X2(t):independent M

18、arkov chainsnXi(t):reversiblenX(t),with X(t)=(X1(t),X2(t):vector-valued stochastic processX(t)is a Markov chainX(t)is reversibleMultidimensional Chains:nQueueing system with two classes of customers,each having its own stochastic properties track the number of customers from each classnStudy the“joi

19、nt”evolution of two queueing systems track the number of customers in each systemExample:Two Independent M/M/1 QueuesnTwo independent M/M/1 queues.The arrival and service rates at queue i are i and i respectively.Assume i=i/i1.n(N1(t),N2(t)is a Markov chain.nProbability of n1 customers at queue 1,an

20、d n2 at queue 2,at steady-staten“Product-form”distributionnGeneralizes for any number K of independent queues,M/M/1,M/M/c,or M/M/.If pi(ni)is the stationary distribution of queue i:nStationary distribution:nDetailed Balance Equations:Verify that the Markov chain is reversible Kolmogorov criterionExa

21、mple:Two Independent M/M/1 Queues02122232011121310010203003132333Example:Two Independent M/M/1 Queues02122232011121310010203003132333Truncation of a Reversible Markov ChainnTheorem 9:X(t)reversible Markov process with state space S,and stationary distribution pj:jS.Truncated to a set ES,such that th

22、e resulting chain Y(t)is irreducible.Then,Y(t)is reversible and has stationary distribution:nRemark:This is the conditional probability that,in steady-state,the original process is at state j,given that it is somewhere in EnProof:Verify that:Two examples:n例例1 M/M/m/m是是M/M/的的截断截断,S=0,1,m,n G=1+m/m!,n

23、 p(n)=(n/n!)/G,=(/)n例例2 M/M/1/K是是M/M/1的截断的截断(习题习题3.21)n M/M/1有平稳分布有平稳分布n(1-),n截断链的状态集为截断链的状态集为S=0,1,K,G=n(1-)=1-K+1,n截断链的平稳分布为截断链的平稳分布为:p(n)=n(1-)/G=n(1-)/(1-K+1).Example:Two Queues with Joint Buffer nThe two independent M/M/1 queues of the previous example share a common buffer of size B arrival th

24、at finds B customers waiting is blockednState space restricted to nE=(n1,n2)|n1+n2=BnDistribution of truncated chain:nNormalizing:Theorem specifies joint distribution up to the normalization constantMCalculation of normalization constant is often tedious02120111210010203003132231 State diagram for B

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

26、别为1/1和和1/2的指数分布。的指数分布。n求系统在稳态时的封锁概率求系统在稳态时的封锁概率例题3.12（Contd.）n两类两类sessions 共享一条有共享一条有m个电路的传输线个电路的传输线,n类型类型1 sessions的到达率为的到达率为1,长度为长度为1/1,n类型类型2 sessions的到达率为的到达率为2,长度为长度为1/2,n我们关心我们关心blocking 概率概率(电路交换系统电路交换系统QoS):n需计算传输线上有需计算传输线上有n1个类型个类型1 session 和和 n2个类型个类型2 session的概率的概率,P(n1,n2),n10,n20,n1+n2m

27、 进一步计算进一步计算blocking 概率概率=P(n1,n2),求和在集合求和在集合 (n1,n2)|n1+n2=mn当当1=2 时，系统可以用时，系统可以用M/M/m/m队列来模拟，其中到达率为队列来模拟，其中到达率为1+2n当当 1和和 2不相等时需建立多维马氏链不相等时需建立多维马氏链.例题3.12 独立的M/M/的截断n截断的状态集截断的状态集S=(n1,n2),0n1,n2m,n1+n2m.n用定理用定理9可以得到截断链的平稳分布和阻塞概率可以得到截断链的平稳分布和阻塞概率（式（式3.39，3.40）例题3.13n类型类型1 session 可使用所有可使用所有m条电路条电路.n类型类型2 session 最多允许使用最多允许使用k条电路条电路,即使即使session到达时到达时m条电路中还有闲条电路中还有闲电路电路.相当于为类型相当于为类型1 sesson预留预留m-k条电路条电路(reservation).nBlocking 条件条件:类型类型1：m-kn1m&n2=m-n1 类型类型2：0n1m&n2=mink,m-n1例题3.13:状态集为:0n1m&0 n2k,n1+n2m.n例题3.13也是两个独立的M/M/的截断n平稳分布:n计算阻塞概率的公式（见185页），即分别计算