隨機(jī)過程第5講(馬爾科夫鏈定義和性質(zhì)).ppt

《隨機(jī)過程第5講(馬爾科夫鏈定義和性質(zhì)).ppt》由會員分享，可在線閱讀，更多相關(guān)《隨機(jī)過程第5講(馬爾科夫鏈定義和性質(zhì)).ppt（42頁珍藏版）》請在裝配圖網(wǎng)上搜索。

隨機(jī)過程及其應(yīng)用 離散時間Markov鏈 第5講 2020 1 29 鄭州大學(xué)信息工程學(xué)院 1 內(nèi)容提要 離散時間Markov鏈的定義 性質(zhì)離散時間Markov鏈舉例 2020 1 29 鄭州大學(xué)信息工程學(xué)院 2 安德雷 安德耶維奇 馬爾可夫 A A Markov 俄數(shù)學(xué)家 1856 1922概率和統(tǒng)計領(lǐng)域?qū)＜?當(dāng)年Markov研究普希金詩歌里元音字母和輔音字母交替出現(xiàn)的規(guī)律時提出了Markov過程的數(shù)學(xué)模型Markov過程80年代興起 在現(xiàn)代工程 自然科學(xué) 社會科學(xué)中應(yīng)用廣泛 2020 1 29 鄭州大學(xué)信息工程學(xué)院 3 1 馬爾可夫過程定義 定義 設(shè)有一隨機(jī)過程 t t T t1 t2 t3 tm tm 1 T 若在t1 t2 t3 tm tm 1時對 t 觀測得到相應(yīng)的觀測值x1 x2 x3 xm xm 1滿足條件 則稱這類過程為具有馬爾可夫性質(zhì)的隨機(jī)過程或馬爾可夫過程 2020 1 29 鄭州大學(xué)信息工程學(xué)院 4 Markov過程也可表示為如下形式 2020 1 29 鄭州大學(xué)信息工程學(xué)院 5 2020 1 29 鄭州大學(xué)信息工程學(xué)院 6 該式表明 t 的n維概率密度等于一些條件概率密度與t1時初始概率密度的乘積 這些條件概率密度稱為轉(zhuǎn)移概率密度 馬爾可夫過程 t t T 可能取的值的全體組成過程的狀態(tài)空間 t 可能取的值稱為狀態(tài) t x代表在t時刻過程 或系統(tǒng) 處在狀態(tài)x 馬爾可夫過程的狀態(tài)空間可以是連續(xù)的 也可以是離散的 馬爾可夫過程的參數(shù)t可以是連續(xù)的 也可以是離散的 Markov過程的分類Markov鏈 狀態(tài)值可數(shù)離散的Markov過程離散時間Markov鏈 第二章 連續(xù)時間Markov鏈 第三章 2020 1 29 鄭州大學(xué)信息工程學(xué)院 7 馬爾可夫鏈的定義 n n 0 1 2 是離散狀態(tài) 狀態(tài)空間為I 參數(shù)為非負(fù)整數(shù)的隨機(jī)過程 且 n 滿足條件 即在參數(shù)n 0 1 2 n 狀態(tài)取 0 i0 1 i1 n 1 in 1 n i的條件下 n 1 j的條件概率與 0 1 n 1 無關(guān)而僅與 n 所取的值有關(guān) 把這類隨機(jī)過程成為馬爾可夫鏈 2020 1 29 鄭州大學(xué)信息工程學(xué)院 8 由定義可知 2020 1 29 鄭州大學(xué)信息工程學(xué)院 9 一步轉(zhuǎn)移概率的兩個性質(zhì) 1 2 2020 1 29 鄭州大學(xué)信息工程學(xué)院 10 齊次馬爾可夫鏈 定義 如果在馬爾可夫鏈中即從 狀態(tài)轉(zhuǎn)移到 狀態(tài)的概率與 無關(guān) 則稱這類馬爾可夫鏈為齊次馬爾可夫鏈 設(shè) 代表一步轉(zhuǎn)移概率pij所組成的矩陣 且狀態(tài)空間 由狀態(tài) 所組成 則 2020 1 29 鄭州大學(xué)信息工程學(xué)院 11 一步轉(zhuǎn)移概率矩陣P中每個元素為非負(fù) 每行之和均為1 2 切普曼 柯爾莫哥洛夫方程式 C K方程 m步轉(zhuǎn)移概率 性質(zhì) m 1時即一步轉(zhuǎn)移概率 m 0時規(guī)定 2020 1 29 鄭州大學(xué)信息工程學(xué)院 12 對于m步轉(zhuǎn)移概率矩陣有C K方程 2020 1 29 鄭州大學(xué)信息工程學(xué)院 13 證明 2020 1 29 鄭州大學(xué)信息工程學(xué)院 14 這一事件可分解成 件的和事件 如下圖所示 C K方程是指 n 在n時處于狀態(tài)i的條件下經(jīng)過m r步轉(zhuǎn)移與n m r時到達(dá)狀態(tài)j 可以先在n時從狀態(tài)i出發(fā) 經(jīng)過m步于n m時到達(dá)某種中間狀態(tài)k 再在n m時從狀態(tài)k出發(fā)經(jīng)過r步轉(zhuǎn)移于n m r時到達(dá)最終狀態(tài)j 而中間狀態(tài)k要取遍整個狀態(tài)空間 C K方程也可以用矩陣形式表示 r 1時 可得 一直推下去可得 結(jié)論 馬爾可夫鏈的m步轉(zhuǎn)移概率由一步轉(zhuǎn)移概率所完全決定 2020 1 29 鄭州大學(xué)信息工程學(xué)院 15 馬爾可夫鏈的分布 1 初始分布稱 i I為馬氏鏈的初始分布 2 有限維分布定理 馬爾可夫鏈的有限維分布由其初始分布和一步轉(zhuǎn)移概率所完全確定 2020 1 29 鄭州大學(xué)信息工程學(xué)院 16 轉(zhuǎn)移概率決定了馬氏鏈的運動的統(tǒng)計規(guī)律 因此 確定馬氏鏈的任意n步轉(zhuǎn)移概率成為馬氏鏈理論中的重要問題之一 證明 2020 1 29 鄭州大學(xué)信息工程學(xué)院 17 馬爾可夫鏈的例子 例 天氣預(yù)報問題如果明天是否有雨僅與今天的天氣 是否有雨 有關(guān) 而與過去的天氣無關(guān) 并設(shè)今日下雨 明日有雨的概率為 今日無雨明日有雨的概率為 又假定把有雨稱為 狀態(tài)天氣 把無雨稱為 狀態(tài)天氣 n 表示n時的狀態(tài)天氣 則 n 是以 0 1 為狀態(tài)空間的齊次馬爾可夫鏈 它的一步轉(zhuǎn)移矩陣為 2020 1 29 鄭州大學(xué)信息工程學(xué)院 18 設(shè) 0 7 0 4 則一步轉(zhuǎn)移概率矩陣為 2020 1 29 鄭州大學(xué)信息工程學(xué)院 19 四步轉(zhuǎn)移概率矩陣 由此可知 今日有雨且第四日仍有雨的概率為 P00 4 0 5749 則兩步轉(zhuǎn)移概率矩陣 2020 1 29 鄭州大學(xué)信息工程學(xué)院 20 例 解 1 先求出2步轉(zhuǎn)移概率矩陣 2020 1 29 鄭州大學(xué)信息工程學(xué)院 21 例一維隨機(jī)游動 游動的概率規(guī)則 如果Q現(xiàn)在位于點i 1 i 5 則下一時刻各以1 3的概率向左或向右移動一格 或以1 3的概率留在原處 2020 1 29 鄭州大學(xué)信息工程學(xué)院 22 如果Q現(xiàn)在位于1 或5 這點上 則下一時刻就以概率1移動到2 或4 這一點上 1和5這兩點稱為反射壁 上面這種游動稱為帶有兩個反射壁的隨機(jī)游動 模擬方法 產(chǎn)生均勻分布的隨機(jī)數(shù)序列13232211122 其中1表示左移 2表示不動 3表示右移 2020 1 29 鄭州大學(xué)信息工程學(xué)院 23 理論分析 狀態(tài)空間是I 而與時刻n以前所處的狀態(tài)無關(guān) 所以它是一個馬氏鏈 且是齊次的 2020 1 29 鄭州大學(xué)信息工程學(xué)院 24 一步轉(zhuǎn)移概率 2020 1 29 鄭州大學(xué)信息工程學(xué)院 25 一步轉(zhuǎn)移概率矩陣 說明 改變游動的概率規(guī)則 就可得到不同方式的 隨機(jī)游動和相應(yīng)的馬氏鏈 如果把點1改為吸收壁 相應(yīng)鏈的轉(zhuǎn)移概率矩陣只須把P中第1行改為 例 無限制隨機(jī)游動問題質(zhì)點在直線上做隨機(jī)游動 如某一時刻質(zhì)點位于 則下一步質(zhì)點以概率 向右移動一格到達(dá) 或以概率 向左移一格到達(dá) 若以 n 表示時刻 時質(zhì)點的位置 則 n n 0 1 2 是一個隨機(jī)過程 而且當(dāng) n i時 n 1 n 2 n k 等 時刻后質(zhì)點所處的狀態(tài)只與 n i有關(guān) 而與質(zhì)點在 以前是如何到達(dá) 的完全無關(guān) 所以它是一個齊次馬爾可夫鏈 其狀態(tài)空間為I 2 1 0 1 2 而其一步轉(zhuǎn)移概率為 2020 1 29 鄭州大學(xué)信息工程學(xué)院 26 下面求它的 步轉(zhuǎn)移概率pij n 已知每次轉(zhuǎn)移只有兩種可能 向左的概率為 向右的概率為 而 次轉(zhuǎn)移的結(jié)果是從 到 如果 次轉(zhuǎn)移中向右m1次 向左m2次 則 2020 1 29 鄭州大學(xué)信息工程學(xué)院 27 例 有限制的隨機(jī)游動問題 帶有兩個吸收壁的隨機(jī)游動 2020 1 29 鄭州大學(xué)信息工程學(xué)院 28 隨機(jī)游動的狀態(tài)空間為I 0 1 2 a 0 a兩狀態(tài)為吸收態(tài) 該過程仍是齊次馬爾可夫鏈 它的一步轉(zhuǎn)移概率矩陣為 例 賭徒輸光問題 兩個賭徒甲 乙進(jìn)行一系列賭博 在每一局中甲獲勝的概率為p 乙獲勝的概率為q p q 1 每一局后 負(fù)者要付一元給勝者 如果起始時甲有資本a元 乙有資本b元 a b c元 兩人賭博直到甲輸光或乙輸光為止 求甲輸光的概率 這個問題實質(zhì)上是帶有兩個吸收壁的隨機(jī)游動 這時的狀態(tài)空間為 0 1 2 c c a b a 1 b 1 現(xiàn)在的問題是求質(zhì)點從a點出發(fā)到達(dá)0狀態(tài)先于到達(dá)c狀態(tài)概率 2020 1 29 鄭州大學(xué)信息工程學(xué)院 29 解 設(shè)0 j c 設(shè)uj為質(zhì)點從j出發(fā)到達(dá)0狀態(tài)先于到達(dá)c狀態(tài)的概率 根據(jù)全概率公式有 考慮質(zhì)點從j出發(fā)移動一步后的情況 在以概率p移到j(luò) 1的假設(shè)下 到達(dá)0狀態(tài)先于到達(dá)c狀態(tài)的概率為uj 1 同理 在以概率q移到j(luò) 1的前提下 到達(dá)0先于到達(dá)c的概率為uj 1 利用全概率定理就可以得到上述方程 這一方程實質(zhì)上是一差分方程 它的邊界條件是 2020 1 29 鄭州大學(xué)信息工程學(xué)院 30 2020 1 29 鄭州大學(xué)信息工程學(xué)院 31 因此 2020 1 29 鄭州大學(xué)信息工程學(xué)院 32 故 當(dāng)r 1時u0 uc 1 cd0而uj c j d0因此 故 由以上計算結(jié)果可知 當(dāng)r 1即p q時 甲先輸光的概率為 2020 1 29 鄭州大學(xué)信息工程學(xué)院 33 當(dāng)r 1即p q時 甲先輸光的概率為b c用同樣的方法可以求得乙先輸光的概率 當(dāng)p q時 乙先輸光的概率為當(dāng)p q時 乙先輸光的概率為a c 2020 1 29 鄭州大學(xué)信息工程學(xué)院 34 例 2020 1 29 鄭州大學(xué)信息工程學(xué)院 35 解 2020 1 29 鄭州大學(xué)信息工程學(xué)院 36 概率為 2020 1 29 鄭州大學(xué)信息工程學(xué)院 37 某計算機(jī)房的一臺計算機(jī)經(jīng)常出故障 研究者每隔15分鐘觀察一次計算機(jī)運行狀態(tài) 收集了24小時的數(shù)據(jù) 共作97次觀察 用1表示正常狀態(tài) 用0表示不正常狀態(tài) 所得的數(shù)據(jù)序列如下 1110010011111110011110111111001111111110001101101 111011011010111101110111101111110011011111100111 分析 狀態(tài)空間 I 0 1 例 2020 1 29 鄭州大學(xué)信息工程學(xué)院 38 96次狀態(tài)轉(zhuǎn)移的情況 因此 一步轉(zhuǎn)移概率可用頻率近似地表示為 有些問題雖然不是馬爾可夫鏈 但經(jīng)過某些處理 仍可以把它看作馬爾可夫鏈 例 在天氣預(yù)報問題中 認(rèn)為今日是否下雨依賴于前兩天的天氣狀況 并規(guī)定 昨日 今日都下雨 明日有雨的概率為0 7 今日有雨 昨日無雨 明日有雨的概率為0 5 昨日有雨 今日無雨 明日有雨的概率為0 4 昨日 今日均無雨 明日有雨的概率為0 2 該問題不是馬爾可夫鏈 但是 經(jīng)過如下處理卻可以把它看作馬爾可夫鏈 2020 1 29 鄭州大學(xué)信息工程學(xué)院 39 設(shè)昨日 今日連續(xù)兩天有雨稱為狀態(tài)0 RR 昨日無雨 今日有雨稱為狀態(tài)1 NR 昨日有雨 今日無雨稱為狀態(tài)2 RN 昨日 今日均無雨稱為狀態(tài)3 NN 于是形成了四個狀態(tài)的馬爾可夫鏈 其中 2020 1 29 鄭州大學(xué)信息工程學(xué)院 40 其中R代表有雨 N代表無雨 于是它的一步轉(zhuǎn)移概率矩陣為 2020 1 29 鄭州大學(xué)信息工程學(xué)院 41 有了一步轉(zhuǎn)移概率矩陣就可以對今后的天氣進(jìn)行預(yù)報 例如 若星期一 星期二均下雨 求星期四下雨的概率 從一步轉(zhuǎn)移概率矩陣可以計算出兩步轉(zhuǎn)移概率矩陣 2020 1 29 鄭州大學(xué)信息工程學(xué)院 42 星期四下雨意味著過程所處的狀態(tài)為0或1 因此星期一 二連續(xù)下雨 星期四下雨的概率為