可逆马氏链中文

1、可逆马氏链中文1第1页，共38页，2022年，5月20日，7点18分，星期二TopicsTime-Reversal of Markov ChainsReversibilityTruncating a Reversible Markov ChainBurkes TheoremQueues in Tandem2第2页，共38页，2022年，5月20日，7点18分，星期二Time-Reversed Markov Chains假定Xn: n=0,1, 为遍历的马氏链, 转移概率为 Pi,j , 唯一的平稳分布为 (j 0). 假定过程从开始, 即Xn:n=,n, -1, 0,1, , 则系统在时刻n的

2、状态概率 PrXn=j= 平稳分布j .任意 0，定义 Yn=X-n, 过程Yn是原马氏链的时间逆转过程. 可以证明Yn也是马氏链(见书215页),转移概率为而且和Xn 有相同的平稳分布 j 通过逆向链可看出正向链的某些性质；3第3页，共38页，2022年，5月20日，7点18分，星期二Reversibility马氏链Xn称为可逆的如果正向链和逆向链有相等的转移概率:Pi,j=Pi,j*, 等价于Xn 满足DBE.定理1. 如果能找到一组正数 j, 其和为1,且满足: iPi,j=jPj,i, 则该马氏链是可逆的且以j为平稳分布.4第4页，共38页，2022年，5月20日，7点18分，星期二R

3、eversibility Discrete-Time ChainsExample: Discrete-time birth-death processes are reversible, since they satisfy the DBE5第5页，共38页，2022年，5月20日，7点18分，星期二重要定理Theorem 1:对转移概率为 Pij.的不可约马氏链，如果存在:一组转移概率 Qij, 满足 j Qij=1, i 0, 和一组整数 j, 其和为1, 并且下式成立则:Qij 为其逆向链的转移概率j 同时既是正向链也是逆向链的平稳分布Remark: 上述定理常用来计算平稳分布：根据马氏

4、链的结构性质猜出两组数Qij,和j,验证是否满足(1)：如果满足，则该马氏链是可逆链且以j为平稳分布，而Qij 为逆链的转移概率. 6第6页，共38页，2022年，5月20日，7点18分，星期二Continuous-Time Markov Chains设X(t): - t 0) 为它的唯一的平稳分布:仍假定过程从-开始，则在有穷时间t链处于平稳态: PX(t)=j=pj令Y(t)=X(-t)，则以下命题成立:7第7页，共38页，2022年，5月20日，7点18分，星期二Reversed Continuous-Time Markov ChainsProposition 2:Y(t) 也是连续时间

5、马氏链，转移率为:Y(t) 和正向链有相同的平稳分布: pj Remark: 逆向链离开i 的转移率等于正向链离开i 的转移率：这是GBE的另一表达形式:逆向链的“出”正向链的“入”8第8页，共38页，2022年，5月20日，7点18分，星期二Reversibility Continuous-Time Chains马氏链称为可逆的如果： 或等价的:此即DBETheorem 3: 如果有一组正数pj,其和为 1 且满足:则:pj 是唯一的平稳分布该马氏链是可逆的9第9页，共38页，2022年，5月20日，7点18分，星期二Birth-Death Process转移率为满足DBEProof: GB

6、E with S =0,1,n give:M/M/1, M/M/c, M/M/是可逆马氏链01n+1n2SSc10第10页，共38页，2022年，5月20日，7点18分，星期二重要的定理Theorem 4: 对有转移率qij. 的不可约马氏链，如果存在:一组转移率 , 满足 ji ij=ji qij, i 0, 和一组正数pj, 其和为 1, 使得以下方程成立:则:ij 是逆向链的转移率,且pj 是正向和逆向链的相同的平稳分布上述定理用来解马氏链：guess两组数ij和pj，验证上述条件11第11页，共38页，2022年，5月20日，7点18分，星期二状态转移率图是树结构的马氏链Theorem

7、 5:状态转移率图有树结构的马氏链是可逆的.0126374512第12页，共38页，2022年，5月20日，7点18分，星期二Burkes 定理假设N(t)为一生灭过程,有平稳分布pjN(t) 的向上跳跃点为到达点.N(t) 的向下跳跃点为离开点.N(t) 包括了系统的到达和离开过程ArrivalsDepartures13第13页，共38页，2022年，5月20日，7点18分，星期二Burkes Theorem如j=, for all,则到达为Poisson. 这时称此过程为 (, j)-过程M/M/1, M/M/c, M/M/为(, j)-过程Poisson arrivals LAA: Fo

