资源描述：
《可逆马氏链(中文.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、NetworkingTheory&FundamentalsLecture5September,20031TopicsTime-ReversalofMarkovChainsReversibilityTruncatingaReversibleMarkovChainBurke’sTheoremQueuesinTandem2Time-ReversedMarkovChains假定{Xn:n=0,1,…}为遍历的马氏链,转移概率为Pi,j,唯一的平稳分布为(πj>0).假定过程从－∞开始,即{Xn:n=…,－n,…,-1,0,1,…},则系统在时刻n的状态概率P
2、r{Xn=j}=平稳分布πj.任意τ>0，定义Yn=Xτ-n,过程{Yn}是原马氏链的时间逆转过程.可以证明{Yn}也是马氏链(见书215页),转移概率为而且和{Xn}有相同的平稳分布πj通过逆向链可看出正向链的某些性质；3Reversibility马氏链{Xn}称为可逆的如果正向链和逆向链有相等的转移概率:Pi,j=Pi,j*,等价于{Xn}满足DBE.定理1.如果能找到一组正数{πj},其和为1,且满足:πiPi,j=πjPj,i,则该马氏链是可逆的且以{πj}为平稳分布.4Reversibility–Discrete-TimeChainsExa
3、mple:Discrete-timebirth-deathprocessesarereversible,sincetheysatisfytheDBE5重要定理Theorem1:对转移概率为Pij.的不可约马氏链，如果存在:一组转移概率Qij,满足∑jQij=1,i≥0,和一组整数{πj},其和为1,并且下式成立则:Qij为其逆向链的转移概率{πj}同时既是正向链也是逆向链的平稳分布Remark:上述定理常用来计算平稳分布：根据马氏链的结构性质猜出两组数Qij,和{πj},验证是否满足(1)：如果满足，则该马氏链是可逆链且以{πj}为平稳分布，而Qij
4、为逆链的转移概率.6Continuous-TimeMarkovChains设{X(t):-∞0)为它的唯一的平稳分布:仍假定过程从-∞开始，则在有穷时间t链处于平稳态:P{X(t)=j}=pj令Y(t)=X(τ-t)，则以下命题成立:7ReversedContinuous-TimeMarkovChainsProposition2:{Y(t)}也是连续时间马氏链，转移率为:{Y(t)}和正向链有相同的平稳分布:{pj}Remark:逆向链离开i的转移率等于正向链离开i的转移率：这
5、是GBE的另一表达形式:逆向链的“出”＝正向链的“入”8Reversibility–Continuous-TimeChains马氏链称为可逆的如果：或等价的:此即DBETheorem3:如果有一组正数{pj},其和为1且满足:则:{pj}是唯一的平稳分布该马氏链是可逆的9Birth-DeathProcess转移率为满足DBEProof:GBEwithS={0,1,…,n}give:M/M/1,M/M/c,M/M/∞是可逆马氏链01n+1n2SSc10重要的定理Theorem4:对有转移率qij.的不可约马氏链，如果存在:一组转移率,满足∑j≠iφij
6、=∑j≠iqij,i≥0,和一组正数{pj},其和为1,使得以下方程成立:则:φij是逆向链的转移率,且{pj}是正向和逆向链的相同的平稳分布上述定理用来解马氏链：guess两组数φij和{pj}，验证上述条件11状态转移率图是树结构的马氏链Theorem5:状态转移率图有树结构的马氏链是可逆的.0126374512Burke’s定理假设N(t)为一生灭过程,有平稳分布{pj}N(t)的向上跳跃点为到达点. N(t)的向下跳跃点为离开点. N(t)包括了系统的到达和离开过程ArrivalsDepartures13Burke’sTheorem如λj=λ
7、,forall,则到达为Poisson.这时称此过程为(λ,μj)-过程M/M/1,M/M/c,M/M/∞为(λ,μj)-过程Poissonarrivals→LAA: Foranytimet,futurearrivalsareindependentof{X(s):s≤t}(λ,μj)-processatsteadystateisreversible:forwardandreversedchainsarestochasticallyidenticalArrivalprocessesoftheforwardandreversedchainsarestoc
8、hasticallyidenticalArrivalprocessofthereversedchainisP
