數(shù)理統(tǒng)計(jì)與隨機(jī)過(guò)程馬爾科夫鏈

《數(shù)理統(tǒng)計(jì)與隨機(jī)過(guò)程馬爾科夫鏈》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)理統(tǒng)計(jì)與隨機(jī)過(guò)程馬爾科夫鏈（34頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù) 理 統(tǒng) 計(jì) 與 隨 機(jī) 過(guò) 程第 十 一 章主講教師：程維虎教授北京工業(yè)大學(xué)應(yīng)用數(shù)理學(xué)院 第 十 一 章 馬 爾 可 夫 鏈 本 章 首 先 從 隨 機(jī) 過(guò) 程 在 不 同 時(shí) 刻 狀 態(tài) 之 間 的 特殊 的 統(tǒng) 計(jì) 聯(lián) 系 ， 引 入 馬 爾 可 夫 (Markoff)過(guò) 程 的 概念 。 然 后 ， 對(duì) 馬 爾 可 夫 鏈 (狀 態(tài) 、 時(shí) 間 都 是 離 散 的馬 爾 可 夫 過(guò) 程 )的 兩 個(gè) 基 本 問(wèn) 題 ， 即 轉(zhuǎn) 移 概 率 的 確定 以 及 遍 歷 性 問(wèn) 題 作 不 同 程 度 的 研 究 和 介 紹 。 馬 爾 可 夫 過(guò) 程 的 理 論 在 近 代 物 理 、

2、生 物 學(xué) 、 管理 科 學(xué) 、 經(jīng) 濟(jì) 、 信 息 處 理 以 及 數(shù) 字 計(jì) 算 方 法 等 方 面都 有 重 要 應(yīng) 用 。 11.1 馬 爾 可 夫 過(guò) 程 及 其 概 率 分 布 在 物 理 學(xué) 中 ， 很 多 確 定 性 現(xiàn) 象 遵 從 如 下 演 變 原則 ： 由 時(shí) 刻 t0系 統(tǒng) 或 過(guò) 程 所 處 的 狀 態(tài) ， 可 以 決 定 系統(tǒng) 或 過(guò) 程 在 時(shí) 刻 t t0所 處 的 狀 態(tài) ， 而 無(wú) 需 借 助 于 t0以 前 系 統(tǒng) 或 過(guò) 程 所 處 狀 態(tài) 的 歷 史 資 料 。 如 微 分 方 程問(wèn) 題 所 描 繪 的 物 理 過(guò) 程 就 屬 于 這 類(lèi) 確 定 性

3、現(xiàn) 象 。 把上 述 原 則 延 伸 到 隨 機(jī) 現(xiàn) 象 ， 即 當(dāng) 一 物 理 系 統(tǒng) 或 過(guò) 程遵 循 的 是 某 種 統(tǒng) 計(jì) 規(guī) 律 時(shí) ， 可 仿 照 上 面 的 原 則 ， 引入 以 下 的 馬 爾 可 夫 性 或 無(wú) 后 效 性 ： 過(guò) 程 (或 系 統(tǒng) )在時(shí) 刻 t0所 處 的 狀 態(tài) 為 已 知 的 條 件 下 ， 過(guò) 程 在 時(shí) 刻 tt0所 處 狀 態(tài) 的 條 件 分 布 與 過(guò) 程 在 t 0之 前 所 處 的 狀 態(tài) 無(wú)關(guān) 。 通 俗 地 說(shuō) ， 就 是 在 已 經(jīng) 知 道 過(guò) 程 “ 現(xiàn) 在 ” 的 條件 下 ， 其 “ 將 來(lái) ” 不 依 賴 于 “ 過(guò) 去 ”

