可逆馬氏鏈中文

1、可逆馬氏鏈中文1第1頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二TopicsTime-Reversal of Markov ChainsReversibilityTruncating a Reversible Markov ChainBurkes TheoremQueues in Tandem2第2頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二Time-Reversed Markov Chains假定Xn: n=0,1, 為遍歷的馬氏鏈, 轉(zhuǎn)移概率為 Pi,j , 唯一的平穩(wěn)分布為 (j 0). 假定過程從開始, 即Xn:n=,n, -1, 0,1, , 則系統(tǒng)在時(shí)刻n的

2、狀態(tài)概率 PrXn=j= 平穩(wěn)分布j .任意 0，定義 Yn=X-n, 過程Yn是原馬氏鏈的時(shí)間逆轉(zhuǎn)過程. 可以證明Yn也是馬氏鏈(見書215頁),轉(zhuǎn)移概率為而且和Xn 有相同的平穩(wěn)分布 j 通過逆向鏈可看出正向鏈的某些性質(zhì)；3第3頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二Reversibility馬氏鏈Xn稱為可逆的如果正向鏈和逆向鏈有相等的轉(zhuǎn)移概率:Pi,j=Pi,j*, 等價(jià)于Xn 滿足DBE.定理1. 如果能找到一組正數(shù) j, 其和為1,且滿足: iPi,j=jPj,i, 則該馬氏鏈?zhǔn)强赡娴那乙詊為平穩(wěn)分布.4第4頁，共38頁，2022年，5月20日，7點(diǎn)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點(diǎn)18分，星期二重要定理Theorem 1:對(duì)轉(zhuǎn)移概率為 Pij.的不可約馬氏鏈，如果存在:一組轉(zhuǎn)移概率 Qij, 滿足 j Qij=1, i 0, 和一組整數(shù) j, 其和為1, 并且下式成立則:Qij 為其逆向鏈的轉(zhuǎn)移概率j 同時(shí)既是正向鏈也是逆向鏈的平穩(wěn)分布Remark: 上述定理常用來計(jì)算平穩(wěn)分布：根據(jù)馬氏

4、鏈的結(jié)構(gòu)性質(zhì)猜出兩組數(shù)Qij,和j,驗(yàn)證是否滿足(1)：如果滿足，則該馬氏鏈?zhǔn)强赡骀溓乙詊為平穩(wěn)分布，而Qij 為逆鏈的轉(zhuǎn)移概率. 6第6頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二Continuous-Time Markov Chains設(shè)X(t): - t 0) 為它的唯一的平穩(wěn)分布:仍假定過程從-開始，則在有窮時(shí)間t鏈處于平穩(wěn)態(tài): PX(t)=j=pj令Y(t)=X(-t)，則以下命題成立:7第7頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二Reversed Continuous-Time Markov ChainsProposition 2:Y(t) 也是連續(xù)時(shí)間

5、馬氏鏈，轉(zhuǎn)移率為:Y(t) 和正向鏈有相同的平穩(wěn)分布: pj Remark: 逆向鏈離開i 的轉(zhuǎn)移率等于正向鏈離開i 的轉(zhuǎn)移率：這是GBE的另一表達(dá)形式:逆向鏈的“出”正向鏈的“入”8第8頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二Reversibility Continuous-Time Chains馬氏鏈稱為可逆的如果： 或等價(jià)的:此即DBETheorem 3: 如果有一組正數(shù)pj,其和為 1 且滿足:則:pj 是唯一的平穩(wěn)分布該馬氏鏈?zhǔn)强赡娴?第9頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二Birth-Death Process轉(zhuǎn)移率為滿足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點(diǎn)18分，星期二重要的定理Theorem 4: 對(duì)有轉(zhuǎn)移率qij. 的不可約馬氏鏈，如果存在:一組轉(zhuǎn)移率 , 滿足 ji ij=ji qij, i 0, 和一組正數(shù)pj, 其和為 1, 使得以下方程成立:則:ij 是逆向鏈的轉(zhuǎn)移率,且pj 是正向和逆向鏈的相同的平穩(wěn)分布上述定理用來解馬氏鏈：guess兩組數(shù)ij和pj，驗(yàn)證上述條件11第11頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二狀態(tài)轉(zhuǎn)移率圖是樹結(jié)構(gòu)的馬氏鏈Theorem

7、 5:狀態(tài)轉(zhuǎn)移率圖有樹結(jié)構(gòu)的馬氏鏈?zhǔn)强赡娴?0126374512第12頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二Burkes 定理假設(shè)N(t)為一生滅過程,有平穩(wěn)分布pjN(t) 的向上跳躍點(diǎn)為到達(dá)點(diǎn).N(t) 的向下跳躍點(diǎn)為離開點(diǎn).N(t) 包括了系統(tǒng)的到達(dá)和離開過程ArrivalsDepartures13第13頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二Burkes Theorem如j=, for all,則到達(dá)為Poisson. 這時(shí)稱此過程為 (, 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點(diǎn)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點(diǎn)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點(diǎn)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點(diǎn)18分，星期二例題3.12 兩類sessions 共享一條有m個(gè)相同容量的獨(dú)立電路的傳輸線類型1 sessions的到達(dá)率為1,長度為1/1類型1 sessions的到達(dá)率為1,長度為1/1類2 sessions的到達(dá)率為2,長度為1/2我們關(guān)心blocking 概率(電路交換

15、系統(tǒng)最重要的性能指標(biāo))需計(jì)算傳輸線上有n1個(gè)類型1 session 和 n2 個(gè)類型2 sessions 概率 P(n1,n2), 當(dāng) 1和 2 不相等時(shí)，需建立多維馬氏鏈26第26頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二例題3.13類型1 session 有較高優(yōu)先級(jí)類型2 session 只允許最多使用k條電路,即使到達(dá)時(shí)有閑電路27第27頁，共38頁，2022年，5月20日，7點(diǎn)18分，星期二3.4.4多維馬氏鏈如果： 滿足DBE 平穩(wěn)分布有乘積形式 不可約截?cái)鄤t截?cái)噫溣虚]形式的解 證明:對(duì)原馬氏鏈的平穩(wěn)解在截?cái)嗖糠诌m當(dāng)歸一化,截?cái)噫溔詽M足DBE 見(3.39)和(3.4

16、0)28第28頁，共38頁，2022年，5月20日，7點(diǎn)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點(diǎn)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點(diǎn)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點(diǎn)18分，星期二Example: Two Indep

20、endent M/M/1 Queues0212223201112131001020300313233332第32頁，共38頁，2022年，5月20日，7點(diǎn)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