電子科技大學(xué)計算機學(xué)院

1、電子科技大學(xué)計算機學(xué)院葉 茂 隨機過程與排隊論-及其在計算機領(lǐng)域中的應(yīng)用學(xué)習(xí)本課程的必要性計算機領(lǐng)域必須的數(shù)學(xué)知識進一深造，科研必須的數(shù)學(xué)基礎(chǔ)本課程目標(biāo)打下在計算機領(lǐng)域內(nèi)研究必須的數(shù)學(xué)基礎(chǔ)。本課程介紹的是隨機過程與排隊論，有非常強的應(yīng)用背景。學(xué)習(xí)數(shù)學(xué)的唯一方法就是扎扎實實學(xué)習(xí)的一些方法和技巧，及推證和估計能力的訓(xùn)練。由于時間限制，本課程只涉及一些基本知識。更多的需要大家自學(xué)本課程安排24學(xué)時左右隨機過程，16學(xué)時左右講述排隊論。我們將盡量涉及到工程應(yīng)用領(lǐng)域。包括遺傳算法，模擬退火算法，圖像處理，計算機網(wǎng)絡(luò)分析等等內(nèi)容將會不定期布置習(xí)題，并作為期末成績的一部份（具體比例待定)。聯(lián)系方式若有任何意

2、見和問題可以通過Email sobolevus聯(lián)系或者電話：81823465 預(yù)約時間本課程通過電子科技大學(xué)教師主頁提供ppt下載。有時候直接板書教學(xué)歡迎大家選修這門課，希望這門課程結(jié)束后，能成為朋友。參考書隨機過程 劉次華 華中科技大學(xué)排隊論 唐應(yīng)輝，唐小我 電子科技大學(xué)*軟計算方法 *遺傳算法*Visual C+圖象處理工程實踐 概率的數(shù)學(xué)理論是本課程的基礎(chǔ)之一，不清楚的請自己找一本這方面的書自學(xué)，現(xiàn)僅介紹幾個概念。以后遇到相關(guān)概念我們會再講。第一章隨機過程的基本概念隨機過程的引入隨機過程的定義隨機過程的分布隨機過程的數(shù)字特征幾種重要的隨機過程隨機過程產(chǎn)生于二十世紀(jì)初，起源于統(tǒng)計物理學(xué)領(lǐng)域

3、，布朗運動和熱噪聲是隨機過程的最早例子。隨機過程理論社會科學(xué)、自然科學(xué)和工程技術(shù)的各個領(lǐng)域中都有著廣泛的應(yīng)用。例如：現(xiàn)代電子技術(shù)、現(xiàn)代通信、自動控制、系統(tǒng)工程的可靠性工程、市場經(jīng)濟的預(yù)測和控制、隨機服務(wù)系統(tǒng)的排隊論、儲存論、生物醫(yī)學(xué)工程、人口的預(yù)測和控制等等。只要研究隨時間變化的動態(tài)系統(tǒng)的隨機現(xiàn)象的統(tǒng)計規(guī)律，就要用到隨機過程的理論。一、隨機過程的定義電話問題設(shè)X(t)表示某電話臺在0,t)時間內(nèi)收到用戶的呼喚次數(shù)。對某個固定的t(0t)，X(t)是一個隨機變量，它可以是任意非負整數(shù)，一個隨機過程。布朗運動懸浮在液體中的微粒由于分子的隨機碰撞而作布朗運動。設(shè)X(t)表示時刻t微粒所處位置的橫座標(biāo)

4、，對某個固定的t(0t)，X(t)是一族隨機變量，即一個隨機過程。熱噪聲電子元件或器件由于內(nèi)部電子的隨機熱運動所引起的端電壓X(t)稱為熱噪聲電壓。對于固定的t0，X(t)是一個隨機變量，一個隨機過程。設(shè)(,F,P)是一個概率空間，T是一個參數(shù)集(TR)，X(t,)，tT，是T上的函數(shù)，如果對于每一個tT，X(t,)是(,F,P)上的隨機變量，則稱隨機變量族X(t,)，tT為定義在(,F,P)上的隨機過程(或隨機函數(shù))。簡記為X(t)，tT，其中t稱為參數(shù)，T稱為參數(shù)集。顯然，隨機過程X(t,)是定義在T上的二元函數(shù)：一方面，當(dāng)tT固定時，X(t,)是定義在上的隨機變量；另一方面，當(dāng)固定時，X

