Lecture5_2 Time-Reversal of Markov Chains

1、1可逆马氏链Time-Reversal of Markov ChainsLecture 5 TopicsnTime-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= 平稳

2、分布j .n任意 0，定义 Yn=X-n过程Yn是原马氏链的时间逆转过程. n可以证明Yn也是马氏链(见书215页),转移概率为n而且和Xn 有相同的平稳分布 j n通过逆向链可看出正向链的某些性质；*,0,1,.jjiijiPPi j*000jjiiijijjijiiiiPPPTime-Reversed Markov Chains*000jjiiijijjijiiiiPPPYn的转移概率证明：kkmmmmiXiXiXjXP,221kkmmmkkmmmmiXiXiXPiXiXiXjXP,221221，iXiXiXPiXPiXjXiXiXPiXjXPmkkmmmmmkkmmmm12211221,

3、iXPjXiXPjXPmmmm11ijijpPpReversibility（可逆性）n随机过程X(t) 称作可逆的（reversible ），如果n(X(t1), X(t2), X(tn) 与 (X(-t1), X(-t2), X(-tn) n对任意, t1, tn有相同的概率分布。n马尔可夫链Xn 是可逆的等价于前向链的转移概率与逆向链的转移概率相等或等价于细节平衡方程成立 可逆*ijijPP,0,1,.iijjjiPPi jReversibility 离散时间马氏链n定理 1: 如果存在一组正数 j, 其和为1， 并满足:n那么1.j 是唯一的平稳分布2.马尔可夫链是可逆的n例: 离散时间

4、生灭过程是可逆的，其满足细节平衡方程,0,1,.iijjjiPPi jTime-离散时间马氏链 (Revisited)n定理 2: 不可约马氏链的转移概率为Pij. 若存在:n一组转移概率Qij, 满足 j Qij=1, i 0, n一组正数j, 其和为1, 并满足n则:nQij 是逆向链的状态转移概率nj 是前向链和逆向链的平稳分布nRemark: 上述定理常用来计算平稳分布：根据马氏链的结构性质猜出两组数Qij,和j,验证是否满足(1)：如果满足，则该马氏链是可逆链且以j为平稳分布，而Qij 为逆链的转移概率.,0,1,.(1)iijjjiPQi j定理2+ n对转移率为 qij.的不可约

5、马氏链，如果:n存在一组正数pj, 其和为1, nq*ij=pjqji/pi满足n jq*ij= jqij (1)n则(1) q*ij为逆向链的转移率 (2) pj是正向链也是逆向链的平稳分布n上述定理常用来计算平稳分布：根据马氏链的结构猜出pj,然后计算q*ij, 验证是否满足(1); 如果满足则pj为它们共同的平稳分布. 连续时间马尔可夫链nX(t): - t 0) 等价于:nProcess in steady state e.g., started at t =-: ,0,1,.jjiiijijijpqpqjlimPr( )Pr( )|(0)tjXX ttXpjij可逆的连续时间马尔可夫

6、链n逆向马尔可夫链逆向马尔可夫链Y(t), 其中其中Y(t)=X(-t), 任意任意0 1.Y(t) 是连续时间马尔可夫链，具有状态转移率是连续时间马尔可夫链，具有状态转移率:2.Y(t) 与前向链有相同的平稳分布与前向链有相同的平稳分布 pjn注意注意: 逆向链中从状态逆向链中从状态i离开的转移率等于前向链中进入状态离开的转移率等于前向链中进入状态i的转的转移率。移率。*,0,1,.,jjiijip qqi jijp*,0,1,.jjiiijj ij iijijij ij iiip qpqqqippReversibility 连续时间马尔可夫链n马氏链马氏链X(t) 是可逆的，等价于前向链与

7、逆向链的转移率相同，是可逆的，等价于前向链与逆向链的转移率相同， 或等价于或等价于细节平衡方程成立细节平衡方程成立 马氏链可逆马氏链可逆n定理定理 3: 如果存在一组正数如果存在一组正数 pj, 其和为其和为1并满足并满足:n则则:1.pj 是唯一的平稳分布是唯一的平稳分布2.马氏链是可逆的马氏链是可逆的*,ijijqq,0,1,.,iijjjip qp qi jij,0,1,.,iijjjip qp qi jijn生-灭过程马氏链是可逆的.nM/M/1,M/M/m,M/M/m/m,M/M/等排队系统内的平稳客户数过程是可逆的.n状态转移图为树形结构的离散马氏链是可逆的.n状态转移率图为树形结

8、构的连续马氏链是可逆的.例: Birth-Death ProcessnTransitions only between neighboring statesnDetailed Balance EquationsnProof: GBE with S =0,1,n give:M/M/1, M/M/c, M/M/01n+1n201n1n121nn,1,1,0, | 1i iii iiijqqqij11,0,1,.nnnnppn110101nnjjiiijnnnnji nji np qp qpp SSc逆向的连续时间马尔可夫链(Revisited)n定理定理 4: 不可约的连续时间马氏链，转移率不可约

9、的连续时间马氏链，转移率 为为qij. 如果存在如果存在:n一组转移率一组转移率ij, 满足满足 ji ij=ji qij, i 0, 并且并且n一组正数一组正数pj, 其和为其和为1, 使得使得n则则:nij 是逆向链的转移率是逆向链的转移率npj 是前向链和逆向链唯一的平稳分布是前向链和逆向链唯一的平稳分布n注注: Use to find the stationary distribution, by guessing the transition probabilities of the reversed chain even if the process is not reversib

10、le,0,1,.,iijjjipp qi jijReversibility: Trees（树状结构）定理定理5:n对于一个马氏链形成的图对于一个马氏链形成的图, 节点表示状态节点表示状态, 任意任意qij0, 任意节点之间存在任意节点之间存在有向弧有向弧ijn不可约马氏链的状态转移率满足不可约马氏链的状态转移率满足qij0 qji0若形成的图为一棵树（无环），则马氏链是可逆的若形成的图为一棵树（无环），则马氏链是可逆的注注:nSufficient condition for reversibilitynGeneralization of one-dimensional birth-death

11、process01q0126374510q12q21q16q61q23q32q67q76qKolmogorovs Criterion (连续马是链)n细节平衡方程基于平稳分布和状态转移率决定了一个马氏链是否细节平衡方程基于平稳分布和状态转移率决定了一个马氏链是否可逆。可逆。应该能够推到一个仅仅依赖于转移率来判断马氏链是否可逆的标应该能够推到一个仅仅依赖于转移率来判断马氏链是否可逆的标准准!n定理定理 6: 一个连续时间马氏链是可逆的，等价于一个连续时间马氏链是可逆的，等价于 :对任意有限状态序列对任意有限状态序列i1, i2, in, 及任意及任意nnnIntuition: Product o

12、f transition rates along any loop i1i2ini1 is equal to the product of transition rates along the same loop traversed in the reverse direction i1ini2i1 1 22 311113 22 1nnnnn ni ii iiii ii ii ii ii iq qqqq qq qKolmogorovs Criterion (proof)定理定理 6证明证明:n必要性必要性: 马氏链是可逆的，则细节平衡方程成立马氏链是可逆的，则细节平衡方程成立n充分性充分性:

13、固定两个状态固定两个状态i1=i, in=j 对所有其他状态对所有其他状态i2, in-1 情况下的式子情况下的式子求和，有求和，有n取极限取极限n1 22 12 33 21 22 311113 22 11111122311nnnnn nnnn nnni ii ii ii ii ii iiii ii ii ii ii iniini ini ii iPPPPP PPPP PP PPPPP22 3113 2211,nnnni ii iijjiijj ii ii iijjiijjiP PPPP PP PPPP P11limlimnnijjiijjijjiijinnPPPPPP例: M/M/2 Que

14、ue with Heterogeneous ServersnM/M/2 队列队列. 服务器服务器 A 与与 B 分别有不同的服务速率分别有不同的服务速率A 与与B. n当系统空时当系统空时, 到达以概率到达以概率进入进入A ，以概率，以概率1-进入进入B. n否则否则, 队列头部客户会选择首先空闲的服务器。队列头部客户会选择首先空闲的服务器。nNeed to keep track of which server is busy when there is 1 customer in the system. Denote the two possible states by: 1A and 1B

15、.nReversibility: we only need to check the loop 01A21B0: nReversible if and only if =1/2.01A1B(1) AB23BAABAB0,11 ,2 2,11 ,00,11 ,2 2,11 ,0(1 )A AB BABB BA ABAq q q qq q q q 例: M/M/2 Queue with Heterogeneous Servers01A1B(1) AB23BAABABS1S2S322,2,3,.nnABppn1001121110102220()2(1)()()()2()(1)2ABAAABAABBA

16、BABABBBABAABABABABppppppppppppppp 1201102(1)112ABABnnABABABppppp Burkes 定理n假设N(t)为一生灭过程,有平稳分布pjnN(t) 的向上跳跃点为到达点.N(t) 的向下跳跃点为离开点.N(t) 包括了系统的到达和离开过程ArrivalsDeparturesBurkes 定理n如j=, for all,则到达为Poisson. n这时称此过程为 (, j)-过程nM/M/1, M/M/c, M/M/为(, j)-过程nPoisson到达 LAA: 对任意时间t, 将来的到达独立于时刻t之前系统的状态X(s): stn(, j

17、)-过程在平稳态是可逆的: 前向链与逆向链有相同分布前向链的离开过程与逆向链的到达过程相同。 n arrival epochs of the reversed chain are the departure epochs of the forward chainDeparture process of the forward chain is Poisson with rate Burkes 定理nReversed chain: arrivals after time t are independent of the chain history up to time t (LAA)nForwa

18、rd chain: departures prior to time t and future of the chain X(s): st are independentttttBurkes Theoremn定理定理 7: 考虑考虑M/M/1, M/M/c, or M/M/ 系统，其到达率为系统，其到达率为 . 假定假定系统从平稳状态开始，那么系统从平稳状态开始，那么:1.离开过程为离开过程为Poisson过程，参数为过程，参数为 2.在每个时刻在每个时刻 t,系统中的客户数独立于系统中的客户数独立于t时刻之前的离开过程时刻之前的离开过程nFundamental result for stud

19、y of networks of M/M/* queues, where output process from one queue is the input process of anotherBurkes定理nBurkes定理说两件事情:n处于平稳态的M/M/排队系统的离开过程是Poisson，而且参数为.n处于平稳态的M/M/排队系统内客户数N(t)独立于t以前,即(0,t)时间内的离开过程n应用Burkes定理可以推出级联队列的平稳客户数分布有乘积形式: P(n1,n2)=P(n1)P(n2).Burkes定理的证明n因为平稳因为平稳M/M/(,)排队系统内客户数过程是可逆的排队系统内

20、客户数过程是可逆的,所所以逆过程以逆过程N( -T)和正过程有相同的转移率和平稳分布和正过程有相同的转移率和平稳分布, 逆逆过程仍是一个过程仍是一个M/M/排队系统排队系统n因为正过程状态因为正过程状态-1对应逆过程状态对应逆过程状态+1,所以正过程的离开是所以正过程的离开是逆过程的到达逆过程的到达,所以它是所以它是Poisson().n正过程正过程t以前的离开对应逆过程以前的离开对应逆过程T-t以后的到达以后的到达, 但未来但未来Poisson到达独立于现在系统内客户数到达独立于现在系统内客户数;所以所以, 正过程在时刻正过程在时刻t时系统内客户数独立于以前的离开过程时系统内客户数独立于以前

21、的离开过程.nFigure 3.31 (a) Forward system number of arrivals, number of departures, and occupancy during 0, T.nFigure 3.31 (b) Reversed system number of arrivals, number of departures, and occupancy during 0,T.n根据根据Burkes定理定理,不能从客户接连不断的离开推断系统内有不能从客户接连不断的离开推断系统内有大量的客户大量的客户,因为这两者之间没相关性因为这两者之间没相关性.(反直觉反直觉,

22、 counterintuitive) 例题3.18 级联的M/M/1系统n图3.33为级联的2个M/M/1系统. n假定1: 客户按参数的 Poisson过程到达第一个队列;在第一个队列接受服务后进入第2个队列接受服务.n假定2: 客户在两个队列要求的服务时间是独立的指数分布的时间,参数分别为1和2.n假定2消除了3.6节指出的级联传输线形成的相关性.n我们要分析在平稳态下队列1内客户数为n,队列2内客户数为m的概率: P(n,m).Single-Server Queues in TandemnCustomers arrive at queue 1 according to Poisson p

23、rocess with rate . nService times exponential with mean 1/i. Assume service times of a customer in the two queues are independent. nAssume i=/i 两个队列的平稳客户数是独立.n= PN1(t)=n, N2(t)=m= 1n(1-1)2m(1-2).n如果排队系统组成的网络是有向无环图, 每个系统的客户服务时间是指数分布, 外部到达是Poisson, 则每个内部排队系统的到达过程是Poisson.Queues in TandemnTheorem 8: Ne

24、twork consisting of K single-server queues 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 dis

25、tribution of queue i is that of an isolated M/M/1 queue with arrival and service rates and i11(,)(1),0,1,.;1,.,iKnKiiiip nnniK ()(1),0,1,.iniiiiip nn Queues in Tandem: State-Dependent Service RatesnTheorem 12: Network consisting of K queues in tandem. Service times at queue i exponential with rate i

26、(ni) when there are ni customers in the queue independent of service times at any queue ji. Arrivals at the 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:

27、 ./M/c and ./M/ queues nIf queue i is ./M/, then:11(,)(),0,1,.;1,.,KKiiiip nnp nniK/( /)(),0,1,.!iiniiiiip nenn Multidimensional Markov ChainsTheorem 8: nX1(t), X2(t): independent Markov chainsnXi(t): reversiblenX(t), with X(t)=(X1(t), X2(t): vector-valued stochastic processX(t) is a Markov chainX(t

28、) 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 “joint” evolution of two queueing systems track the number of customers in each systemExample: Two Independent M/M/

29、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, and n2 at queue 2, at steady-staten“Product-form” distributionnGeneralizes for any number K of independ

30、ent queues, M/M/1, M/M/c, or M/M/. If pi(ni) is the stationary distribution of queue i:121211221122(,)(1)(1)()()nnp n np np n 121122(,)()()()KKKp n nnp n p npnnStationary distribution:nDetailed Balance Equations:Verify that the Markov chain is reversible Kolmogorov criterionExample: Two Independent

31、M/M/1 Queues121122121122(,)11nnp n n 112112212212(1,)(,)(,1)(,)p nnp n np n np n n22222222222222222222222202122232111111011121311111110010203011111103132333111111Example: Two Independent M/M/1 Queues22222222222222222222222202122232111111011121311111110010203011111103132333111111Truncation of a Rever

32、sible Markov ChainnTheorem 9: X(t) reversible Markov process with state space S, and stationary distribution pj: jS. Truncated to a set ES, such that the resulting chain Y(t) is irreducible. Then, Y(t) is reversible and has stationary distribution: nRemark: This is the conditional probability that,

33、in steady-state, the original process is at state j, given that it is somewhere in EnProof: Verify that:,jjkk EppjEp,;1jijjiiijjiijjjiiijkkk Ek Ejjj Ej Ekk Eppp qp qqqp qp qi jS ijpppppTwo examples:n例例1 M/M/m/m是是M/M/的的截断截断,S=0,1,m,n G=1+ + m/m!, p(n)=(n/n!)/G, =(/)n例例2 M/M/1/K是是M/M/1的截断的截断(习题习题3.21)

34、n 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: Two Queues with Joint Buffer nThe two independent M/M/1 queues of the previous example share a common buffer of size B arrival that finds B customers waiting is blockednState

35、 space restricted to nDistribution of truncated chain:nNormalizing:Theorem specifies joint distribution up to the normalization constantMCalculation of normalization constant is often tedious222222112222221111112222220212110111211111001020301111031322311212(,):(1)(1)En nnnB12121212(,)(0,0), (,)nnp n npn nE 1212112(,)(0,0)nnn nEp State diagram for B =2多维马氏链多维马氏链-在电路交换网中的应用在电路交换网中的应用Example：3.12n考虑具有考虑具有m条独立电路，每条电路都具有相同的传输能力条独立电路，每条电路都具有相同的传输能力n系统中存在两类会话，到达率分别是