隨機過程與排隊論

隨機過程與排隊論計算機科學與工程學院顧小豐Email：guxf@10九月20242024/9/10計算機科學與工程學院顧小豐30－2上一講內(nèi)容回顧離散參數(shù)馬氏鏈齊次馬氏鏈的性質(zhì)鏈初始分布、絕對分布、極限分布遍歷性平穩(wěn)性2024/9/10計算機科學與工程學院顧小豐30－3本講主要內(nèi)容齊次馬氏鏈狀態(tài)的分類互通首達常返與非常返正常返與零常返狀態(tài)空間分解不可約馬氏鏈狀態(tài)的周期性2024/9/10計算機科學與工程學院顧小豐30－4§3.3齊次馬氏鏈狀態(tài)的分類一、互通首達

如果存在某一個n≥1，使得pij(n)＞0，i,jE，則稱從狀態(tài)i可到達狀態(tài)j，記為i→j；否則稱狀態(tài)i不能到達狀態(tài)j，記為i→j，此時對一切n，均有pij(n)＝0。

如果i→j且j→i，則稱狀態(tài)i和j互通，或稱相通，記為i?j。容易證明，互通關系具有以下三個性質(zhì)：

(1)自反性：i?i；

(2)對稱性：若i?j則j?i；

(3)傳遞性：若i?j且j?k，則i?k。2024/9/10計算機科學與工程學院顧小豐30－5首達從狀態(tài)i出發(fā)經(jīng)過n步首次到達狀態(tài)j的時刻Tij＝min{n：X(m)=i,X(m+n)=j,nN}稱為首達時刻。首達時刻是一個隨機變量，它的取值是從狀態(tài)i出發(fā)，使得X(n)＝j的最小正整數(shù)n。自狀態(tài)i出發(fā)經(jīng)過n步首次到達狀態(tài)j的概率

fij(n)＝P{Tij=n|X(m)=i}＝P{X(m+n)=j,X(m+k)j,1k<n|X(m)=i}稱為首達概率。自狀態(tài)i出發(fā)遲早(最終)到達狀態(tài)j的概率定義為2024/9/10計算機科學與工程學院顧小豐30－6返回當j＝i時Tii：表示從狀態(tài)i出發(fā)首次返回i的時刻；

fii(n)：表示從狀態(tài)i出發(fā)經(jīng)過n步首次返回i的概率；

fii：表示從狀態(tài)i出發(fā)遲早返回i的概率。稱為自狀態(tài)i出發(fā)首次到達j的平均時間(平均步數(shù))；稱為自狀態(tài)i出發(fā)首次到達i的平均返回時間(平均返回步數(shù))；2024/9/10計算機科學與工程學院顧小豐30－7定理1對任意i,jE及n1，有證明設系統(tǒng)從狀態(tài)i出發(fā)經(jīng)n步到達狀態(tài)j，則Tij

n，pij(n)＝P{X(n)＝j|X(0)=i}2024/9/10計算機科學與工程學院顧小豐30－8定理2fij＞0

i→j證明

)設fij＞0，因為，所以至少有一個n≥1，使得fij(n)＞0，由定理1得故i→j。)

設i→j，則存在n≥1，使得pij(n)＞0，由定理1得從而fij(1),fij(2),…,fij(n)中至少有一個大于0，所以2024/9/10計算機科學與工程學院顧小豐30－9推論i?j

fij＞0且fij＞02024/9/10計算機科學與工程學院顧小豐30－10狀態(tài)j常返的充分必要條件是；二、常返如果fii＝1，則稱狀態(tài)i是常返狀態(tài)；如果fii＜1，則稱狀態(tài)i是非常返狀態(tài)，或瞬時狀態(tài)。判別常返狀態(tài)的準則：狀態(tài)j非常返的充分必要條件是；若狀態(tài)j是非常返的，則。2024/9/10計算機科學與工程學院顧小豐30－11返回的次數(shù)定義隨機變量則隨機變量表示質(zhì)點到達狀態(tài)j的次數(shù)，有由此可知，表示由j出發(fā)再返回j的平均次數(shù)。當j是常返狀態(tài)時，返回j的次數(shù)是無窮多次；當j是非常返狀態(tài)時，返回j的次數(shù)只能是有限多次。2024/9/10計算機科學與工程學院顧小豐30－12正常返與零常返設i是常返狀態(tài)，fii＝1，如果，稱狀態(tài)i是一個正常返狀態(tài)；如果，稱狀態(tài)i是一個零常返狀態(tài)，或消極常返狀態(tài)。平均返回時間有限平均返回時間無限2024/9/10計算機科學與工程學院顧小豐30－13定理設i是常返狀態(tài)，則i是零常返的充分必要條件是；如果j也是零常返狀態(tài)，則如果i?j，則它們同為常返或非常返；如果它們均為常返時，則它們同為正常返或零常返。歸納i是非常返i是零常返i是正常返2024/9/10計算機科學與工程學院顧小豐30－14三、狀態(tài)空間分解設C是狀態(tài)空間E的一個子集，若C外的任一狀態(tài)不可能從C內(nèi)的任一狀態(tài)到達，即對任意的i