5、(t,)是定義在T上的函數(shù)，稱為隨機過程的樣本函數(shù)。隨機過程在時刻t所取的值X(t)=x稱為時刻t時隨機過程X(t),tT處于狀態(tài)x，隨機過程X(t),tT所有狀態(tài)構(gòu)成的集合稱為狀態(tài)空間，記為E，即：Ex：X(t)=x,tT隨機過程的分類：根據(jù)參數(shù)T及狀態(tài)空間I是可列集或不可列集，可以把隨機過程分為以下四種類型：1、T和I都是可列的2、T非可列，I可列3、T可列，I非可列4、T和I都非可列1，3可稱為隨機序列或時間序列，1，2也可稱為可列過程二 隨機過程的分布和數(shù)字特征設(shè)X(t),tT是一個隨機過程，對任意t1,t2,tnT，n維隨機變量(X(t1),X(t2),X(tn)的聯(lián)合分布函數(shù)F(t

6、1,t2,tn;x1,x2,xn)t1,t2,tnT，PX(t1)x1,X(t2)x2,X(tn)0稱為隨機過程X(t),tTn維分布函數(shù)族顯然，隨機過程X(t),tT分布函數(shù)族F有如下性質(zhì)（1）對稱性 對于t1,t2,tn的任意排列ti1,ti2,tin F(t1,t2,tn;x1,x2,xn)= F(ti1,ti2,tin;xi1,xi2,xin)相容性 當(dāng)mn時 F(t1,t2,tm)= F(t1,tm,tn;x1,x2,xm,).反之，對給定的滿足對稱性和相容性條件的分布函數(shù)族F，是否一定存在一個以F作為分布函數(shù)族的隨機過程呢？Kolmogorov已經(jīng)證明其存在隨機過程X(t),tT的

7、n維特征函數(shù)定義為(t1,t2,tm;u1,u2,un)我們稱(t1,t2,tm;u1,u2,un)，t1,t2,tmT，n1為隨機過程X(t),tT的有限維特征函數(shù)族。例1利用投擲一枚硬幣的試驗，定義隨機過程假定“出現(xiàn)正面”和“出現(xiàn)反面”的概率各為0.5，試求：X(t)的一維分布函數(shù)F(0.5,x)和F(1,x)；X(t)的二維分布函數(shù)F(0.5,1;x,y)。解：(1)由X(t)的定義求得概率分布為：X(0.5)01X(1)-12P0.50.5P0.50.5所以一維分布函數(shù)為：(2)由于擲硬幣試驗是相互獨立的，故(X(0.5),X(1)的聯(lián)合概率密度為：X(1)X(0.5)-1200.25

8、0.2510.250.25所以二維分布函數(shù)為：給定隨機過程X(t),tT，稱m(t)EX(t)，tT為隨機過程X(t),tT的均值函數(shù)(數(shù)學(xué)期望)。若X(t),tT的狀態(tài)空間是離散的，則X(t),tT是離散型隨機變量，X(t)的概率分布為pk(t)PX(t)=Xk，k=1,2,，則若X(t),tT的狀態(tài)空間是連續(xù)的，則X(t),tT是連續(xù)型隨機變量，X(t)的一維概率密度為f(t,x)為，則給定隨機過程X(t),tT， 如果EX2(t)存在稱X(t)為二階矩過程。稱D(t)DX(t)EX(t)m(t)2，tT為隨機過程X(t),tT的方差函數(shù)。顯然，D(t)EX(t)m(t)2EX2(t)m2

9、(t)。稱為隨機過程X(t),tT的均方差函數(shù)(標(biāo)準(zhǔn)方差函數(shù))。若X(t),tT是離散型隨機變量，X(t)的概率分布為pk(t)PX(t)=Xk，k=1,2,，則若X(t),tT是連續(xù)型隨機變量，X(t)的一維概率密度為f(t,x)為，則協(xié)方差函數(shù)和相關(guān)函數(shù)給定隨機過程X(t),tT，稱B(s,t)cov(X(s),X(t)EX(s)m(s)X(t)m(t)為隨機過程X(t),tT的協(xié)方差函數(shù)。顯然，B(s,t)EX(s)X(t)m(s)m(t)，B(t,t)D(t)EX(t)m(t)2。給定隨機過程X(t),tT，稱R(s,t)EX(s)X(t)為隨機過程X(t),tT的相關(guān)函數(shù)。顯然，B(

10、s,t)R(s,t)m(s)m(t)，R(s,t)B(s,t)m(s)m(t)。為隨機過程X(t),tT的相關(guān)系數(shù)。均值函數(shù)m(t)是隨機過程在時刻t的平均值，方差函數(shù)D(t) 是隨機過程在時刻t對均值的偏離程度，而協(xié)方差函數(shù)B(s,t)和R(s,t)相關(guān)函數(shù)反映隨機過程在時刻s,t時的線性相關(guān)程度。給定兩個隨機過程X(t),tT和Y(t),tT，稱BXY(s,t)EX(s)mX(s)Y(t)mY(t)，s,tT為隨機過程X(t),tT和Y(t),tT的互協(xié)方差函數(shù)。其中：mX(s)EX(s)，mY(t)EY(t)。稱RXY(s,t)EX(s)Y(t)為隨機過程X(t),tT和Y(t),tT的

11、互相關(guān)函數(shù)。顯然，BXY(s,t)RXY(s,t)mX(s)mY(t)。如果BXY(s,t)0，等價地RXY(s,t)mX(s)mY(t)，即EX(s)Y(t)EX(s)EY(t)，則稱X(t),tT和Y(t),tT互不相關(guān)。如果隨機過程X(t),tT和Y(t),tT相互獨立，則它們一定互不相關(guān)；反之，如果隨機過程X(t),tT和Y(t),tT互不相關(guān)，一般不能推出它們相互獨立。三、幾種重要的隨機過程1、獨立增量過程2、馬爾可夫過程3、正態(tài)過程和維納過程4、平穩(wěn)過程1. 獨立增量過程設(shè)隨機過程X(t),tT，T0,+)，如果對任意正整數(shù)n2，t1,t2,tnT且t1t20,s+h,t+hTX(

12、t+h)-X(s+h)與X(t)-X(s)有相同的概率分布，則稱X(t),tT為平穩(wěn)獨立增量過程。平穩(wěn)獨立增量過程X(t),tT的增量X(t+)-X(t)，tT,t+T的概率分布僅依賴于而與t無關(guān)，即僅與時間區(qū)間的長度有關(guān)，而與起點無關(guān)，具有平穩(wěn)性，即增量具有平穩(wěn)性。例：X(t)表示懸浮在液面上微粒位置的橫坐標(biāo)，則X(t)是隨機過程。由于微粒的運動是大量分子的隨機碰撞引起的，因此X(t)是平穩(wěn)獨立增量過程。后面提到的微納過程和泊松過程都是平穩(wěn)獨立增量過程2馬爾可夫過程給定隨機過程X(t),tT，如果對于參數(shù)中任意n個時刻ti,i=1,2,n，t1t2tn有PX(tn)xn|X(t1)x1,X(

13、t2)x2,X(tn-1)xn-1PX(tn)xn|X(tn-1)0，W(t)N(0,2t)，0；則稱隨機過程W(t),t0是參數(shù)為2的維納過程(布朗運動)。如果一個試驗E滿足下列條件：在相同的條件下可以重復(fù)進行；每次試驗的結(jié)果不止一個，并且能事先明確知道試驗的所有結(jié)果；一次試驗結(jié)束之前，不能確定哪一個結(jié)果會出現(xiàn)則稱此試驗為隨機試驗。隨機試驗E的每一個最簡單的試驗結(jié)果，稱為樣本點，記為。全體樣本點構(gòu)成的集合，稱為樣本空間，記為。樣本空間的子集組成的集類F，如果滿足：F；若AF，則F;若AiF(i=1,2,)，則 ；那么稱F為隨機事件體(域)或代數(shù)。隨機事件體F 的任意元素A成為隨機事件；近含一

14、個樣本點的事件成為基本事件；樣本空間和F的二元體( ,F)稱為可測空間。設(shè)(,F)是可測空間，如果定義隨機事件體F上的實值集函數(shù)P(A)，AF滿足：0P(A)1，AF；(非負性)P()1；(規(guī)范性)AiF(i=1,2,)，AiAj(ij)，則等式成立。(完全可加性)則稱P為(,F)上的概率測度，簡稱概率。對任意AF，P(A)稱為隨機事件A的概率。樣本空間 、隨機事件體F和概率P組成的三元體(,F,P)稱為概率空間。擲一枚均勻的骰子，觀察出現(xiàn)點數(shù)的隨機試驗E。樣本空間1,2,3,4,5,6；ii，i1,2,6，含有6個樣本點；隨機事件體F由的全體子集(共2664個)構(gòu)成；F上的概率定義為P(A)，k為隨機事件A包含的樣本點數(shù)；(,F,P)為概率空間 。隨機變量及其分布一、隨機變量設(shè)(,F,P)為概率空間，如果定義樣本空間上的一個單值實函數(shù)XX()， ，滿足：X()xF-x+則稱X()為隨機變量。隨機變量縮寫為R.V.。二、分布函數(shù)設(shè)XX()是概率空間(,F,P)上的隨機變量，對任意實數(shù)x，定義函數(shù)F(x)PXx-x+稱為R.V.X的概率分布函