可逆马氏链(中文).ppt

1、1,可逆马氏链,Topics,Time-Reversal of Markov Chains Reversibility Truncating a Reversible Markov Chain Burkes Theorem Queues in Tandem,Time-Reversed Markov Chains,假定Xn: n=0,1, 为遍历的马氏链, 转移概率为 Pi,j , 唯一的平稳分布为 (j 0). 假定过程从开始, 即Xn:n=,n, -1, 0,1, , 则系统在时刻n的状态概率 PrXn=j= 平稳分布j . 任意 0，定义 Yn=X-n, 过程Yn是原马氏链的时间逆转过程.

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

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

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

5、的: 此即DBE Theorem 3: 如果有一组正数pj,其和为 1 且满足:则: pj 是唯一的平稳分布 该马氏链是可逆的,Birth-Death Process,转移率为 满足DBE Proof: GBE with S =0,1,n give: M/M/1, M/M/c, M/M/是可逆马氏链,重要的定理,Theorem 4: 对有转移率qij. 的不可约马氏链，如果存在: 一组转移率 , 满足 ji ij=ji qij, i 0, 和 一组正数pj, 其和为 1, 使得以下方程成立: 则: ij 是逆向链的转移率,且 pj 是正向和逆向链的相同的平稳分布 上述定理用来解马氏链：gues

6、s两组数ij和pj，验证上述条件,状态转移率图是树结构的马氏链,Theorem 5:状态转移率图有树结构的马氏链是可逆的.,Burkes 定理,假设N(t)为一生灭过程,有平稳分布pj N(t) 的向上跳跃点为到达点.N(t) 的向下跳跃点为离开点.N(t) 包括了系统的到达和离开过程,Burkes Theorem,如j=, for all,则到达为Poisson. 这时称此过程为 (, j)-过程 M/M/1, M/M/c, M/M/为(, j)-过程 Poisson arrivals LAA: For any time t, future arrivals are independent

7、of X(s): st (, j)-process at steady state is reversible: forward and reversed chains are stochastically identical Arrival processes of the forward and reversed chains are stochastically identical Arrival process of the reversed chain is Poisson with rate The arrival epochs of the reversed chain are

8、the departure epochs of the forward chain Departure process of the forward chain is Poisson with rate ,Burkes Theorem,Reversed chain: arrivals after time t are independent of the chain history up to time t (LAA) Forward chain: departures prior to time t and future of the chain X(s): st are independe

9、nt,Burkes Theorem,Theorem 10: Consider an M/M/1, M/M/c, or M/M/ system with arrival rate . Suppose that the system starts at steady-state. Then: The departure process is Poisson with rate At each time t, the number of customers in the system is independent of the departure times prior to t Fundament

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

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

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

13、e independent and,Poisson,Station 1,Station 2,Single-Server Queues in Tandem,Q1 is a M/M/1 queue. At steady state its departure process is Poisson with rate . Thus Q2 is also M/M/1. Marginal stationary distributions: To complete the proof: establish independence at steady state Q1 at steady state: a

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

15、: Network 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: At steady state the queues are independent; the

16、 distribution of queue i is that of an isolated M/M/1 queue with arrival and service rates and i,Queues in Tandem: State-Dependent Service Rates,Theorem 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 indepen

17、dent 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 Examples: ./M/c and ./M/ queues If queue i is ./M/, then:,Multi

18、dimensional Markov Chains,Theorem 8: X1(t), X2(t): independent Markov chains Xi(t): reversible X(t), with X(t)=(X1(t), X2(t): vector-valued stochastic process X(t) is a Markov chain X(t) is reversible Multidimensional Chains: Queueing system with two classes of customers, each having its own stochas

19、tic properties track the number of customers from each class Study the “joint” evolution of two queueing systems track the number of customers in each system,Example: Two Independent M/M/1 Queues,Two independent M/M/1 queues. The arrival and service rates at queue i are i and i respectively. Assume

20、i= i/i1. (N1(t), N2(t) is a Markov chain. Probability of n1 customers at queue 1, and n2 at queue 2, at steady-state “Product-form” distribution Generalizes 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:,Stationary distribution: De

21、tailed Balance Equations: Verify that the Markov chain is reversible Kolmogorov criterion,Example: Two Independent M/M/1 Queues,Example: Two Independent M/M/1 Queues,Truncation of a Reversible Markov Chain,Theorem 9: X(t) reversible Markov process with state space S, and stationary distribution pj:

22、jS. Truncated to a set ES, such that the resulting chain Y(t) is irreducible. Then, Y(t) is reversible and has stationary distribution: Remark: This is the conditional probability that, in steady-state, the original process is at state j, given that it is somewhere in E Proof: Verify that:,Two examp

23、les:,例1 M/M/m/m是M/M/的截断,S=0,1,m, G=1+ + m/m!, p(n)=(n/n!)/G, =(/) 例2 M/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: Two Queues with Joint Buffer,The two independent M/M/1 queues of the previous example share a common

24、buffer of size B arrival that finds B customers waiting is blocked State space restricted to E=(n1, n2)| n1+n2=B Distribution of truncated chain: Normalizing: Theorem specifies joint distribution up to the normalization constant Calculation of normalization constant is often tedious,State diagram for B =2,多维马氏链-在电路交换网中的应用,Example：3.12,考