C,j

C，總有pij(n)＝0，則稱C為一個閉集。重要結(jié)論：整個狀態(tài)空間E是最大的閉集；pii＝1的狀態(tài)i稱為吸收狀態(tài)。任何一個吸收狀態(tài)構成最小的單點閉集。所有常返狀態(tài)構成一個閉集；狀態(tài)空間E必可分解為E＝N＋C1＋C2＋…＋Ck＋…其中N為非常返狀態(tài)集合，C1,C2,…,Ck,…是互不相交的常返閉集。這里的“＋”即為集合的并“∪”且兩兩互不相容2024/9/10計算機科學與工程學院顧小豐30－15不可約馬氏鏈一個馬氏鏈，如果除了整個狀態(tài)空間E構成閉集外，不可能再分解出較小的閉集來，則稱此馬氏鏈為不可約馬氏鏈。結(jié)論：馬氏鏈為不可約馬氏鏈的充分必要條件是任何兩個狀態(tài)都相通；一個不可約馬氏鏈，或者沒有非常返狀態(tài)，或者沒有常返狀態(tài)。不可約馬氏鏈是常返的充分必要條件是方程沒有非零的有界解。2024/9/10計算機科學與工程學院顧小豐30－16四、有限馬爾可夫鏈狀態(tài)空間E是有限集合的馬氏鏈稱為有限馬氏鏈。有限馬氏鏈具有如下特點：所有非常返狀態(tài)所組成的集合不可能是閉集；沒有零常返狀態(tài)；必有正常返狀態(tài)；狀態(tài)空間E必可分解為E＝N＋C1＋C2＋…＋Ck其中，N為非常返狀態(tài)集合，C1,C2,…,Ck是互不相交的常返閉集。2024/9/10計算機科學與工程學院顧小豐30－17五、狀態(tài)的周期性

稱d＝GCD{n：pii(n)＞0}為狀態(tài)i的周期。這里，GCD表示最大公約數(shù)。

如果i有周期d＞1，則只有n＝d,2d,…,kd(k為正整數(shù))時，pii(n)＞0；否則，當n不能被d整除時，pii(n)＝0。如果不存在大于1的d，則稱狀態(tài)i是非周期的，記為d=1。對于不可約馬氏鏈，若pii＞0，則此馬氏鏈是非周期的。結(jié)論：如果i?j，則狀態(tài)i和j或者有相同的周期，或者都是非周期的；如果C是一個常返閉集，則C中的每一個狀態(tài)或者都是非周期的，或者都是同周期的；如果馬氏鏈是不可約常返鏈，那么只要有一個是周期為d(d＞1)的狀態(tài)，則狀態(tài)空間E都是周期為d的狀態(tài)。2024/9/10計算機科學與工程學院顧小豐30－18六、極限定理如果j是一個非周期常返狀態(tài)，則如果馬氏鏈是不可約非周期常返鏈，則其中

j＝E(Tjj)。由此定理知：不可約非周期正常返狀態(tài)的齊次馬氏鏈是遍歷馬氏鏈。即且滿足：i)j＝1/j；ii)極限分布{j,jE}是馬氏鏈唯一的平穩(wěn)分布，且。即絕對分布的極限是平穩(wěn)分布.不可約非周期常返鏈是遍歷鏈的充分必要條件是存在平穩(wěn)分布{1/j,jE}，即極限分布。不可約非周期有限馬氏鏈必存在平穩(wěn)分布，且平穩(wěn)分布就是極限分布。2024/9/10計算機科學與工程學院顧小豐30－19例1兩個吸收壁的隨機游動狀態(tài)空間E＝{1,2,3,4}狀態(tài)轉(zhuǎn)移矩陣狀態(tài)轉(zhuǎn)移圖12341qpqp1以狀態(tài)為結(jié)點，以狀態(tài)轉(zhuǎn)移概率為有向邊的權值得到的賦權有向圖。2024/9/10計算機科學與工程學院顧小豐30－20例1(續(xù))p11＝1，f11(1)＝1，f11(n)＝0(n>1)，f11＝1，

