【正文】 65 . 討 論 上 節(jié) 例 3 各 狀 態(tài) 性 質(zhì) ， 計 算 正 常 態(tài) 的 平 均例 4 回 轉(zhuǎn) 時 。1 2 3{ 0 }, { 1 , 2 } { 3 , 4 } { 5 } { 5 }C C C? ? ?有 四 個 等 價 類 ， 和 ， 只 有 不 閉 。解 ：0 1 2 3 4? ， ， ， ， 正 常 返 ， 5 暫 留 ，1 210 1 2 5 3 4， ， ， 非 周 期 ， ， 周 期 為 2001 ???是 吸 收 態(tài) ，22{ } Ma r kovnX C C把 限 制 在 上 得 到 一 個 遍 歷 鏈 ， 狀 態(tài) 空 間 為0 1 2 3 4 51111 1212, ) ( , )33?? ?平 穩(wěn) 分 布 ( 123, ) ( 3 , )2????(浙江大學(xué)隨機(jī)過程 66 33{ } M a r k o v.nXCC把 限 制 在 上 得 到 一 個 不 可 約 正 常 返 周 期 為 2 的 鏈 ，狀 態(tài) 空 間 為3 4113411, ) ( , )22?? ?平 穩(wěn) 分 布 (34, ) ( 2 , 2)????(浙江大學(xué)隨機(jī)過程 67 (), 0 , 1 l i m nijni j p???. 在 01 傳 輸 問 題 中 ， 對 , 存 在 嗎 ？如 存 在例 5， 計 算 之 。()00 00 | 0n np P X X? ? ?： （方 法 一 ）ppqq0 1k n kkn qpk????????偶 數(shù)＝( n )P= 前 次 傳 輸 中 誤 碼 偶 數(shù) 次1 [ ( ) ]2k n k k n kkknnq p q pkk??? ? ? ?? ? ?? ? ? ?? ? ? ???11[ ( ) ( ) ] [ 1 ( 2 1 ) ]22 n n np q q p p? ? ? ? ? ? ? ?浙江大學(xué)隨機(jī)過程 68 ()00 00 | 0n np P X X? ? ?： （方 法 一 ）ppqq0 111[ ( ) ( ) ] [ 1 ( 2 1 ) ]22 n n np q q p p? ? ? ? ? ? ? ?() 11 0 1 , l i m2nijnp p i j??? ? ? ?（ ） 若 則 ， ，（ 極 限 與 出 發(fā) 點(diǎn) 無 關(guān) ）()3 0 , l im nijnp i j p????（ ） 若 則 ， ， 不 存 在( ) ( ) ( ) ( )0 0 1 1 1 0 0 12 1 , l im l im 1 l im l im 0n n n nn n n np p p p p? ? ? ? ? ? ? ?? ? ? ? ?（ ） 若 則 ，（ 極 限 與 出 發(fā) 點(diǎn) 有 關(guān) ）浙江大學(xué)隨機(jī)過程 69 方 法 二 ：ppqq0 1( 0 ) 1 , { }ndX??又 遍 歷1 0 1 { 0 1 } { }npX??（ ） 若 ， 則 ， 是 閉 的 等 價 類 ， 所 以 正 常 返3 0 ,p ?（ ） 若2 1 ,p ?（ ） 若0111, ) ( , )22?? ?平 穩(wěn) 分 布 (() 1l im2nijn p i j??? ? ?， ，110 1110 1( ) ( )00 11( ) ( )10 01l i m l i m 1l i m l i m 0nnnnnnnnpppp? ? ? ?? ? ? ?????則 ，()l im nijni j p???則 ， ， 不 存 在浙江大學(xué)隨機(jī)過程 70 例 6：設(shè)有 6個球 (2個紅球 ,4個白球 )隨機(jī)平分放入甲 , 乙兩個盒中 .今每次從兩盒中各任取一球并進(jìn)行交換 . 表示開始時甲盒中的紅球數(shù) , 表示經(jīng) n次交換 后甲盒中的紅球數(shù) . (1)求此馬氏鏈的初始分布 。 (2)求一步轉(zhuǎn)移矩陣 。 (3)計算 0 2 4 2( 1 , 1 , 0 ) , ( 2 )P X X X P X? ? ? ?0X用 nX4 l im 25nn PX?? ?（ ） （ ） 存 在 嗎 ？ 如 存 在 ， 計 算 之 。（ ） 求 甲 盒 中 紅 球 數(shù) 變 沒 的 平 均 時 間 間 隔浙江大學(xué)隨機(jī)過程 71 0 1 3 2 3 0( 2) 1 2 9 5 9 2 9 ,2 0 2 3 1 3P?????????20 7 2 7 1 6 2 7 4 2 7( 3 ) 1 1 6 8 1 4 9 8 1 1 6 8 1 ,2 4 2 7 1 6 2 7 7 2 7P???????（ ）3 3 1 2 30 4 6 0 2 4 62 1 30 2 4 6( 0 ) 1 5 , ( 1 ) 3 5 ,( 2 ) 1 5 ,P X C C P X C C CP X C C C? ? ? ? ? ?? ? ?解 :(1)00 1 2~1 5 3 5 1 5X??????即 :024( 1 , 1 , 0)P X X X???( 2 ) ( 2 ) ( 2 )2 0 02 0 12 0 22( 2 ) ( 0 ) ( 1 ) ( 2 )P X P X p P X p P X p? ? ? ? ? ? ?3 5 49 81 16 81 235 2 328 05 ? ? ? ? ?( 2 ) ( 2 )0 11 10( 1 )P X p p??1 5 4 27 3 5 16 81 1 5 7 27 1 5 ? ? ? ? ? ? ? ?浙江大學(xué)隨機(jī)過程 72 ( 4) ( 0 1d ??） ， 不 可 約 ， 遍 歷12395223 9 321931? ? ?? ? ? ?? ? ?? ? ?????? ? ??????? ? ? ??0 0 11 0 1 22 1 2012方 程 組? ?,? ? ? ?012設(shè) 平 穩(wěn) 分 布 = ，153515???????0120 1 213292313592923215l im 2nnPX ???? ? ?（ ） = 001( 5 ) 5????所 求 為浙江大學(xué)隨機(jī)過程 73 平穩(wěn)分布的意義 11 2 ,2 1 1 1{ , ...} ,2 , ( , , ),2,1knnnkkXk X Xn n n n n? ? ?????? ? ?設(shè) 初 始 分 布 為 平 穩(wěn) 分 布 ＝ 則 所 有 的 分 布 均 為 ， 對 的 分 布 僅 與 時 間 差 有 關(guān) ， 與 時 間 起 點(diǎn)（ ）（ ）無 關(guān) 。當(dāng) 初 始 分 布 為 時 ， Markov 鏈 嚴(yán) 平平 穩(wěn) 為分 布 穩(wěn) 過 程 。浙江大學(xué)隨機(jī)過程 74 123 2 12111 , 2 2 , 3 1 ,3 2 12111 , 2 2 , 3 1 ,111121().2 ( , , )( ) .. ....kkki i i i i ikkkki i i i i ikkn n nnnnn n n kn n n nnnnn n n nnniX P P P PXXP X i X i X iP X i p p pp p p? ? ??????????????? ? ? ????（ ） （ ）（ ）（ ） （ ）（ ）（ 1 ） 的 分 布 為 與 的 分 布 相 同 ， 所 以 所 有證均 為（ ）：的 分 布浙江大學(xué)隨機(jī)過程 75 Markov鏈的應(yīng)用 — PageRank PageRank, 就是網(wǎng)頁排名，又稱網(wǎng)頁級別，是一種由搜索引擎根據(jù)網(wǎng)頁之間相互的超鏈接計算的網(wǎng)頁排名技術(shù)， Google用它來體現(xiàn)網(wǎng)頁的重要性。是Google的創(chuàng)始人拉里 佩奇和謝爾蓋 布林在斯坦福大學(xué)發(fā)明了這項技術(shù) , 并最終以拉里 佩奇（ Larry Page）之姓來命名。 浙江大學(xué)隨機(jī)過程 76 Markov鏈的應(yīng)用 PageRank ? ?? ?P a ge R a nk P a ge R a nk 31. 2. 3. (是 基 于 「 從 許 多 優(yōu) 質(zhì) 的 網(wǎng) 頁 鏈 接 過 來 的 網(wǎng) 頁 ， 必 定 還 是 優(yōu) 質(zhì) 網(wǎng) 頁 」 的 回 歸 關(guān) 系 ， 來 判 定 所 有 網(wǎng) 頁 的 重 要 性 。提 高 的 要 點(diǎn) ， 大 致 有 個 :反 向 鏈 接 數(shù) 單 純 的 意 義 上 的 受 歡 迎 度 指 標(biāo)反 向 鏈 接 是 否 來 自 推 薦 度 高 的 頁 面 有 根 據(jù) 的 受 歡 迎 指 標(biāo)反 向 鏈 接 源 頁 面 的 鏈 接 數(shù) 被 選 中 的 幾 率 指 標(biāo) )浙江大學(xué)隨機(jī)過程 77 鏈接源 I D 鏈接目標(biāo) 1 1 2,3,4,5, 7 ? 2 1 ? 3 1,2 ? 4 2,3,5 ? 5 1,3,4,6 ? 6 1,5 ? 7 5 浙江大學(xué)隨機(jī)過程 78 ,{ } M a r kov ,0 1 / 5 1 / 5 1 / 5 1 / 5 0 1 / 51 0 0 0 0 0 01 / 2 1 / 2 0 0 0 0 00 1 / 3 1 / 3 0 1 / 3 0 01 / 4 0 1 / 4 1 / 4 0 1 / 4 01 / 2 0 0 0 1 / 2 0 00 0 0 0 1 0 0nnXX????????????????????訪 問 網(wǎng) 絡(luò) 可 看 成 是 在 這 些 網(wǎng) 絡(luò) 上 的 隨 機(jī) 游 動 每 次 都等 可 能 地 訪 問 所 在 網(wǎng) 頁 的 友 情 連 接 若 用 表 示 第 n 次訪 問 的 網(wǎng) 頁 , 則 是 鏈 轉(zhuǎn) 移 矩 陣 P=浙江大學(xué)隨機(jī)過程 79 152347P a geR a nk : ( 1 ) 0 , 1( 2) ( 03 5, 66 1, 40 6, 05 4, 78 9 , 44 7, 60 7)P a geR a nk :( 1 ) 03 5( 2) 78 9( 3 ) 66 1( 4) 40 6( 5 ) 05 4( 6) 6,j i jjijpj????????????????????????其 滿 足恰 好 為 平 穩(wěn) 分 布 . 解 得 :所 以 網(wǎng) 絡(luò) 的 評 價 排 名 為607( 7 ) 44 7? ?浙江大學(xué)隨機(jī)過程 80