8、r any time t, future arrivals are independent of X(s): st(, j)-process at steady state is reversible: forward and reversed chains are stochastically identicalArrival processes of the forward and reversed chains are stochastically identicalArrival process of the reversed chain is Poisson with rate Th

9、e arrival epochs of the reversed chain are the departure epochs of the forward chainDeparture process of the forward chain is Poisson with rate 14第14页，共38页，2022年，5月20日，7点18分，星期二Burkes TheoremReversed chain: arrivals after time t are independent of the chain history up to time t (LAA)Forward chain: d

10、epartures prior to time t and future of the chain X(s): st are independent15第15页，共38页，2022年，5月20日，7点18分，星期二Burkes TheoremTheorem 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 ti

11、me t, the number of customers in the system is independent of the departure times prior to tFundamental result for study of networks of M/M/* queues, where output process from one queue is the input process of another16第16页，共38页，2022年，5月20日，7点18分，星期二Single-Server Queues in TandemCustomers 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=/i0Linear system has a unique solution 1, 2, KTheorem 13: Consider a Jackson network, where i=/i , where upon service completion a

13、customer is fed back with probability p 1, joining the end of the queueThe total arrival process does not have independent interarrival times:If an arrival occurs at time t, there is a very high probability that a feedback arrival will follow in (t, t+At arbitrary t, the probability of an arrival in

14、 (t, t+ is small since is smallArrival process consists of bursts, each burst triggered by a single customer arrivalPoissonQueuePoisson25第25页，共38页，2022年，5月20日，7点18分，星期二例题3.12 两类sessions 共享一条有m个相同容量的独立电路的传输线类型1 sessions的到达率为1,长度为1/1类型1 sessions的到达率为1,长度为1/1类2 sessions的到达率为2,长度为1/2我们关心blocking 概率(电路交换

15、系统最重要的性能指标)需计算传输线上有n1个类型1 session 和 n2 个类型2 sessions 概率 P(n1,n2), 当 1和 2 不相等时，需建立多维马氏链26第26页，共38页，2022年，5月20日，7点18分，星期二例题3.13类型1 session 有较高优先级类型2 session 只允许最多使用k条电路,即使到达时有闲电路27第27页，共38页，2022年，5月20日，7点18分，星期二3.4.4多维马氏链如果： 满足DBE 平稳分布有乘积形式 不可约截断则截断链有闭形式的解 证明:对原马氏链的平稳解在截断部分适当归一化,截断链仍满足DBE 见(3.39)和(3.4

16、0)28第28页，共38页，2022年，5月20日，7点18分，星期二Multidimensional Markov ChainsTheorem 8: X1(t), X2(t): independent Markov chainsXi(t): reversibleX(t), with X(t)=(X1(t), X2(t): vector-valued stochastic processX(t) is a Markov chainX(t) is reversibleMultidimensional Chains:Queueing system with two classes of custo

17、mers, each having its own stochastic properties track the number of customers from each classStudy the “joint” evolution of two queueing systems track the number of customers in each system29第29页，共38页，2022年，5月20日，7点18分，星期二Example: Two Independent M/M/1 QueuesTwo independent M/M/1 queues. The arrival

18、 and service rates at queue i are i and i respectively. Assume 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” distributionGeneralizes for any number K of independent queues, M/M/1, M/M/c, or M/M/. If pi(ni) is the st

19、ationary distribution of queue i:30第30页，共38页，2022年，5月20日，7点18分，星期二Stationary distribution:Detailed Balance Equations:Verify that the Markov chain is reversible Kolmogorov criterionExample: Two Independent M/M/1 Queues0212223201112131001020300313233331第31页，共38页，2022年，5月20日，7点18分，星期二Example: Two Indep

20、endent M/M/1 Queues0212223201112131001020300313233332第32页，共38页，2022年，5月20日，7点18分，星期二Truncation of a Reversible Markov ChainTheorem 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: Remark: This is the conditional probability that, in steady-state, the original process is at state j, given that it is somewhere in EProof: Verify that:33第33页，共38页，2