4、。 現(xiàn) 用 分 布 函 數(shù) 來(lái) 表 述 馬 爾 可 夫 性 .設(shè) 隨 機(jī) 過(guò) 程 X(t), t T的 狀 態(tài) 空 間 為 I。 如 果 對(duì) 時(shí) 間 t的 任 意 n個(gè) 數(shù) 值 t1t2 tn, n3, ti T， 在 條 件 X(ti)=xi,xi I,i=1,2, ,n-1下 , X(tn)的 條 件 分 布 函數(shù) 恰 等 于 在 條 件 X(tn-1)=xn-1下 X(tn)的 條 件 分 布 函 數(shù)，或 寫(xiě) 成 ),( ),;,( ,)()( )(,)(,)()( 11 12112111 112211 nnnntt nnnnttt nnnnn nnnn txtxF tttxxxtxF

5、Rx xtXxtXP xtXxtXxtXxtXP 1-nn 1-n1n 則 稱 過(guò) 程 X(t), t T具 有 馬 爾 可 夫 性 或 無(wú) 后 效 性 ， 并 稱 此 過(guò)程 為 馬 爾 可 夫 過(guò) 程 。 (1.1) 例 1 設(shè) X(t), t 0是 獨(dú) 立 增 量 過(guò) 程 ， 且 X(0)=0， 證 明 X(t), t 0是 一 個(gè) 馬 爾 可 夫 過(guò) 程 。證 由 (1.1)式 知 ， 只 要 證 明 在 已 知 X(tn-1)=xn-1的 條 件 下 X(tn)與 X(tj),j=1,2, ,n-2相 互 獨(dú) 立 即 可 。 現(xiàn) 由 獨(dú) 立 增 量 過(guò) 程 的 定 義知 道 ， 當(dāng) 0

6、tjtn-1tn,j=1,2, ,n-2時(shí) ， 增 量X(tj)-X(0)與 X(tn)-X(tn-1)相 互 獨(dú) 立 。 根 據(jù) 條 件 X(0)=0和 X(tn-1)=xn-1,即 有X(tj)與 X(tn)-X(tn-1)相 互 獨(dú) 立 。 再 由 第 三 章 4定 理 知 ， 此 時(shí) X(tn)與 X(tj)， j=1,2, ,n-2相 互 獨(dú) 立 。 這 表 明 X(t)具 有 后 無(wú) 效 性 ,即 X(t), t 0是 一 個(gè) 馬 爾可 夫 過(guò) 程 。 由 上 例 知 ， 泊 松 過(guò) 程 是 時(shí) 間 連 續(xù) 狀 態(tài) 離 散 的 馬 氏 過(guò) 程 ；維 納 過(guò) 程 是 時(shí) 間 狀 態(tài)

7、都 連 續(xù) 的 馬 氏 過(guò) 程 。 時(shí) 間 和 狀 態(tài) 都 是 離 散 的 馬 爾 可 夫 過(guò) 程 稱 為 馬 爾可 夫 鏈 ， 簡(jiǎn) 稱 馬 氏 鏈 ， 記 為 Xn=X(n), n =0,1,2, ， 它可 以 看 作 在 時(shí) 間 集 T1=0,1,2, 上 對(duì) 離 散 狀 態(tài) 的 馬 氏 過(guò) 程 相繼 觀 察 的 結(jié) 果 .我 們 約 定 記 鏈 的 狀 態(tài) 空 間 I=a1,a2, ,ai R。在 鏈 的 情 形 ， 馬 爾 可 夫 性 通 常 用 條 件 分 布 律 來(lái) 表 示 ， 即 對(duì) 任意 的 正 整 數(shù) n,r和 0t1t2 trm； m,n T1， 有 aXaXP aXaXa

8、XaXaXP imjnm imitititjnm rr, , 2211 (1.2)其 中 ai I。 記 上 式 右 端 為 Pij(m, m+n),我 們 稱 條 件 概 率 Pij(m, m+n)=PXm+n= aj Xm = ai為 馬 氏 鏈 在 時(shí) 刻 m處 于 狀 態(tài) ai條 件 下 ， 在 時(shí) 刻 m+n轉(zhuǎn) 移 到 狀態(tài) aj的 轉(zhuǎn) 移 概 率 。 (1.3) 由 于 鏈 在 時(shí) 刻 m從 任 何 一 狀 態(tài) ai出 發(fā) ， 到 另 一 時(shí) 刻 m+n，必 然 轉(zhuǎn) 移 到 a1, a2, 諸 狀 態(tài) 中 的 某 一 個(gè) ， 所 以 1 ,2,1,1),(j ij inmmP (1

9、.4) 由 轉(zhuǎn) 移 概 率 組 成 的 矩 陣 P(m, m+n)=(Pij(m, m+n)稱 為 馬氏 鏈 的 轉(zhuǎn) 移 概 率 矩 陣 。 由 (1.4)式 知 ， 此 矩 陣 的 每 一 行 元 之和 等 于 1。 當(dāng) 轉(zhuǎn) 移 概 率 Pij(m, m+n)只 與 i,j及 時(shí) 間 間 距 n有 關(guān) 時(shí) ， 把它 記 為 Pij(n)， 即 P ij(m, m+n)= Pij(n)并 稱 此 轉(zhuǎn) 移 概 率 具 有 平 穩(wěn) 性 。 同 時(shí) 也 稱 此 鏈 是 齊 次 的 或 時(shí)齊 的 。 以 下 我 們 限 于 討 論 齊 次 馬 氏 鏈 。 在 馬 氏 鏈 為 齊 次 的 情 形 下 ，

10、 由 (1.3)式 定 義 的 轉(zhuǎn) 移 概 率 Pij(n)= PXm+n= aj Xm = ai 稱 為 馬 氏 鏈 的 n步 轉(zhuǎn) 移 概 率 ，P (n)= (Pij(n)為 n步 轉(zhuǎn) 移 概 率 矩 陣 。 在 以 下 的 討 論 中 特 別 重要 的 是 一 步 轉(zhuǎn) 移 概 率 Pij=Pij(1)=PXm+1= aj Xm = ai 或 由 它 們 組 成 的 一 步 轉(zhuǎn) 移 概 率 矩 陣在 上 述 矩 陣 的 左 側(cè) 和 上 邊 標(biāo) 上 狀 態(tài) a 1, a2, 是 為 了 顯 示 Pij是 由 狀 態(tài) ai經(jīng) 一 步 轉(zhuǎn) 移 到 狀 態(tài) aj的 概 率 。 例 2 （ 0-1傳

11、 輸 系 統(tǒng) ） 在 如 下 圖 只 傳 傳 輸 數(shù) 字 0和 1的 串 聯(lián) 系統(tǒng) 中 ， 設(shè) 每 一 級(jí) 的 傳 真 率 （ 輸 出 與 輸 入 數(shù) 字 相 同 的 概 率 稱為 系 統(tǒng) 的 傳 真 率 ， 相 反 情 形 稱 為 誤 碼 率 ） 為 p， 誤 碼 率 為q=1-p， 并 設(shè) 一 個(gè) 單 位 時(shí) 間 傳 輸 一 級(jí) ， X0是 第 一 級(jí) 的 輸 入 ，Xn是 第 n級(jí) 的 輸 出 (n1)， 那 么 Xn, n =0,1,2, 是 一 隨 機(jī) 過(guò)程 ， 狀 態(tài) 空 間 I=0,1， 而 且 當(dāng) Xn=i , i I為 已 知 時(shí) , Xn+1所 處的 狀 態(tài) 的 概 率 分

12、 布 只 與 Xn=i 有 關(guān) ， 而 與 時(shí) 刻 n以 前 所 處 的狀 態(tài) 無(wú) 關(guān) ， 所 以 它 是 一 個(gè) 馬 氏 鏈 ， 而 且 還 是 齊 次 的 。 它 的一 步 轉(zhuǎn) 移 概 率 和 一 步 轉(zhuǎn) 移 概 率 分 別 為 1 , , , 0,1, ,ij n n p j ip p X j X i i jq j i 01 p qP q p 和 例 2 一 維 隨 機(jī) 游 動(dòng) 設(shè) 一 醉 漢 Q在 如 下 圖 所 示 直 線 的 點(diǎn) 集I=1,2,3,4,5上 作 隨 機(jī) 游 動(dòng) ， 且 僅 在 1秒 、 2秒 等 時(shí) 刻 發(fā) 生 游動(dòng) 。 游 動(dòng) 的 概 率 規(guī) 則 是 ： 如 果

13、Q現(xiàn) 在 位 于 點(diǎn) i(1i5)， 則 下一 時(shí) 刻 各 以 1/3的 概 率 向 左 或 向 右 移 動(dòng) 一 格 ， 或 以 1/3的 概率 留 在 原 處 ； 如 果 Q現(xiàn) 在 位 于 1(或 5)這 點(diǎn) 上 ， 則 下 一 時(shí) 刻就 以 概 率 1移 動(dòng) 到 2(或 4)這 一 點(diǎn) 上 。 1和 5這 兩 點(diǎn) 稱 為 反 射 壁 。上 面 這 種 游 動(dòng) 稱 為 帶 有 兩 個(gè) 反 射 壁 的 隨 機(jī) 游 動(dòng) 。 若 以 Xn表 示 時(shí) 刻 n時(shí) Q的 位 置 ， 不 同 的 位 置 就 是 Xn的 不同 狀 態(tài) ， 那 么 Xn , n=0,1,2是 一 隨 機(jī) 過(guò) 程 ， 狀 態(tài)

14、空 間 就是 I， 而 且 Xn=i, i I為 已 知 時(shí) ， Xn+1所 處 的 狀 態(tài) 的 概 率 分布 只 與 Xn= i 有 關(guān) ， 而 與 Q在 時(shí) 刻 n以 前 如 何 達(dá) 到 i是 完 全 無(wú)關(guān) 的 ， 所 以 Xn , n=0,1,2是 一 馬 氏 鏈 ， 而 且 還 是 齊 次 的 ，它 的 一 步 轉(zhuǎn) 移 概 率 和 一 步 轉(zhuǎn) 移 概 率 矩 陣 分 別 為 1 1, 1, , 1,1 53 1, 1, 2 5, 4,0, 2ij n n j i i i ip P X j X i i j i jj i 或0 1 0 0 01/3 1/3 1/3 0 00 1/3 1/3

15、 1/3 00 0 1/3 1/3 1/30 0 0 1 01 2 3 4 512345和 P= 如 果 把 1這 一 點(diǎn) 改 為 吸 收 壁 ， 即 是 說(shuō) Q一 旦 到 達(dá) 1這 一點(diǎn) ， 則 就 永 遠(yuǎn) 留 在 點(diǎn) 1上 ， 此 時(shí) ， 相 應(yīng) 鏈 的 轉(zhuǎn) 移 概 率 矩 陣只 須 把 P中 的 第 一 橫 行 改 為 (1,0,0,0,0)。 總 之 ， 改 變 游 動(dòng) 的概 率 規(guī) 則 ,就 可 得 到 不 同 方 式 的 隨 機(jī) 游 動(dòng) 和 相 應(yīng) 的 馬 式 鏈 。 隨 機(jī) 游 動(dòng) 的 思 想 在 數(shù) 值 計(jì) 算 方 法 方 面 有 重 要 應(yīng) 用 。例 4 排 隊(duì) 模 型 設(shè)

16、服 務(wù) 系 統(tǒng) 由 一 個(gè) 服 務(wù) 員 和 只 可 以 容 納兩 個(gè) 人 的 等 候 室 組 成 ， 見(jiàn) 圖 11-3。 服 務(wù) 規(guī) 則 是 ： 先 到 先服 務(wù) ， 后 來(lái) 者 首 先 需 在 等 候 室 。 假 定 一 顧 客 到 達(dá) 系 統(tǒng) 時(shí)發(fā) 現(xiàn) 系 統(tǒng) 內(nèi) 已 有 3個(gè) 顧 客 (一 個(gè) 正 在 接 受 服 務(wù) ， 兩 個(gè) 在 等候 室 排 隊(duì) )， 則 該 顧 客 即 離 去 。 設(shè) 時(shí) 間 間 隔 t內(nèi) 有 一 個(gè)顧 客 進(jìn) 入 系 統(tǒng) 的 概 率 為 q， 有 一 原 來(lái) 被 服 務(wù) 的 顧 客 離 開(kāi)系 統(tǒng) (即 服 務(wù) 完 畢 )的 概 率 為 p。 又 設(shè) 當(dāng) t充 分

17、 小 時(shí) ， 在這 時(shí) 間 間 隔 內(nèi) 多 于 一 個(gè) 顧 客 進(jìn) 入 或 離 開(kāi) 系 統(tǒng) 實(shí) 際 上 是 不可 能 的 。 再 設(shè) 有 無(wú) 顧 客 來(lái) 到 與 服 務(wù) 是 否 完 畢 是 相 互 獨(dú) 立 ?，F(xiàn) 用 馬 氏 鏈 來(lái) 描 述 這 個(gè) 服 務(wù) 系 統(tǒng) 。 圖 11-3 設(shè) Xn=X(nt)表 示 時(shí) 刻 nt 時(shí) 系 統(tǒng) 內(nèi) 的 顧 客 數(shù) ， 即 系 統(tǒng) 的 狀態(tài) , Xn , n=0,1,2 是 一 隨 機(jī) 過(guò) 程 ,狀 態(tài) 空 間 I=0,1,2,3,可 知 它是 一 個(gè) 齊 次 馬 氏 鏈 。 下 面 來(lái) 計(jì) 算 此 馬 氏 鏈 的 一 步 轉(zhuǎn) 移 概 率 。 p00 在

18、系 統(tǒng) 內(nèi) 沒(méi) 有 顧 客 的 條 件 下 ， 經(jīng) t 后 仍 沒(méi) 有 顧 客 的概 率 (此 處 是 條 件 概 率 ， 以 下 同 ) p00=1-q. p01-在 系 統(tǒng) 內(nèi) 沒(méi) 有 顧 客 的 條 件 下 ， 經(jīng) t 后 有 一 顧 客 進(jìn) 入系 統(tǒng) 的 概 率 ， p01=q. p10-系 統(tǒng) 內(nèi) 恰 有 一 個(gè) 顧 客 正 在 接 受 服 務(wù) 的 條 件 下 ， 經(jīng) t后系 統(tǒng) 內(nèi) 無(wú) 人 的 概 率 ， 它 等 于 在 t 間 隔 內(nèi) 顧 客 因 服 務(wù) 完 畢 而 離去 ， 且 無(wú) 人 進(jìn) 入 系 統(tǒng) 的 概 率 ， p 10=p(1-q) p11 系 統(tǒng) 內(nèi) 恰 有 1個(gè) 顧

19、 客 的 條 件 下 ， 在 t 間 隔 內(nèi) ， 他 因服 務(wù) 完 畢 而 離 去 ， 而 另 一 顧 客 進(jìn) 入 系 統(tǒng) ， 或 者 正 在 接 受 服 務(wù)的 顧 客 將 繼 續(xù) 要 求 服 務(wù) ， 且 無(wú) 人 進(jìn) 入 系 統(tǒng) 的 概 率 。 p11=pq+(1-p)(1-q). p12 正 在 接 受 服 務(wù) 的 顧 客 繼 續(xù) 要 求 服 務(wù) ， 且 另 一 個(gè) 顧 客進(jìn) 入 系 統(tǒng) 的 概 率 p12=q(1-p). p13 正 在 接 受 服 務(wù) 的 顧 客 繼 續(xù) 要 求 服 務(wù) ， 且 在 t 間 隔內(nèi) 有 兩 個(gè) 顧 客 進(jìn) 入 系 統(tǒng) 的 概 率 ， 由 假 設(shè) ， 后 者

20、實(shí) 際 上 是 不可 能 發(fā) 生 的 ， p13 =0. 類(lèi) 似 地 ， 有 p21 = p32=p(1-q), p22 =pq+(1-p)(1-q), p23= q(1-p), p ij =0(|i-j|2). p33 一 人 因 服 務(wù) 完 畢 而 離 去 且 另 一 人 將 進(jìn) 入 系 統(tǒng) ， 或 者無(wú) 人 離 開(kāi) 系 統(tǒng) 的 概 率 ， p33 = pq+(1-p) 于 是 該 馬 氏 鏈 的 一 步 轉(zhuǎn) 移 概 率 矩 陣 為 )1()1(00 )1()1)(1()1(0 0)1()1)(1()1( 00)1( ppqqp pqqppqqp pqqppqqp qqP 在 實(shí) 際 問(wèn)

21、題 中 ， 一 步 轉(zhuǎn) 移 概 率 通 常 可 通 過(guò) 統(tǒng) 計(jì) 試 驗(yàn) 確定 ， 下 面 看 一 實(shí) 例 。例 5 計(jì) 算 機(jī) 機(jī) 房 的 一 臺(tái) 計(jì) 算 機(jī) 經(jīng) 常 出 故 障 ， 研 究 者 每 隔 15分 鐘 觀 察 一 次 計(jì) 算 機(jī) 的 運(yùn) 行 狀 態(tài) ， 收 集 了 24小 時(shí) 的 數(shù) 據(jù)（ 共 作 97次 觀 察 ） 。 用 1表 示 正 常 狀 態(tài) ， 用 0表 示 不 正 常 狀態(tài) ， 所 得 的 數(shù) 據(jù) 序 列 如 下 ：11100100111111100111101111110011111111100011011011110110110101111011101111011

22、11110011011111100111 設(shè) Xn為 第 n( n =1,2,97)個(gè) 時(shí) 段 的 計(jì) 算 機(jī) 狀 態(tài) ,可 以 認(rèn) 為 它是 一 個(gè) 馬 氏 鏈 ,狀 態(tài) 空 間 I=0， 1.96次 狀 態(tài) 轉(zhuǎn) 移 的 情 況 是 :0 0,8次 ； 0 1,18次 ； 1 0,18次 ； 1 1,52次 .因 此 ， 一 步 轉(zhuǎn) 移 概 率 可 用 頻 率 近 似 地 表 示 為 ,268188 800100 nn XXpp ,26181881801 101 nn XXpp ,701852181810110 nn XXpp .705252185211111 nn XXpp 例 6（ 續(xù)

23、例 5） 若 計(jì) 算 機(jī) 在 前 一 段 (15分 鐘 )的 狀 態(tài) 為 0， 問(wèn) 在此 條 件 下 從 此 時(shí) 段 起 此 計(jì) 算 機(jī) 能 連 續(xù) 正 常 工 作 3刻 鐘 (3個(gè) 時(shí)段 )的 概 率 為 多 少 ？解 由 題 意 ， 某 一 時(shí) 段 的 狀 態(tài) 為 0就 是 初 始 狀 態(tài) 為 0， 即X 0= 0。 由 乘 法 公 式 、 馬 氏 性 和 齊 次 性 得 ， 所 求 條 件 概 率 為 382.0705270522618)1()1()1( 111101 0/0,1,11 0,11010 0/1,1,1,0 01,1,1 111101 231201 00123 012010

24、 03210 0321 PPP XXPXXPXXP XPXXXXP XXXPXXPXP XPXXXXP XXXXP 接 著 ， 我 們 來(lái) 研 究 齊 次 馬 氏 鏈 的 有 限 維 分 布 。 首 先 ， 記.,)0( 0 ， 21j Ia aXPp jjj 稱 它 為 馬 氏 鏈 的 初 始 分 布 。 再 看 馬 氏 鏈 在 任 意 時(shí) 刻 n T1的一 維 分 布 ： ( ) , , 1,2,.j n j jp n P X a a I j 顯 然 ， 應(yīng) 有 由 全 概 率 公 式1)(1 npj j ,00 1 iiji njn aXpaXaXpaXp ,.2,1),()0()( 1

25、 jnppnp iji ij即 (1.6)(1.7) 一 維 分 布 (1.6)也 可 用 行 向 量 表 示 成 p(n)=( p1(n), p2(n), pj(n),)這 樣 ， 利 用 矩 陣 乘 法 (I是 可 列 無(wú) 限 集 時(shí) ， 仍 用 有 限 階 矩 陣 乘法 的 規(guī) 則 確 定 矩 陣 之 積 的 元 )， (1.7)式 可 寫(xiě) 成 p(n) = p(0)P(n) 此 式 表 明 ， 馬 氏 鏈 在 任 一 時(shí) 刻 n T1時(shí) 的 一 維 分 布 由 初 始 分布 p(0)和 n 步 轉(zhuǎn) 移 概 率 矩 陣 所 確 定 。 (1.6) (1.7) 又 ,對(duì) 于 任 意 n個(gè)

26、時(shí) 刻 t1t2 tn, ti T1 以 及 狀 態(tài) ， 馬 氏 鏈 的 n維 分 布 ：1 2, ,., ni i ia a a I )()( , , 112 1211 11112211 112211 112211 2211 nniiiii ititititit itititit ititit ititit ttPttPp aXaXPaXaXPaXP aXaXaXaXP aXaXPaXP aXaXaXP nn nnnn nnnn nn (1.8)由 此 ， 并 結(jié) 合 (1.7)或 (1.7) 可 知 ： 齊 次 馬 氏 鏈 的 有 限 維 分 布同 樣 完 全 由 初 始 分 布 和 轉(zhuǎn)

27、移 概 率 確 定 。 總 之 ， 轉(zhuǎn) 移 概 率 決 定 了 馬 氏 鏈 的 統(tǒng) 計(jì) 規(guī) 律 。 因 此 ， 確定 馬 氏 鏈 的 任 意 n步 轉(zhuǎn) 移 概 率 就 成 為 馬 氏 鏈 理 論 中 的 重 要問(wèn) 題 之 一 。 11.2 多 步 轉(zhuǎn) 移 概 率 的 確 定 為 了 確 定 齊 次 馬 氏 鏈 的 n步 轉(zhuǎn) 移 概 率 Pij(n) ， 首 先 介 紹Pij(n) 所 滿 足 的 基 本 方 程 。 設(shè) X(n), n T1是 一 齊 次 馬 氏 鏈 ,則 對(duì) 任 意 的 u,v T1 ,有 方 程 (2.1)就 是 著 名 的 切 普 曼 -柯 莫 哥 洛 夫 (Chapma

28、n-K olmogorov)方 程 ， 簡(jiǎn) 稱 C-K 方 程 。 )1.2(.2,1,),()()( 1 jivpupvup kjk ikij C-K 方 程 基 于 下 述 事 實(shí) ， 即 “ 從 時(shí) 刻 s所 處 的 狀 態(tài) a i，即 X(s)=ai出 發(fā) ， 經(jīng) 時(shí) 段 u+v轉(zhuǎn) 移 到 狀 態(tài) aj ,即 X(s+u+v） =aj”這 一 事 件 可 分 解 成 “ 從 X(s)=ai 出 發(fā) ， 先 經(jīng) 時(shí) 段 u轉(zhuǎn) 移 到 中間 狀 態(tài) ak(k,=1,2)， 再 從 ak經(jīng) 時(shí) 段 v轉(zhuǎn) 移 到 狀 態(tài) aj”這 樣 一些 事 件 和 事 件 (見(jiàn) 圖 11-4)。 圖 11

29、-4 方 程 (2.1)的 證 明 如 下 ： 先 固 定 ak I 和 s T1， 由 條 件概 率 定 義 和 乘 法 定 理 ， 有 )(.)()( )(,)()( )()( )()(,)( 馬 氏 性 和 齊 次 性 vPuP asXausXavusXP asXausXP asXausXavusXP kjik ikj ik ikj (2.2) 又 由 于 事 件 組 “ X(s+u)= ak”,k=1,2,構(gòu) 成 一 劃 分 ， 故 有)(|)(,)( )()()( 1 ikjk ijij asXausXavusXP asXavusXPvuP 將 (2.2)式 代 入 上 式 ， 即

30、得 所 要 證 明 的 C-K 方 程 。 C-K 方 程 也 可 寫(xiě) 成 矩 陣 形 式 ： P(u+v)=P(u)P (v) (2.1) 利 用 C-K 方 程 我 們 容 易 確 定 n步 轉(zhuǎn) 移 概 率 。 事 實(shí) 上 ，在 (2.1) 式 中 令 u=1,v=n-1， 得 遞 推 關(guān) 系 ： P(n)= P(1) P(n-1) =PP(n-1), 從 而 可 得 P(n)= P n. (2.3)就 是 說(shuō) ， 對(duì) 齊 次 馬 氏 鏈 而 言 ， n步 轉(zhuǎn) 移 概 率 矩 陣 是 一 步 轉(zhuǎn)移 概 率 矩 陣 的 n次 方 。 進(jìn) 而 可 知 ， 齊 次 馬 氏 鏈 的 有 限 維 分

31、 布 可 由 初 始 與 一步 轉(zhuǎn) 移 概 率 完 全 確 定 。 例 1 設(shè) Xn,n0是 具 有 三 個(gè) 狀 態(tài) 0,1,2的 齊 次 馬 氏 鏈 ， 一步 轉(zhuǎn) 移 概 率 矩 陣 為初 始 分 布 pi(0)=PX0=i=1/3, i=0,1,2.試 求 : (i) PX0=0, X2=1; (ii) PX2=1解 先 求 出 二 步 轉(zhuǎn) 移 概 率 矩 陣于 是 (i) ;48516531)2()0( 0101,0 010 02020 Pp XXPXPXXP(ii) 由 (1.7)式 ， .2411)16921165(31)2()0( )2()0()2()0(1)2( 212 1110

32、1021 Pp PpPpXPp 例 2 在 1例 2中 ,(i)設(shè) p=0.9 , 求 系 統(tǒng) 二 級(jí) 傳 輸 后 的 傳 真 率 與三 級(jí) 傳 輸 后 的 誤 碼 率 ； (ii)設(shè) 初 始 分 布 P1 (0)= PX0 =1= ， P0 (0) =P X0 = 0=1- ， 又 已 知 系 統(tǒng) 經(jīng) n級(jí) 傳 輸 后 輸 出 為 1，問(wèn) 原 發(fā) 字 符 也 是 1的 概 率 是 多 少 ？解 先 求 出 n步 轉(zhuǎn) 移 概 率 矩 陣 P(n)= Pn。 由 于有 相 異 的 特 征 值 1=1,2=p-q,由 線 形 代 數(shù) 知 識(shí) ， 可 將 P表 示成 對(duì) 角 陣的 相 似 矩 陣 。

33、 具 體 做 法 是 ： 求 出 1, 2對(duì) 應(yīng) 的 特 征 相 量(q=1-p) qp0 01,0 0, 11 2/1 2/11e 2/1 2/12e 令 2/12/1 2/12/1, 21 eeH則 nnnn nnn qp qpqp qp HHHHP )(2121 )(2121)(2121 )(2121 )( 11 (2.4) (i)由 (2.4)式 可 知 ， 當(dāng) p=0.9時(shí) ， 系 統(tǒng) 經(jīng) 二 級(jí) 傳 輸 后 的 傳 真 率 與 三級(jí) 傳 輸 的 誤 碼 率 分 別 為 244.0)1.09.0(2121)3()3( 820.0)1.09.0(2121)2()2( 20110 200

34、11 PP PP (ii)根 據(jù) 貝 葉 斯 公 式 ， 當(dāng) 已 知 系 統(tǒng) 經(jīng) n級(jí) 傳 輸 后 輸 出 為 1， 原 發(fā) 字符 也 是 1的 概 率 為 0 00 1 1 1 1 1 1nn np X p X Xp X X p X 1 110 01 1 11(0) ( ) ( )(0) ( ) (0) ( ) 1 (2 1)( )n np p n p qp p n p p n p q 對(duì) 于 只 有 兩 個(gè) 狀 態(tài) 的 馬 氏 鏈 ， 一 步 轉(zhuǎn) 移 概 率 矩 陣 一般 可 表 示 為 ： .1,011 ba bb aaP ，利 用 類(lèi) 似 于 例 2的 方 法 ， 可 得 n步 轉(zhuǎn) 移

35、 概 率 矩 陣 為 )5.2(.,2,1 )1(1 )()( )()()( 1110 0100 n bb aaba baab abba nPnP nPnPPnP nn ， 11.3 遍 歷 性 對(duì) 于 一 般 的 兩 個(gè) 狀 態(tài) 的 馬 氏 鏈 ， 由 (2.5)式 可 知 ,當(dāng) 0a, b1 時(shí) 就 可 得 到 n步 轉(zhuǎn) 移 概 率 的 近 似值 ： pij(n) j .)(lim)(lim .)(lim)(lim 1101 0100 1nn 0nn baanPnP babnPnP 記 成記 成 一 般 ， 設(shè) 齊 次 馬 氏 鏈 的 狀 態(tài) 空 間 為 I， 若 對(duì) 于 所 有ai,aj

36、 I， 轉(zhuǎn) 移 概 率 Pij (n)存 在 極 限 )()(lim i np jijn 不 依 賴 于 . . . . .)( 21 21 21)( jjjnnpnp 或則 稱 此 鏈 具 有 遍 歷 性 ， 又 若 ， 則 同 時(shí) 稱 為 鏈 的 極 限 分 布 。 齊 次 馬 氏 鏈 在 什 么 條 件 下 才 具 有 遍 歷 性 ？ 如 何 求 出 它 的極 限 分 布 ？ 這 問(wèn) 題 在 理 論 上 已 經(jīng) 完 滿 解 決 ,下 面 僅 就 只 有 有 限個(gè) 狀 態(tài) 的 鏈 ,即 有 限 鏈 的 遍 歷 性 給 出 一 個(gè) 充 分 條 件 。1j j ,.),( 21 定 理 設(shè) 齊

37、 次 馬 氏 鏈 Xn ,n 1的 狀 態(tài) 空 間 為 I= a1 ,a2 ,aN, P是 它 的 一 步 轉(zhuǎn) 移 概 率 矩 陣 ， 如 果 存 在 整 數(shù) m ， 使 對(duì) 任 意 的ai ,aj I， 都 有 Pij (m)0, i,j=1,2,N, (3.1)則 此 鏈 具 有 遍 歷 性 ,且 有 極 限 分 布 =(1, 2, , N)， 它 是 方 程組 =P或 即 (3.2)的 滿 足 條 件 (3.3)的 唯 一 解 。 依 照 定 理 ， 為 證 有 限 鏈 是 遍 歷 的 ， 只 需 要 找 一 正 整 數(shù) m， 使 m步 轉(zhuǎn) 移 概 率 矩 陣 P m無(wú) 零 元 。 而

38、求 極 限 分 布 的 問(wèn) 題 ， 化 為 求 解方 程 組 (3.2)的 問(wèn) 題 。 注 意 ， 方 程 組 (3.2)中 僅 N-1個(gè) 未 知 數(shù) 是 獨(dú)立 的 ， 而 唯 一 解 可 用 歸 一 條 件 確 定 。 NjpijNi ij ,.,2,1,1 1,0 1 Nj jj 11 nj j 在 定 理 的 條 件 下 ， 馬 氏 鏈 的 極 限 分 布 又 是 平 穩(wěn) 分 布 。意 即 ， 若 用 作 為 鏈 的 初 始 分 布 ， 即 p(0)= ,則 鏈 在 任 一 時(shí)刻 n T1的 分 布 p(n)永 遠(yuǎn) 與 一 致 。 事 實(shí) 上 ， 有 p(n)= p(0) p(n)= p

39、n = pn-1 = = p = 000 000000 000)4( 000 0000000 00 00 00 00000000 00 00 00 0000)2( 42PP PP例 1 試 說(shuō) 明 1例 2中 ， 帶 有 兩 個(gè) 放 射 壁 的 隨 機(jī) 游 動(dòng) 是 遍歷 的 ， 并 求 其 極 限 分 布 (平 穩(wěn) 分 布 )。解 為 簡(jiǎn) 便 計(jì) ， 以 符 號(hào) “ ”代 表 轉(zhuǎn) 移 概 率 矩 陣 的 正 元 素 ，于 是 ， 由 1例 2中 的 一 步 轉(zhuǎn) 移 概 率 矩 陣 P， 得 即 P(4)無(wú) 零 元 。 由 定 理 ， 鏈 是 遍 歷 的 。 再 根 據(jù) (3.2)和 (3.3)

40、式 ,寫(xiě) 出 極 限 分 布 = ( 1, 2, 5)滿 足 的 方 程 組先 由 前 四 個(gè) 方 程 ， 解 得 ： 3 1= 2= 3= 4=3 5 ， 將 它 們 代入 歸 一 條 件 ， 即 最 后 一 個(gè) 方 程 ， 解 之 ， 得 唯 一 解 ： 1= 5=1/11, 2= 3= 4=3/11所 以 極 限 分 布 為 =(1/11,3/11,3/11,3/11,1/11)。 這 個(gè) 分 布 表 明 ：經(jīng) 過(guò) 長(zhǎng) 時(shí) 間 游 動(dòng) 之 后 ， 醉 漢 Q位 于 i點(diǎn) (1i5)的 概 率 約 為 3/11，位 于 點(diǎn) 1(或 5)的 概 率 約 為 1/11。 .1,3/1 ,3/1

41、3/1 3/13/13/1 ,3/13/1 ,3/1 54321 45 5434 ,4323 3212 21 例 2 試 說(shuō) 明 1例 4(排 隊(duì) 模 型 )中 的 鏈 是 遍 歷 的 ， 并 求 其極 限 分 布 。解 依 照 例 1， 由 1例 4中 的 一 步 轉(zhuǎn) 移 概 率 矩 陣 P， 可 算得 P(3)= P3 無(wú) 零 元 。 根 據(jù) 定 理 ， 鏈 是 遍 歷 的 。 而 極 限 分布 = ( 0, 1, 2, 3)滿 足 下 列 方 程 組 : 解 之 ， 得 唯 一 解 .1 ,)1()1( ,)1()1)(1()1( ,)1()1)(1( ,)1()1( 3210 323

42、3212 2101 100 ppqpq qpqppqpq qpqppqq qpq .)1()1)(1()1()1( /)1(,/)1)(1( ,/)1(,/)1( 2322233 23322 221330 pqqppqqqpqpC CpqCqppq CqqpCqp 其 中 假 若 在 此 例 中 ， 設(shè) p = q = 1/2， 則 可 算 得 0 = 1/7 0.14, 1= 2= 3=2/7 0.29,即 此 時(shí) 極 限 分 布 為 =(1/7,2/7,2/7,2/7).這 就 是 說(shuō) ， 經(jīng) 過(guò) 相 當(dāng) 長(zhǎng) 的 時(shí) 間 后 ， 系 統(tǒng) 中 無(wú) 人 的 情 形 約 占14%的 時(shí) 間 ，

43、而 系 統(tǒng) 中 有 一 人 、 二 人 、 三 人 的 情 形 各 占 29%的 時(shí) 間 。例 3 設(shè) 一 馬 氏 鏈 的 一 步 轉(zhuǎn) 移 概 率 矩 陣 為試 討 論 它 的 遍 歷 性 。 02/102/1 2/102/10 02/102/1 2/102/10P 解 先 算 得 2/102/10 02/102/1 2/102/10 02/102/1)2( 2PP進(jìn) 一 步 可 驗(yàn) 證 ： 當(dāng) n為 奇 數(shù) 時(shí) ， P(n)=P(1)=P； n為 偶 數(shù) 時(shí) ，P(n)=P(2) 。 這 表 明 對(duì) 任 一 固 定 的 j (=1,2,3,4)， 極 限都 不 存 在 。 按 定 義 ， 此

44、 鏈 不 具 遍 歷 性 。 )(lim npijn 馬 氏 過(guò) 程 的 內(nèi) 容 除 了 討 論 最 簡(jiǎn) 情 形 馬 氏 鏈 之 外 ，還 研 究 狀 態(tài) 離 散 、 時(shí) 間 連 續(xù) 的 馬 氏 過(guò) 程 和 狀 態(tài) 、 時(shí) 間 都 連續(xù) 的 馬 氏 過(guò) 程 ， 它 們 都 有 比 較 完 善 的 理 論 ， 而 且 討 論 的 主題 也 都 是 從 各 自 場(chǎng) 合 的 C-K 方 程 出 發(fā) ， 研 究 轉(zhuǎn) 移 概 率 的 確定 方 法 和 性 質(zhì) 。 本 書(shū) 除 前 面 介 紹 的 泊 松 過(guò) 程 和 維 納 過(guò) 程 這兩 個(gè) 具 體 的 馬 氏 過(guò) 程 模 型 外 不 再 作 一 般 的 介 紹 。