随机过程:指数分布、泊松过程、更新过程(renewal process)+大数定律
筆記主要基于中文版《應用隨機過程 Introduction to Probability Models 》(Sheldon M. Ross),只有非常少的一部分是我自己的注解。寫這個筆記的目的是自己復習用,閱讀需要一定的微積分和概率論基礎。本人為初學者,且全部為自學,如果筆記中有錯誤,歡迎指正。
https://zhuanlan.zhihu.com/p/165909489
提示:概率論和指數分布作為本節的基礎,我把一些重要公式寫在開頭,但是可以直接從泊松過程開始閱讀,在泊松過程中用到相關知識點的時候再回頭閱讀。當然,從頭讀到尾也許理解得更好。
1. 概率論復習
隨機過程是概率論的延申。因為我本科并沒有系統學過概率論,所以有必要把一些概率論常用公式羅列在開頭。
1.1 指數分布及其重要性質
1.2 泊松過程
要理解泊松過程,我們還有一些概念要理清楚。
首先,什么是隨機過程?隨機過程可以看成隨機變量的集合X(t),t∈T{X(t),t\in T}X(t),t∈T,或者說是一連串的隨機變量,T是指標集,t可以理解為時間,也就是某個時刻有著對應的隨機變量取值X(t),X(t)稱為狀態(state)。一個系統,在不同的時刻可能會有不同的狀態,這些狀態是隨機的,你按照時間順序觀察到的狀態就是隨機過程了。
具體一點,你可以想象一個黑盒子,黑盒子里面有個數字,你每隔一段時間打開黑盒子看一下,會看到不同的數字,你把看到的數字按照時間順序記錄下來,就是隨機過程。隨機過程就是假定你觀察到的數字是有規律的,可以用概率論的模型去描述的。
平穩過程保證了隨著時間變動,泊松過程產生的隨機變量是同分布的,而獨立增量過程則保證了隨著時間變動前后過程的獨立性,所以平穩獨立增量就就可以理解成連續情形下的 i.i.d。在隨機過程中,基于平穩獨立增量過程的條件,我們往往可以通過類似在一個小區間 (t,t+h]中發生事件的個數,能夠推出整個隨機過程的信息。
2. 更新過程
Renewal theory is the branch of probability theory that generalizes the Poisson process for arbitrary holding times. Instead of exponentially distributed holding times, a renewal process may have any independent and identically distributed (IID) holding times that have finite mean. A renewal-reward process additionally has a random sequence of rewards incurred at each holding time, which are IID but need not be independent of the holding times.
A renewal process has asymptotic properties analogous to the strong law of large numbers and central limit theorem. The renewal function m(t)m(t)m(t) (expected number of arrivals) and reward function g(t)g(t)g(t) (expected reward value) are of key importance in renewal theory. The renewal function satisfies a recursive integral equation, the renewal equation. The key renewal equation gives the limiting value of the convolution of m′(t)m'(t)m′(t) with a suitable non-negative function. The superposition of renewal processes can be studied as a special case of Markov renewal processes.
Applications include calculating the best strategy for replacing worn-out machinery in a factory and comparing the long-term benefits of different insurance policies. The inspection paradox relates to the fact that observing a renewal interval at time t gives an interval with average value larger than that of an average renewal interval.
一個泊松過程可以分解成一系列 i.i.d 的指數分布隨機變量相加,如果把指數分布換成其他 i.i.d 的分布就得到了更新過程。
更新過程本身是泊松過程的一種擴長,同時更新過程也可以發展出一套更新理論,包括更新方程等。
更新過程(renewal process)是一類隨機過程,是描述元件或設備更新現象的一類隨機過程。
設對某元件的工作進行觀測。假定元件的使用壽命是一隨機變量,當元件發生故障時就進行修理或換上新的同類元件,而且元件的更新是即時的(修理或更換元件所需的時間為零)。如果每次更新后元件的工作是相互獨立且有相同的壽命分布,令N(t)為在區間(0,t]中的更新次數,則稱計數過程{N(t),t≥0}為更新過程。
2.1 N(t)的分布
2.2 更新過程分類
在數學上更新過程可簡單地定義為相鄰兩個點事件(即更新)的間距是相互獨立同分布(但從原點到第一次更新的間距T1可以有不同分布)的計數過程。
根據T1的分布情形更新過程分為以下三類:
- 普通更新過程
- 延遲更新過程
- 平衡更新過程
更新過程也可用過程的事件間距序列{Tn,n≥1}給定,這時N(t)和Tn有如下關系:
其中
是第n次更新時間(n≥1,再定義S0=0)。
對于普通更新過程,Sn是n個相互獨立同分布的非負隨機變量之和,因此在數學上更新過程也可以看做是一類特殊的獨立隨機變量和。
2.2.1 普通更新過程(ordinary renewal process)
一類特殊的延遲更新過程。
指所有更新間距T1,T2,T3,…都具有相同分布的更新過程,有時也簡稱更新過程。
2.2.2 延遲更新過程(delayed renewal process)
亦稱變形更新過程。一種更新過程,指允許第一個更新間距T1(即從原點到第一次更新的間距)的分布G和其后的更新間距T2,T3,…的(共同)分布F相異的更新過程。
這類過程產生的背景和得名的原因如下:設想對一個元件更新模型開始觀測的時刻t=0并不恰好是一個新元件開始工作的時刻,因而過程第一個元件的壽命(從開始觀測時算起)分布G和新元件的壽命分布F一般是不相同的。由于在上述模型中是當一個元件已經工作了一段時間才開始觀測的,所以人們稱之為延遲更新過程。因為普通更新過程和平衡更新過程都可看做延遲更新過程的特殊情形,故也有人把延遲更新過程稱為一般更新過程。
2.2.3 平衡更新過程(equilibrium renewal process)
一類特殊的延遲更新過程。它的第一個更新間距T1有分布
這里A(t)和Y(t)分別是過程在時刻t的年齡和剩余壽命(參見“年齡”和“剩余壽命”)。
2.2.4 交替更新過程(alternating renewal process)
如果考慮更換時間,即考慮機器的開與關兩種狀態,稱作交替更新過程。設系統最初是開的,持續時間是Z1,而后關閉,時間是Y1,之后再打開,時間為Z2,又關閉,時間為Y2……交替進行。假設(Zn,Yn),n>=1是獨立同分布的。
一類特殊的兩狀態馬爾可夫更新過程。其特征是兩類型的更新區間交替出現。確切地說,交替更新過程就是非負隨機向量序列{(Zn,Yn),n≥1},其中各(Zn,Yn)是獨立同分布的(因而隨機變量序列{Zn}和{Yn}也各自是獨立同分布的),但Zn和Yn(對于任一正整數n)可以是相依的。在元件更新模型中,若更新時間不恒等于零而是一個隨機變量,令Zn和Yn分別表示第n個元件的使用壽命和它的更新時間,人們就得到一個交替更新過程(參見“馬爾可夫更新過程”)。
2.2.5 一些說明
所謂更新過程就是更新
間隔雖然是i.i.d 但是可以服從一般分布(包括指數分布)的泊松計數過程。
我們一般把更新過程的更新間隔的均值命名為μ\muμ,把更新過程的均值命名為更新函數m(t)。
1/μ1/\mu1/μ我們稱為更新速率。
2.3 更新定理
2.3.1 更新基本定理:
更新數與時間之比趨近于更新速率。
另外更新函數與時間之比也趨近于更新速率。
這里的趨近是說當時間趨于無窮的時候。
2.3.2 關鍵更新定理:
一個黎曼可積的函數與更新函數的增量的卷積等于該函數在正區間的積分乘以更新速率。
定義:格點更新過程:更新只在一個正數的正整數(周期)的倍數時刻發生的更新過程。否則叫做非格點的更新過程。
非格點的更新過程有如下定理:
非格點的更新過程的差分與時間之比趨近于更新速率。
格點的更新過程有如下定理:
在極限時刻發生的更新數與周期之比趨近于更新速率。
所以可以看出更新過程的定理基本都是和更新基本定理類似的。
但是最有用的定理還是關鍵更新定理。
2.4 補充一些
更新函數是n個更新間隔的和的分布的(對n的)累加。
dm(y)dm(y)dm(y)是更新發生在(y,y+dy)(y,y+dy)(y,y+dy)期間的概率。
F(t?y)dyF(t-y)dyF(t?y)dy是更新間隔大于t-y的概率。
所以dm(y)F(t?y)dydm(y)F(t-y)dydm(y)F(t?y)dy就是dFSN(t)dF_{S_{N(t)}}dFSN(t)??的概率,也就是第N(t)個更新發生在t時刻的概率。
我們定義,在t時間內發生了N(t)N(t)N(t)個更新,那么SN(t)S_{N(t)}SN(t)?(即第N(t)個更新發生的時刻)與t的時間差叫做“零件”的年齡。把SN(t)+1S_{N(t)+1}SN(t)+1?(即第N(t)+1N(t)+1N(t)+1個更新發生的時刻)與t的時間差叫做“零件”的剩余壽命。
“零件”的年齡和剩余壽命在時間趨于無窮大的時候有相同的分布,且都等于int0tF(y)dy/μint_{0}^{t}F(y)dy/\muint0t?F(y)dy/μ
2.5 更新過程的推廣
2.5.1 交錯更新過程:
就是忙時和停時更替進行的一種更新過程,我們把一個忙時和緊接著的一個停時叫做一個循環。
則機器在時刻t是處于忙時的概率(隨時間)趨近于
EZn/(EZn+EYn)=EZn/EXnE{Z_{n}}/(E{Z_{n}}+E{Y_{n}})=E{Z_{n}}/E{X_{n}}EZn?/(EZn?+EYn?)=EZn?/EXn?
這里XnX_{n}Xn?表示第n個循環的長度。ZnZ_{n}Zn?表示第n個忙時的長度。YnY_{n}Yn?表示第n個停時的長度。
2.5.2 延遲更新過程:
也稱為一般更新過程,就是初次間隔并不和其后的間隔分布相同。
前面出現過的這個分布函數:int0tF(y)dy/muint_{0}^{t}F(y)dy/muint0t?F(y)dy/mu稱為平衡分布函數。
如果首次間隔分布服從平衡分布函數,則這樣的一般更新過程,就稱為平衡更新過程。
2.5.3 酬勞更新過程:
如果每次更新有一次酬勞(酬勞也可以是penalty,也就是說酬勞可以為負),那么這樣的更新過程叫做酬勞更新過程。
每次的酬勞,我們記為R_{n},并用R(t)記直到t時刻的所有酬勞之和。
那么有如下和基本更新定理類似的定理:
R(t)/tR(t)/tR(t)/t(總酬勞的平均) 趨近于平均一個更新間隔內的平均酬勞。
或者總酬勞的均值的平均趨近于平均一個更新間隔內的平均酬勞。
這里的趨近于都是時間上趨近無窮大的涵義下。
排隊論可以說是最重要的定理:
更新過程的來到率:定義為更新間隔的均值的倒數也就是更新速率。記為λ\lambdaλ。
則排隊論的重要定理可以敘述為:
系統中(按時間)的平均人數等于來到率(更新速率)乘以每個顧客在系統中度過的時間。
或者排隊中(按時間)的平均人數等于來到率(更新速率)乘以每個顧客在排隊中度過的時間。
因為來到率是更新間隔的倒數,所以,至少在單位上,是不成問題的。也比較容易理解。
2.6 再生過程(regenerative process)
再生過程是說,存在一個時刻,在這個時刻之后,系統又從0時刻開始重復。
系統可以處于很多狀態上,兩個時刻之間算一個循環。
與交錯(交替)更新過程類似:
系統處于第j個狀態上的概率(在時間上)趨近于在一個更新間隔(循環)的均值時間內,系統處于狀態j的時間的均值。即處于狀態j的時間的均值比一個更新間隔(循環)的均值。
2.7 平穩點過程:
顧名思義,平穩點過程就是一個具有平穩增量的計數過程。
平穩點過程的重要定理如下:
平穩點過程計數N(t)大于0的概率與時間(t)之比等于一個正數。
也就是說平穩點過程N(t)的期望均值等于時間(t)乘以更新速率。
3. 大數定律
在數學與統計學中,大數定律又稱大數法則、大數律,是描述相當多次數重復實驗的結果的定律。根據這個定律知道,樣本數量越多,則其算術平均值就有越高的概率接近期望值。
大數定律很重要,因為它“說明”了一些隨機事件的均值的長期穩定性。人們發現,在重復試驗中,隨著試驗次數的增加,事件發生的頻率趨于一個穩定值;人們同時也發現,在對物理量的測量實踐中,測定值的算術平均也具有穩定性。比如,我們向上拋一枚硬幣,硬幣落下后哪一面朝上是偶然的,但當我們上拋硬幣的次數足夠多后,達到上萬次甚至幾十萬幾百萬次以后,我們就會發現,硬幣每一面向上的次數約占總次數的二分之一,亦即偶然之中包含著必然。
上述現象是切比雪夫不等式的一個特殊應用情況,辛欽定理和伯努利大數定律也都概括了這一現象,它們統稱為大數定律。
大數定理簡單來說,指得是某個隨機事件在單次試驗中可能發生也可能不發生,但在大量重復實驗中往往呈現出明顯的規律性,即該隨機事件發生的頻率會向某個常數值收斂,該常數值即為該事件發生的概率。
另一種表達方式為當樣本數據無限大時,樣本均值趨于總體均值。
因為現實生活中,我們無法進行無窮多次試驗,也很難估計出總體的參數。
大數定律告訴我們能用頻率近似代替概率;能用樣本均值近似代替總體均值。
很好得解決了現實問題。
3.1 舉例
例如,拋擲一顆均勻的6面的骰子,1,2,3,4,5,6應等概率出現,所以每次扔出骰子后,出現點數的期望值是
1+2+3+4+5+66=3.5\frac{1+2+3+4+5+6}{6}=3.561+2+3+4+5+6?=3.5
根據大數定理,如果多次拋擲骰子,隨著拋擲次數的增加,平均值(樣本平均值)應該接近3.5,根據大數定理,在多次伯努利實驗中,實驗概率最后收斂于理論推斷的概率值,對于伯努利隨機變量,理論推斷的成功概率就是期望值,而若對n個相互獨立的隨機變量的平均值,頻率越多則相對越精準。
例如硬幣投擲即伯努利實驗,當投擲一枚均勻的硬幣,理論上得出的正面向上的概率應是1/2。因此,根據大數定理,正面朝上的比例在相對“大”的數字下,“理應”接近為1/2,尤其是正面朝上的概率在n次實驗(n接近無限大時)后應幾近收斂到1/2。
即使正面朝上(或背面朝上)的比例接近1/2,幾乎很自然的正面與負面朝上的絕對差值(absolute difference差值范圍)應該相應隨著拋擲次數的增加而增加。換句話說,絕對差值的概率應該是會隨著拋擲次數而接近于0。直觀的來看,絕對差值的期望會增加,只是慢于拋擲次數增加的速度。
3.2 表現形式
大數定律主要有兩種表現形式:弱大數定律和強大數定律。
定律的兩種形式都肯定無疑地表明,樣本均值
相較于辛欽大數定律,切比雪夫大數定理并未要求同分布,更具一般性。
4. non-renewal
In real stochastic systems, the arrival and service processes may not be renewal processes. For example, in many telecommunication systems such as internet traffic where data traffic is bursty, the sequence of inter-arrival times and service times are often correlated and dependent. One way to model this non-renewal behavior is to use Markovian Arrival Processes (MAPs) and Markovian Service Processes (MSPs). MAPs and MSPs allow for inter-arrival and service times to be dependent, while providing the analytical tractability of simple Markov processes.
Young Myoung Ko & Jamol Pender (2018) Strong approximations for timevarying infinite-server queues with non-renewal arrival and service processes, Stochastic Models,
34:2, 186-206, DOI: 10.1080/15326349.2018.1425886
https://www.cnblogs.com/sddai/p/6094837.html
https://zhuanlan.zhihu.com/p/59876036
https://wenku.baidu.com/view/199c386cb84ae45c3b358c8a.html
https://zh.wikipedia.org/wiki/%E5%A4%A7%E6%95%B0%E5%AE%9A%E5%BE%8B
https://zhuanlan.zhihu.com/p/77312635
總結
以上是生活随笔為你收集整理的随机过程:指数分布、泊松过程、更新过程(renewal process)+大数定律的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 江苏省常熟理工学院是几本(常熟理工学院值
- 下一篇: 电脑快捷键键如何设置(电脑快捷键怎么设置