1＝1，故狀態(tài)1為吸收狀態(tài)、正常返狀態(tài)；p44＝1，f44(1)＝1，f44(n)＝0(n>1)，f44＝1，

4＝1，故狀態(tài)4為吸收狀態(tài)、正常返狀態(tài)；p22＝0，f22(1)＝0，f22(2)＝pq，f22(n)＝0(n>2)，f22＝pq，故狀態(tài)2為非常返狀態(tài)。

狀態(tài)2和3互通，2?3，具有相同的狀態(tài)性質(zhì)，即狀態(tài)3也為非常返狀態(tài)。從而N＝{2,3}為非常返集；C1＝{1}、C2＝{4}都為正常返集。狀態(tài)空間分解為E＝N＋C1＋C2即 E＝{1,2,3,4}＝{2,3}＋{1}＋{4}2024/9/10計算機科學與工程學院顧小豐30－21例2設齊次馬氏鏈的狀態(tài)空間E＝{1,2,3,4}，狀態(tài)轉(zhuǎn)移圖12341轉(zhuǎn)移矩陣2024/9/10計算機科學與工程學院顧小豐30－22例2(續(xù)1)

由圖可知，對一切n

1，f44(n)＝0，從而，故狀態(tài)4為非常返狀態(tài)；f33(1)＝，f33(n)＝0(n>1)，從而，故狀態(tài)3非常返狀態(tài)；2024/9/10計算機科學與工程學院顧小豐30－23例2(續(xù)2)故狀態(tài)1和2都是正常返狀態(tài)，又d＝1，故都是遍歷態(tài)。

狀態(tài)空間分解為E＝N＋C其中N＝{3,4}為非常返集；C1＝{1,2}為正常返閉集。非周期正常返狀態(tài)2024/9/10計算機科學與工程學院顧小豐30－24例3設齊次馬氏鏈的狀態(tài)空間E＝{0,1,2,…}，轉(zhuǎn)移概率為狀態(tài)轉(zhuǎn)移圖轉(zhuǎn)移矩陣0123…2024/9/10計算機科學與工程學院顧小豐30－25例3(續(xù))對狀態(tài)0故狀態(tài)0為非周期、正常返、遍歷狀態(tài)。又因pi0=，i

E＝{0,1,2,…}，從而狀態(tài)i（i=0,1,2,…）與狀態(tài)0互通，故狀態(tài)i=1,2,3,…與狀態(tài)0有相同的狀態(tài)性質(zhì)，都是非周期、正常返、遍歷狀態(tài)。因此該馬氏鏈為不可約遍歷的齊次馬氏鏈。所有狀態(tài)均為非周期、正常返、遍歷狀態(tài)。2024/9/10計算機科學與工程學院顧小豐30－26例4設齊次馬氏鏈的狀態(tài)空間E＝{1,2,3,4,5,6}，狀態(tài)轉(zhuǎn)移圖16541轉(zhuǎn)移矩陣231112024/9/10計算機科學與工程學院顧小豐30－27例4(續(xù)1)故狀態(tài)1為正常返狀態(tài)，且周期為3.

因為f11(3)＝1，f11(n)＝0（n

3)，1?3?5，從而狀態(tài)3和5與狀態(tài)1有相同的狀態(tài)性質(zhì)，由此可知，C1={1,3,5}是周期為3的正常返閉集。，(n

3)2024/9/10計算機科學與工程學院顧小豐30－28例4(續(xù)2)故狀態(tài)2為正常返狀態(tài)。

該齊次馬氏鏈的狀態(tài)空間分解為E＝N＋C1＋C2其中N＝{4}為非常返集；C1＝{1,3,5}為周期為3的正常返閉集；C2＝{2,6}為非周期、正常返遍歷的閉集。f66(1)>0，故狀態(tài)6為非周期狀態(tài)。

2?6，從而狀態(tài)2與狀態(tài)6有相同的狀態(tài)性質(zhì)，它們都是非周期、正常返、遍歷狀態(tài)，故C2={2,6}是非周期、正常返、遍歷閉集。故狀態(tài)4為非常返狀態(tài)。由于f44(1