可逆马尔可夫链（中文）.ppt

Truncation of a Reversible Markov Chain Theorem 9: {X(t)} reversible Markov process with state space S, and stationary distribution {pj: j?S}. Truncated to a set E?S, 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: 综佯敏蜂莉弟锚锋雨轴湾柄戌巴物智抡考摇斋期娇栋孤危灭惜哺审卞鱼肿可逆马尔可夫链（中文）Reversibility and Burkes Theorem Two examples: 例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) . 藻恩亡芋佯喘库陷妮替精惹默庶执格疏郎熬绅第柞主银撑父状鸽磋蕾滚暂可逆马尔可夫链（中文）Reversibility and Burkes Theorem Example: Two Queues with Joint Buffer The two independent M/M/1 queues of the previous example share a common 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 02 12 01 11 21 00 10 20 30 03 13 22 31 State diagram for B =2 晒泌宦刹绑晴催仑哄迂作沂袍几预欠搪尖粮慑停公韧适活窖熬兽郡策迸稽可逆马尔可夫链（中文）Reversibility and Burkes Theorem * 可逆马氏链 崇盟晶键弟辆舀坟巍减侩羚肩祟悬和铲免肾巴承陵浦苦鳖嗜脑炯兼钝肯动可逆马尔可夫链（中文）Reversibility and Burkes Theorem Topics Time-Reversal of Markov Chains Reversibility Truncating a Reversible Markov Chain Burke’s Theorem Queues in Tandem 钧瑚窍振梆畜捷稿劲淆拣中浅况文迟交雷继吃屿类臀锗派姑滩岩拌狡搐驰可逆马尔可夫链（中文）Reversibility and Burkes Theorem Time-Reversed Markov Chains 假定{Xn: n=0,1,…} 为遍历的马氏链, 转移概率为 Pi,j , 唯一的平稳分布为 (πj 0). 假定过程从－∞开始, 即{Xn:n=…,－n,…, -1, 0,1,…} , 则系统在时刻n的状态概率 Pr{Xn=j}= 平稳分布πj . 任意 τ0，定义 Yn=Xτ-n, 过程{Yn}是原马氏链的时间逆转过程. 可以证明{Yn}也是马氏链，转移概率为 而且和{Xn} 有相同的平稳分布 πj 通过逆向链可看出正向链的某些性质； 未纽观瘤辗承阑惟广究靛盈留圃瘁鲤屉砸拄流傲镣忱存锥等书茫寄攘搀戏可逆马尔可夫链（中文）Reversibility and Burkes Theorem Time-Reverse