（應(yīng)用數(shù)學(xué)專業(yè)論文）高階非齊次馬氏鏈的遍歷性及其應(yīng)用.pdf

江蘇大學(xué)碩士學(xué)位論文 摘要 在馬氏鏈理論研究領(lǐng)域中 遍歷性一直是一個(gè)饒有趣味并富有意義的課題 馬氏鏈遍歷性理論在生物 數(shù)值計(jì)算 信息理論 自動(dòng)控制 近代物理和公用事 業(yè)中的服務(wù)系統(tǒng)等眾多領(lǐng)域都有著廣泛的應(yīng)用 并顯示出至關(guān)重要的作用 本文主要研究高階非齊次馬氏鏈的遍歷性及其在遺傳算法中的應(yīng)用 通過(guò)引 入m 重有限非齊次馬氏鏈強(qiáng) 弱 遍歷性的概念 利用高階馬氏鏈的c k 方程及 高階馬氏鏈與一階馬氏鏈之間的轉(zhuǎn)化關(guān)系 分別給出了m 重有限非齊次馬氏鏈滿 足這種強(qiáng) 弱 遍歷性的幾個(gè)條件 將高階齊次馬氏鏈遍歷性的結(jié)果推廣到了高階 有限非齊次馬氏鏈上 在此基礎(chǔ)上 通過(guò)引入m 重可列非齊次馬氏鏈強(qiáng)遍歷性及 其絕對(duì)平均強(qiáng)遍歷性的定義 分別研究了m 重可列非齊次馬氏鏈滿足這種強(qiáng)遍歷 性和絕對(duì)平均強(qiáng)遍歷性的充分條件 本文還在引入m 重可列非齊次馬氏鏈c e s a r o 平均收斂概念的基礎(chǔ)上 給出并證明了m 重可列非齊次馬氏鏈的一個(gè)c e s a r o 平 均收斂定理 并討論了該定理在信息論中的應(yīng)用 最后 本文給出了高階馬氏鏈 在遺傳算法中的應(yīng)用 在描述了穩(wěn)定態(tài)遺傳算法中個(gè)體進(jìn)化過(guò)程的高階馬氏鏈模 型的基礎(chǔ)上 通過(guò)對(duì)算法進(jìn)行改進(jìn) 利用高階有限非齊次馬氏鏈的遍歷性證明了 改進(jìn)穩(wěn)定態(tài)遺傳算法是全局收斂的結(jié)論 關(guān)鍵詞 m 重非齊次馬氏鏈 遍歷性 收斂 遺傳算法 江蘇大學(xué)碩士學(xué)位論文 a b s t r a c t e r g o d i c i t yi sa l w a y sa ni n t e r e s t i n ga n dc h a l l e n g i n gr e s e a r c ht a s ki nt h ef i e l d so f m a r k o vt h e o r y t h ee r g o d i cf o rm a r k o vh a se x t e n s i v ea p p l i c a t i o na n dp l a y sa l l i m p o r t a n tr o l ei nt h ea r e a so fb i o l o g y n u m e r i c a lc a l c u l a t e t h e o r yo fi n f o r m a t i o n a u t o m a t i cc o m m a n d p h y s i t sa n dt h es e r v i c es y s t e mo f p u b l i ce n t e r p r i s e i nt h i sp a p e rw ep r i n c i p a l l yr e s e a r c he r g o d i cf o rm u l t i p l en o n h o m o g e n e o u sm a r k o v c h a i n sa n da p p l i c a t i o n t h en o t i o n so f t h es t r o n g l ye r g o d i ca n dw e a k l ye r g o d i cf o rmo r d e r f i n i t en o n h o m o g e n e o u sm a r k o vc h 鋤u sa r ed e f i n e d t h ec o n d i t i o n su n d e rw h i c hamo r d e r f i n i t en o n h o m o g e n e o u sm a r k o vc h a i n sp o s s e s s e st h ek i n do f s t r o n g l ye r g o d i ca n d w e a k l y e r g o d i c a r eo b t a i n e dr e s p e c t i v e l yb ya p p l y i n gt h er e l a t i o n sb e t w e e nm u l t i p l em a r k o v c h a i n sa n dm a r k o vc h a i n sa n dc ke q u a t i o no f t h em u l t i p l em a r k o vc h a i n s s o m er e s u l t s a b o u te r g o d i c 時(shí)f o rm u l t i p l eh o m o g e n e o u sm a r k o vc h a i n sa r ee x t e n d e dt om u l t i p l ef i n i t e n o n h o m o g e n e o u sm a r k o vc h a i n s b a s e do nt h i s t h en o t i o n so ft h es t r o n g l ye r g o d i ca n d a b s o l u t em e a ns t r o n g l ye r g o d i cf o rmo r d e rn o n h o m o g e n e o u sm a r k o vc h a i n sa l ed e f i n e d a n dt h ec o n d i t i o n su n d e rw h i c hamo r d e rn o n h o m o g e n e o n sm a r k o vc h a i n 5p o s s e s s e st h e k i n do fs t r o n g l ye r g o d i ca n da b s o l u t em e a ns t r o n g l ye r g o d i ca r er e s e a r c h e dr e s p e c t i v e l y i nt h i sp a p e r t h en o t i o no ft h ec o n v e r g e n c eo fc e s a r oa v e r a g e sf o rmo r d e r n o n h o m o g e n e o u sm a r k o vc h a i n si si n t r o d u c e d b a s e do nt h i s w ep r o v eac o n v e r g e n c e t h e o r e mf o rc e s a r oa v e r a g e sf o rmo r d e rn o n h o m o g e n e o u sm a r k o vc h a i n s a n dd i s c u s st h e a p p l i c a t i o no ft h i st h e o r e mo nt h ei n f o r m a t i o nt h e o r y f i n a l l y w eg i v et h ea p p l i c a t i o no f m u l t i p l em a r k o vc h a i n so nt h eg e n e t i ca l g o r i t h m s b a s e do nd e s c r i b i n gm u l t i p l em a r k o v c h a i n so fi n d i v i d u a l s 證t h es t e a d ys t a t eg e n e t i ca l g o r i t h m w ei m p r o v et h ea l g o t i t h ma n d p r o v et h a tt h ei m p r o v e ds t e a d ys t a t eg e n e t i ca l g o r i t h mi sg l o b a lc o n v e r g e n c e b ya p p l y i n g e r g o d i cf o rm u l t i p l ef i n i t en o n h o m o g e n e o u sm a r k o v c h a i n s k e yw o r d s mo r d e rn o n h o m o g e n e o u sm a r k o vc h a i n s e r g o d i c i t y c o n v e r g e n c e g e n e t i ca l g o r i t h m s i i 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留 使用學(xué)位論文的規(guī)定 同意學(xué)校保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版 允許論文被查閱和借閱 本人授權(quán)江蘇大學(xué)可以將本學(xué)位論文的全部 內(nèi)容或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索 可以采用影印 縮印或掃 描等復(fù)制手段保存和匯編本學(xué)位論文 本學(xué)位論文屬于 保密口 在年解密后適用本授權(quán)書 不保密回 學(xué)位論文作者簽名 汪炎 指導(dǎo)教師簽名 詘占年f 2 月f r 日坳彳年1 2 月f f 日 獨(dú)創(chuàng)性聲明 本人鄭重聲明 所呈交的學(xué)位論文 是本人在導(dǎo)師的指導(dǎo)下 獨(dú) 立進(jìn)行研究工作所取得的成果 除文中已注明引用的內(nèi)容以外 本論 文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過(guò)的作品成果 對(duì)本文 的研究做出重要貢獻(xiàn)的個(gè)人和集體 均已在文中以明確方式標(biāo)明 本 人完全意識(shí)到本聲明的法律結(jié)果由本人承擔(dān) 學(xué)位論文作者簽名 汪炎 江蘇大學(xué)碩士學(xué)位論文 第一章緒論 馬爾可夫過(guò)程是一類重要的隨機(jī)過(guò)程 它的原始模型馬爾可夫鏈 簡(jiǎn)稱馬氏 鏈 由俄國(guó)數(shù)學(xué)家a a m a r k o v 于1 9 0 7 年提出 由于馬爾可夫過(guò)程在物理學(xué) 生物科學(xué) 信息理論 自動(dòng)控制 工程技術(shù)及數(shù)值計(jì)算等方面起到的異乎尋常的 作用 使得人們?cè)絹?lái)越重視馬爾可夫過(guò)程的理論及其應(yīng)用的研究 卜7 在馬爾可夫過(guò)程研究領(lǐng)域中 馬氏鏈的遍歷性一直是一個(gè)饒有趣味并富有意 義的課題 它主要是研究馬氏鏈轉(zhuǎn)移概率矩陣的收斂性即研究馬氏鏈的穩(wěn)定性 在一定意義下 基于具體模型分析 依據(jù)穩(wěn)定性給模型分類是首要的最基本的操 作 且馬氏鏈理論適用于幾乎所有領(lǐng)域 1 因此 對(duì)馬氏鏈穩(wěn)定性的研究尤為 重要 遺傳算法 g e n e t i ca l g o r i t h m g a s 是一類模擬達(dá)爾文自然進(jìn)化論與蒙代 爾遺傳變異的仿生優(yōu)化技術(shù) 從數(shù)學(xué)的觀點(diǎn)上說(shuō) 它是一類借喻生物進(jìn)化特別是 遺傳學(xué)術(shù)語(yǔ)與原理的仿生優(yōu)化方法 由于遺傳算法下一代種群的狀態(tài)通常完全依 賴當(dāng)前種群信息 而不依賴于以往狀態(tài) 故可自然地用馬氏鏈描述 近年來(lái) 人 們對(duì)遺傳算法收斂性的馬氏鏈分析開展了大量的研究 取得了許多深刻的結(jié)果 e i b e n 8 f o g e l 9 q i 和p a l m i e r i i 0 r u d o l p h 1 i r e y n o l d s 和g o m a t a m 1 2 等人對(duì)編碼方式和選擇策略不同的遺傳算法分別建立了種群的不同馬氏鏈模型 有條件地得出了全局收斂性分析的理論結(jié)果 馬氏鏈理論在遺傳算法收斂性分析 中已經(jīng)顯示出十分重要的理論價(jià)值和廣闊的發(fā)展?jié)摿?1 1 研究背景 1 1 1 馬氏鏈的直觀背景 馬爾可夫鏈 簡(jiǎn)稱馬氏鏈 是一種特殊的隨機(jī)過(guò)程 最初由a a m a r k o v 所 研究 它的直觀背景如下 設(shè)想有一個(gè)隨機(jī)運(yùn)動(dòng)的體系 例如運(yùn)動(dòng)著的質(zhì)點(diǎn)等 它可能處的狀態(tài) 或 位置 記為s s 最 總數(shù)共有可列多個(gè)或有窮個(gè) 這體系只可能在時(shí)刻 江蘇大學(xué)碩士學(xué)位論文 t 1 2 上改變它的狀態(tài) 隨著 的運(yùn)動(dòng)過(guò)程 定義一列隨機(jī)變量 以 珂 0 1 2 其中 以 k 如在t n 時(shí) 位于s 一般地 以 未必是相互獨(dú)立的 實(shí)際中常常碰到具有下列性質(zhì)的運(yùn)動(dòng)體系 如果已知它在t 片時(shí)的狀態(tài) 則關(guān)于它在行時(shí)以前所處的狀態(tài)的補(bǔ)充知識(shí) 對(duì)預(yù)言 在n 時(shí)以后所處的狀態(tài)不 起任何作用 或者說(shuō) 在已知 現(xiàn)在 的條件下 將來(lái) 與 過(guò)去 是獨(dú)立的 這種性質(zhì) 就是直觀意義上的 馬爾可夫性 簡(jiǎn)稱 馬氏性 或稱 無(wú)后效 性 具有這種特性的隨機(jī)過(guò)程稱為馬爾可夫過(guò)程 簡(jiǎn)稱馬氏過(guò)程 荷花池中的一只青蛙的跳躍是馬爾可夫過(guò)程的一個(gè)形象化例子 青蛙按照它 瞬間跳起的念頭從一片荷葉上跳躍到另一片荷葉上 如果青蛙是沒有記憶的 人 們自然可以假定 當(dāng)已知青蛙在某時(shí)刻所處的位置時(shí) 它下一步跳往何處與它此 前走過(guò)的路徑無(wú)關(guān) 如果將荷葉編號(hào) 例如編號(hào)為自然數(shù)l 2 3 并用墨 表示青蛙在初始時(shí)刻所處的荷葉的號(hào)碼 用墨 托 分別表示青蛙經(jīng)過(guò)第一次 第二次 跳躍后所處的荷葉的號(hào)碼 那么 隨機(jī)序列 瓦 以 o 就是一個(gè)馬 爾可夫過(guò)程 1 1 2 馬氏鏈遍歷性的研究進(jìn)展 馬氏鏈理論是隨機(jī)過(guò)程理論中較早開始研究并得到較廣泛應(yīng)用的一個(gè)理論 分支 而馬氏鏈遍歷性理論又是馬氏鏈理論中的基本內(nèi)容之一 1 9 4 8 年 s h a n n o n 首先證明遍歷齊次馬爾科夫鏈的極限是存在的 1 9 5 7 年 b r i e m a n n 證明了平穩(wěn) 遍歷的馬爾科夫鏈的極限是存在的 d i s a a c s o n r m a d s e n 等人在二十世紀(jì)七 十年代提出了馬氏鏈的弱遍歷性 強(qiáng)遍歷性 c e s a r o 平均收斂 又稱c 一強(qiáng)遍歷 性 就是轉(zhuǎn)移概率矩陣列的各種收斂形式 1 3 隨后 對(duì)于非齊次馬氏鏈轉(zhuǎn)移 概率矩陣列的各種收斂性質(zhì) d i s a a c s o n b b o w e r m a n h t d a v i d b e t h o a d e s 等人相繼作了一些深入研究 1 9 7 6 年 c h e n g c h ih u a n g d i s a a c s o n 和 2 江蘇大學(xué)碩士學(xué)位論文 b v i n a g r a d e 等人首先研究并論證了一齊次馬氏鏈的轉(zhuǎn)移概率矩陣p 強(qiáng)遍歷 隨 后又研究了轉(zhuǎn)移概率矩陣列 只 1 收斂于一強(qiáng)遍歷轉(zhuǎn)移概率矩陣的非齊次馬 氏鏈的性質(zhì) 1 4 1 9 7 7 年 b b o w e r m a n h t d a v i d 和d i s a a c s o n 等人提出了 周期強(qiáng)遍歷隨機(jī)矩陣的概念 并論證了一非齊次馬氏鏈轉(zhuǎn)移概率矩陣列收斂于一 周期強(qiáng)遍歷矩陣 即該馬氏鏈的c e s a r o 平均收斂性 1 5 1 9 7 9 年 b e r h o a d e s 也討論了轉(zhuǎn)移概率矩陣列收斂于周期強(qiáng)遍歷矩陣的非齊次馬氏鏈 引進(jìn)無(wú)限正規(guī) 矩陣的概念 論證了該馬氏鏈比c e s a r o 平均收斂更強(qiáng)的結(jié)論 1 6 隨后 楊衛(wèi) 國(guó)于1 9 9 4 年提出馬氏鏈絕對(duì)平均強(qiáng)遍歷的概念 并給出非齊次馬氏鏈滿足這種 強(qiáng)遍歷的充分條件 得到非齊次馬氏鏈熵率存在的一個(gè)定理 1 7 1 8 陳永義等 人于1 9 9 6 年利用兩個(gè)非齊次馬氏鏈的轉(zhuǎn)移概率矩陣列的比較 討論了兩個(gè)鏈遍 歷性的關(guān)系 得到一個(gè)非齊次馬氏鏈?zhǔn)菑?qiáng)遍歷的一些充分條件 并且分析了非齊 次馬氏鏈的一致強(qiáng) 弱遍歷的關(guān)系 得到一個(gè)非齊次馬氏鏈?zhǔn)且恢聫?qiáng)遍歷的一些 充分條件 1 9 但是 對(duì)于非齊次馬氏鏈轉(zhuǎn)移矩陣列收斂尤其是收斂于周期強(qiáng)遍 歷矩陣性質(zhì)的研究很少有人做 直到九十年代末 楊衛(wèi)國(guó)在前人研究的基礎(chǔ)上 進(jìn)一步減弱條件 研究一類更廣泛的非齊次馬氏鏈 得到該馬氏鏈c e s a r o 平均 收斂的條件 推廣了b o w e r m a n 的一個(gè)結(jié)論 1 5 并應(yīng)用到馬氏決策過(guò)程和信息 論中 2 0 2 1 隨著馬氏鏈理論的不斷發(fā)展和應(yīng)用 人們對(duì)高階馬氏鏈的理論和 應(yīng)用也越來(lái)越有興趣 2 0 0 2 年 楊衛(wèi)國(guó)等人研究了非齊次m 階馬氏信源的漸進(jìn) 均分割性 2 2 之后又于2 0 0 4 年利用鞅的方法 給出了二重非齊次馬氏鏈三元 函數(shù)的幾個(gè)強(qiáng)極限定理 作為特例 將賭博系統(tǒng)的隨機(jī)變換概念推廣到二重馬氏 鏈情形 得到了二重馬氏鏈隨機(jī)選擇與隨機(jī)公平比的若干極限定理 2 3 1 2 本文的研究方法和主要解決的問題 本文是在楊衛(wèi)國(guó)教授研究的非齊次m 階馬氏信源的漸進(jìn)均分割性的基礎(chǔ)上 進(jìn)一步研究高階非齊次馬氏鏈的遍歷性及其在遺傳算法中的應(yīng)用 通過(guò)采用將高 階非齊次馬氏鏈轉(zhuǎn)化為一階非齊次馬氏鏈的方法 把研究高階有限非齊次馬氏鏈 遍歷性問題轉(zhuǎn)化成研究一階多維有限非齊次馬氏鏈遍歷性問題 并在建立高階非 齊次馬氏鏈c k 方程的基礎(chǔ)上 通過(guò)任取一m 階轉(zhuǎn)移矩陣p 規(guī)定由p 所確定的 3 江蘇大學(xué)碩士學(xué)位論文 m 維轉(zhuǎn)移矩陣f 是遍歷的 討論兩個(gè)高階非齊次馬氏鏈之間的遍歷性關(guān)系 并利 用高階馬氏鏈與一階馬氏鏈之間的轉(zhuǎn)化關(guān)系 研究m 重可列非齊次馬氏鏈的 c e s a r o 平均收斂性及其在信息論中的應(yīng)用 最后通過(guò)對(duì)遺傳算法中個(gè)體進(jìn)化過(guò) 程的高階馬氏鏈模型的描述 利用高階有限非齊次馬氏鏈之間的遍歷性關(guān)系 研 究遺傳算法的全局收斂性 1 3 本文的組織 本文旨在研究高階非齊次馬氏鏈的遍歷性 在此基礎(chǔ)上 通過(guò)對(duì)遺傳算法中 個(gè)體進(jìn)化過(guò)程的高階馬氏鏈模型的描述 研究遺傳算法的全局收斂性 本文共分為五章 第一章概述了馬氏鏈的直觀背景及馬氏鏈遍歷性的研究進(jìn)展 并對(duì)本文內(nèi) 容做一整體介紹 第二章介紹了后續(xù)章節(jié)所需要用到的基本理論知識(shí)與概念 第三章在給出商階非齊次馬氏鏈各種遍歷性定義的基礎(chǔ)上 利用高階馬氏 鏈c k 方程及高階馬氏鏈與一階馬氏鏈之間的轉(zhuǎn)化關(guān)系 討論了高階非齊次馬氏 鏈滿足各種遍歷性的條件 第四章通過(guò)引入高階可列非齊次馬氏鏈c e s a r o 平均收斂的概念 利用高 階馬氏鏈與一階馬氏鏈之間的轉(zhuǎn)化關(guān)系 研究了高階可列非齊次馬氏鏈的c e s a r o 平均收斂性 并討論了該收斂性在信息論中的應(yīng)用 第五章描述了穩(wěn)定態(tài)遺傳算法中個(gè)體進(jìn)化過(guò)程的高階馬氏鏈模型 并通過(guò) 對(duì)穩(wěn)定態(tài)遺傳算法進(jìn)行改進(jìn) 利用高階有限非齊次馬氏鏈的遍歷性證明了改進(jìn)后 的算法是全局收斂的結(jié)論 4 江蘇大學(xué)碩士學(xué)位論文 第二章基本理論與概念 在這一章中 我們給出了馬氏鏈數(shù)學(xué)上的嚴(yán)格定義和馬氏鏈遍歷性的基本理 論 并給出了后面幾章節(jié)內(nèi)容所涉及到的相關(guān)定義 性質(zhì)與定理 2 1 馬氏鏈的定義及基本概念 2 1 1 馬氏鏈的定義和性質(zhì) 在 i 1 1 中我們對(duì)馬氏鏈的特征作了直觀性的描述 雖然能夠作為判斷實(shí) 際生活中隨機(jī)現(xiàn)象的依據(jù) 但是直觀上的馬氏性弗不能作為理論研究的依據(jù) 因 而必須模型化 給出數(shù)學(xué)上的嚴(yán)格定義 由此引出了本節(jié)中的一系列基本概念 相對(duì)于一隨機(jī)試驗(yàn) 設(shè)q 是所有樣本點(diǎn) 構(gòu)成的樣本空間 f 是q 上的所 有隨機(jī)事件構(gòu)成的事件集合稱為盯一代數(shù) p 是定義在于上的概率測(cè)度即概率 稱定義在概率空間 q f p 上的隨機(jī)變量族x 置 口 t 為一隨機(jī)過(guò)程 其 中丁為一參數(shù)集 若r 是一個(gè)含有可列多個(gè)元素的無(wú)限集 例如 暇 盯 0 1 稱為離散參數(shù)的隨機(jī)過(guò)程或隨機(jī)序列 一個(gè)隨機(jī)過(guò)程所有可能 取值的集合稱為該過(guò)程的狀態(tài)空間 記作s 如果s 是可列集或有限集 則稱此 過(guò)程為鏈 下面給出馬氏鏈的嚴(yán)格定義 定義2 1 1 設(shè)x x n 甩 0 l 是定義在概率空間 q f p 上的離散參 數(shù)隨機(jī)過(guò)程 狀態(tài)空間s 為可列集或有限集 如果z 具有由下式定義的馬爾可夫 性 簡(jiǎn)稱馬氏性 即對(duì)任意的非負(fù)整數(shù)療及任意的狀態(tài)乇 i l 厶 s 只要p i o x i 以 0 總有 p z l x o i o 置 瓦 p 以 i 以 2 1 1 成立 則稱z 為馬氏鏈 若s 為可列集或有限集 則稱x 分別依次為可列馬氏 鏈和有限馬氏鏈 在本章中 2 1 1 就是馬氏性的正式定義 它是上一章中直觀意義上的馬 氏性的數(shù)學(xué)抽象 江蘇大學(xué)碩士學(xué)位論文 定義2 1 2 設(shè)x 以 門 0 1 是馬氏鏈 其狀態(tài)空間s 不妨取為 l 2 或 1 2 n x 在時(shí)刻胛處于i 狀態(tài)的條件下 經(jīng)過(guò)m 步轉(zhuǎn)移 在時(shí)刻 l m 到達(dá)j 狀態(tài)的條件概率 以 i 以 f 稱為x 的m 步轉(zhuǎn)移概率 記為 p lf 特別令 娃驀 億m 以 p i i f f f j 第i 行第 列的元素排成的矩陣 p 4 p if 2 1 3 稱為x 的m 步轉(zhuǎn)移矩陣 當(dāng)m 1 時(shí) 將 1 l f p 1 分別簡(jiǎn)記為以 i f 只 定義2 1 3 馬氏鏈稱為齊次的 如果對(duì)一切f s 它的轉(zhuǎn)移概率p z j l f 都與行無(wú)關(guān) 即 p o j i f a i i p 2 j l f p j i i 或 e o 只 是 p 如果與n 有關(guān) 則稱x 為非齊次的 引理2 1 1 參見文獻(xiàn) 6 p 6 對(duì)任何正整數(shù)m 及非負(fù)整數(shù)h 馬氏鏈的 轉(zhuǎn)移概率矩陣 p p p 滿足下列方程 p 4 l j p p 2 1 4 即 p 巾 p 4 k l d 舯 p 氣 l 2 1 5 稱式 2 1 4 或 2 1 5 為切普曼一柯爾莫哥洛夫方程 簡(jiǎn)稱c k 方程 2 1 2 高階馬氏鏈的定義及性質(zhì) 定義2 1 4設(shè) 瓦 o 1 是定義在概率空間 q f p 上的隨機(jī)變量序 列 狀態(tài)空間s 是可列集或有限集 m l 為整數(shù) 如果對(duì)任意整數(shù)n m 一1 及 t s 0 i n l 當(dāng)p x o x 0 x l x i 以 0 時(shí) 總有 尸 以 l x n t l x o 矗 x o x o 江蘇大學(xué)碩士學(xué)位論文 p 瓦 矗 i 以 矗 以 l x n 1 2 1 6 成立 則稱 j 0 h o l 2 為m 重馬氏鏈 若s 為可列集或有限集 則稱x 分別 依次為m 重可列馬氏鏈和m 重有限馬氏鏈 注意到 馬氏鏈的定義等價(jià)于 p 瓦 1 i x o i o x t 以 p 瓦 t i 以 所以馬氏鏈?zhǔn)且恢伛R氏鏈 下面引理指出 在擴(kuò)大狀態(tài)空間維數(shù)后 可化m 重馬氏鏈為 一重 馬氏鏈 考慮空間s 蘭 蘭 令m 維隨機(jī)向量乙 瓦 咒 以一 于是 梆 乙的取值空間為s 我們有 引理2 1 2 參見文獻(xiàn) 2 4 p s 2 設(shè) 是m 重馬氏鏈 則 乙 丹 0 l 2 是馬氏鏈 2 2 馬氏鏈遍歷性的基本理論 2 2 1 范數(shù)的定義與性質(zhì) 定義2 2 1 設(shè)廠 彳 a 石 為一行向量 定義 的范數(shù)洲如下 i f l l l 設(shè)g 島 9 2 9 3 是一列向量 定義g 的范數(shù)洲如下 l i g l l s u p l g l 2 2 1 2 2 2 設(shè)彳 是j z 月階實(shí)數(shù)矩陣 m 和 可以是無(wú)窮大 定義4 的范數(shù) 如下 i i a i i s u p x l o 2 2 3 易知這樣定義的范數(shù)洲滿足范數(shù)的三個(gè)公理 并且據(jù)有以下性質(zhì) 參見文獻(xiàn) 1 3 p 1 4 7 7 江蘇大學(xué)碩士學(xué)位論文 性質(zhì)2 2 1 對(duì)任何矩陣爿與b 有 肛圳 t 1 4 性質(zhì)2 2 2 對(duì)任何矩陣a 任何行向量廠及任何列向量g 有 i v a i i v i i 4 l i i 如0 1 1 4 i l g l l l i f g l l l l f l l i l g l l 性質(zhì)2 2 3 若p 是隨機(jī)矩陣 則有 1 2 2 2 馬氏鏈遍歷性的基本概念 在這一節(jié)中 我們將從范數(shù)意義上給出馬氏鏈各種遍歷性的定義 在給出各 種遍歷性定義之前 先給出一些預(yù)備知識(shí) 設(shè)q 是一隨機(jī)矩陣 若q 的各行均相同 則稱q 為常數(shù)隨機(jī)矩陣 設(shè) x 一 0 是定義在s 0 1 2 上的非齊次馬氏鏈 其轉(zhuǎn)移矩陣列為 只 以 i f f i 0 其中 記 n i i p 以 i j i 以 f f s n 2 0 p 4 巴 1 只 2 只 2 2 4 若馬氏鏈?zhǔn)驱R次的 則 只 療 0 簡(jiǎn)記為p p 細(xì)4 簡(jiǎn)記為p 下面我們給出馬氏鏈各種遍歷性的定義 定義2 2 2 稱馬氏鏈 只 咒 o 是弱遍歷的 如果對(duì)每個(gè)肌 存在一常數(shù)隨 機(jī)矩陣序列 既 肌 l 2 有 嬲護(hù) l 幺 9 o 2 2 5 定義2 2 3 稱馬氏鏈 只 即 o 關(guān)于常數(shù)隨機(jī)矩陣q 是強(qiáng)遍歷的 如果對(duì)任 何正整數(shù)朧有 l i m0 p m m m q 0 l u 2 2 6 江蘇大學(xué)碩士學(xué)位論文 定義2 2 4 稱馬氏鏈餌 療 0 關(guān)于常數(shù)隨機(jī)矩陣q 是絕對(duì)平均強(qiáng)遍歷的 如果對(duì)任何正整數(shù)所有 l i m 翱p m n k q 2 2 7 定義2 2 5 稱馬氏鏈織 刀 0 關(guān)于常數(shù)隨機(jī)矩陣q 是c e s a r o 平均收斂 的 又稱c 一強(qiáng)遍歷的 如果對(duì)任何正整數(shù)所有 l i m 噍i t p m m k e 卜 眨z 固 由上述定義可知 若一馬氏鏈 e 行 0 關(guān)于常數(shù)隨機(jī)矩陣q 是強(qiáng)遍歷的 則必定關(guān)于常數(shù)隨機(jī)矩陣q 是絕對(duì)平均強(qiáng)遍歷的 若一馬氏鏈僻 珂 0 關(guān)于常 數(shù)隨機(jī)矩陣9 是絕對(duì)平均強(qiáng)遍歷的 則必定關(guān)于常數(shù)隨機(jī)矩陣9 是c e s a r o 平均 收斂的 下面我們給出周期強(qiáng)遍歷性的定義 由文獻(xiàn) 1 5 知 一個(gè)不可約周期為d 的隨機(jī)矩陣p 可將狀態(tài)空間s 分解為d 個(gè)互不相交的狀態(tài)子集c o c l 一 巳一 并且p 派生出d 個(gè)隨機(jī)矩陣 7 0 正 乃 其中每個(gè)互定義在q 上 如果p 是有限的 則每個(gè)乃必是強(qiáng)遍歷的 但如果p 是可列無(wú)限的 則諸乃不一定是強(qiáng)遍歷的 若p 4 派生出的每個(gè)正都是 強(qiáng)遍歷的 則稱這樣的隨機(jī)矩陣p 是周期強(qiáng)遍歷的 2 3 遺傳算法的基本概念及模型描述 遺傳算法被認(rèn)為是對(duì)人類自然演化過(guò)程的模擬 人類的自然演化過(guò)程是進(jìn)化 過(guò)程 這種進(jìn)化過(guò)程發(fā)生在染色體上 自然選擇使適應(yīng)值好的染色體比那些適應(yīng) 值差的染色體有更多的繁殖機(jī)會(huì) 變異可以使子代染色體不同于父代染色體 通 過(guò)兩個(gè)父代染色體的結(jié)合與重組可以產(chǎn)生全新的染色體 染色體的選擇 變異與 重組進(jìn)程是無(wú)記憶的 將這些概念反映在數(shù)學(xué)上就形成了遺傳算法的基本概念 定義2 3 1 所謂 個(gè)體x 即是長(zhǎng)度為 的0 和l 字符串 簡(jiǎn)稱個(gè)體 f 稱 9 江蘇大學(xué)碩士學(xué)位論文 作個(gè)體的鏈長(zhǎng) 個(gè)體的全體記作s 0 1 稱為個(gè)體空間 按照遺傳學(xué)術(shù)語(yǔ) 個(gè)體也稱作染色體 個(gè)體的分量稱作基因的位置 分量的 可能取值稱作等位基因 定義2 3 2 所謂m 種群 是m 個(gè)個(gè)體組成的集合 個(gè)體允許重復(fù) 簡(jiǎn)稱 種群 m 稱作種群規(guī)模 稱 s z 置 爿j 爿 置 s 1 i 聊 為m 種群空間 定義2 3 3 所謂母體就是一對(duì)個(gè)體 對(duì)一對(duì)個(gè)體通過(guò)繁殖產(chǎn)生新個(gè)體 即 后代 用s 2 五 x x i x 2 研表示所有母體 稱作母體空間 遺傳算子解決種群到新種群的產(chǎn)生方法 它是遺傳算法對(duì)自然演化中種群更 替機(jī)制的類比與抽象 通過(guò)作用于當(dāng)前種群 產(chǎn)生新種群 以達(dá)到搜索全局最優(yōu) 解的目的 下面給出選擇 變異和雜交算子的定義 定義2 3 4 選擇算子即是在一個(gè)種群中選擇一個(gè)個(gè)體 它是隨機(jī)映射 t s 寸s 特別地 按照概率規(guī)則 p i t t z z 掣 廠 五 選擇個(gè)體的方式稱為適應(yīng)值選擇算子 其中廠 置 表示種群z 中的個(gè)體z 的適應(yīng) 值 0 口 0 時(shí)有 2 1 6 成立 則稱 瓦 盯 o 1 2 為m 重非齊次馬氏鏈 若s 1 2 n 或 s l 2 3 則稱 z 7 1 o 1 2 分別依次為m 重有限非齊次馬氏鏈和m 重可 列非齊次馬氏鏈 我們記 島 川 o 一1 p 以 i l 以 l i o 以 f m 1 3 1 1 1 2 江蘇大學(xué)碩士學(xué)位論文 只 p lf o 厶一 3 1 2 稱p l 島 一 為m 重非齊次馬氏鏈 瓦 胛 o 1 2 一 的m 階轉(zhuǎn)移概率 只為其 m 階轉(zhuǎn)移矩陣 p i 0 1 p x o i 以 l f 0 以 一i 3 1 3 為m 重非齊次馬氏鏈 x n n o 12 的m 階k 步轉(zhuǎn)移概率 由條件概率公式易 知 p i 乇 一 p p i f 0 一 p k 1 i 一 膳s 特別令 而稱 p o if 0 一i p p i 毛 一i k 一1 j 一1 3 1 4 為冥m 階k 步轉(zhuǎn)移矩陣 為了借助馬氏鏈的已有理論結(jié)果來(lái)探討m 重馬氏鏈的性質(zhì) 我們令m 維隨機(jī) 向量乙 j 乙 以 l 以一i 則由引理2 1 2 知 當(dāng) 厶 刀 0 l 2 為m 重馬 氏鏈時(shí) 乙 n o l 2 為m 維馬氏鏈 可以證明當(dāng) j 厶 胛 0 1 2 為m 重非齊 次馬氏鏈時(shí) 乙 療 o 1 2 必為m 維非齊次馬氏鏈 令i j m m j m 易知 此時(shí)記 e 礦 p z i z 3 1 5 槲一 卜1 齡 1 豢 艫耐 露 死 l 3 1 7 稱露為由m 階轉(zhuǎn)移矩陣只一 確定的i n 維轉(zhuǎn)移矩陣 進(jìn)而記 盛 江蘇大學(xué)碩士學(xué)位論文 蘆伸 f i m p z j jz i m 為 乙 z o 1 2 的k 步轉(zhuǎn)移概率 由條件概率公式易知 特別令 而稱 聲 fi p o r f 1 ir e s 萬(wàn) 0 1 i i i j i j 嚴(yán) 蘆 ii m 為 乙 廳 o 12 的k 步轉(zhuǎn)移矩陣 3 1 2m 重有限非齊次馬氏鏈的弱遍歷性 記f j 厶 1 l l m 4 3 1 8 3 1 9 定義3 1 2 參見文獻(xiàn) 6 p 1 0 4 如果對(duì)于任意月 0 及任意i j r s 覡 ii r a 一 礦 i o 3 1 1 0 則稱m 維有限非齊次馬氏鏈 z 珂 0 i 2 是弱遍歷的 也稱露為弱遍歷的 如果 定義3 1 3 設(shè) 以 珂 o 1 2 為一m 重有限非齊次馬氏鏈如3 1 1 定義 i m p j i 一護(hù) jl o 3 l 1 1 對(duì)任意押 m 1 及任意 s i m s 都成立 則稱 以 玎 o 1 2 是弱遍歷 的 也稱只是弱遍歷的 3 1 1 1 并不意味著當(dāng)七一m 時(shí) p i i m 和 p iz 有極限 但它 表示存在著一種趨向 即對(duì)任意n m i 當(dāng)t 寸0 0 時(shí) 矩陣 p 他 r i p i i m 中的每一行都趨于相等 下面給出m 重有限非齊次馬氏鏈具有上述弱遍歷性的一個(gè)充分條件 1 4 盛 江蘇大學(xué)碩士學(xué)位論文 定理3 1 1 設(shè)m 維轉(zhuǎn)移矩陣露是由m 階轉(zhuǎn)移矩陣只一 所確定的 如果乏是 弱遍歷的 則只也是弱遍歷的 證明如果瓦是弱遍歷的 由定義3 1 2 有 i m f i f 一 f i f o f z s 行 0 3 1 1 2 于是對(duì)任意以 0 l s f z s 有 憋h 一 p 厶 n m 1 1 l i n l p 以 li 瓦 蜀 之 一 0 一p 咒 厶l z 以 如 以一 2 憋差 p e t2 缸 咒 m k i 一 厶i 咒2 誓 m i 一 一p 以 z 制 厶f 以 咒一 2 1 受毒 p z 一可i z 一刮 p z 礦川z 一刮 2 憋善哳仆b 邛下一蘆沖b w 韌 0 從而對(duì)任意珂 m 及任意厶 s s m 有 憋 p 厶 一 p li 0 3 l 1 3 由定義3 1 3 知只是弱遍歷的 證畢 3 1 3i l l 重有限非齊次馬氏鏈的強(qiáng)遍歷 陛 在 3 1 2 中我們已經(jīng)給出了m 重有限非齊次馬氏鏈弱遍歷性的定義 并研究 了其滿足這種弱遍歷性的條件 下面我們對(duì)有限狀態(tài)下m 重非齊次馬氏鏈的強(qiáng)遍 歷性進(jìn)行討論 為此 我們先給出m 重有限非齊次馬氏鏈強(qiáng)遍歷性的定義 定義3 1 4 參見文獻(xiàn) 6 p 1 1 2 設(shè) z 行 0 1 2 為一m 維有限非齊次馬氏 鏈如 3 1 1 中定義 如果對(duì)任意 z 0 及任意 j s 存在不依賴于i s 的石 使得 江蘇大學(xué)碩士學(xué)位論文 j i m 歹似 1 i z j 一 則稱 z n 0 1 2 是強(qiáng)遍歷的 也稱乏為強(qiáng)遍歷的 3 1 1 4 定義3 1 5 設(shè) 以 n 0 1 2 為一m 重有限非齊次與氏鏈 如果對(duì)任恿 盯 塒一1 s i s 存在極限 l i m p u i 而且它不依賴于f m s 記為乃 即 j i m p i i 丌 3 1 1 5 則稱 j 厶 0 3 2 是強(qiáng)遍歷的 也稱只是強(qiáng)遍歷的 由定義知 由m 重有限非齊次馬氏鏈的強(qiáng)遍歷性可以導(dǎo)出其弱遍歷性 反 之則不然 現(xiàn)在我們給出m 重有限非齊次馬氏鏈滿足上述強(qiáng)遍歷性的定理及證明 定理3 1 2 設(shè)乏是由m 階轉(zhuǎn)移矩陣只一 所確定的m 維轉(zhuǎn)移矩陣 如果乏是 強(qiáng)遍歷的 則只也是強(qiáng)遍歷的 證明如果巨是強(qiáng)遍歷的 由定義3 1 4 知存在z j 使得 i m 療 i e s o 3 1 1 6 于是對(duì)任意n 0 厶 s i s 有 l i i i l l 礦 2 牌p 以一一 厶i 以2 杠 以一t2 一 善眠礦j l o x n k m i 2 j m x 啾拭一 釧 2 l i m 毒 p z 一叫叫z i m 2 l i r a 毒 n f 川 石 r 厶 從而對(duì)任意n m 1 厶 s i s 有 1 6 江蘇大學(xué)碩士學(xué)位論文 l i m p 厶 硝 厶 由定義3 1 5 知只是強(qiáng)遍歷的 證畢 設(shè) p p 厶i 厶 s i s 是一r l l 階轉(zhuǎn)移矩陣 定義一r n 維轉(zhuǎn)移矩陣如下 其中 乒 f i i s 4 3 1 1 7 3 1 1 8 3 1 1 9 酣門 n 鼢 未 肛1 限m 稱聲為由m 階轉(zhuǎn)移矩陣p 所確定的i l l 維轉(zhuǎn)移矩陣 那么我們有 定理3 i 3 設(shè)0 k z 0 i 2 j 為一m 重有限非齊次馬氏鏈 鼠 f 及 p i 分別如 3 1 1 和 3 1 3 定義 設(shè) p p c j 礦 3 1 2 1 為另一m 階轉(zhuǎn)移矩陣 假設(shè)p 所確定的i n 維轉(zhuǎn)移矩陣f 是遍歷的 如果對(duì)任意 j s i e s 有 艦p a i l 2 p 3 1 2 2 則 以 n 0 12 是強(qiáng)遍歷的t 即對(duì)任意 s i e s 櫛 優(yōu)一1 存在乃使得 i r a p ii 萬(wàn) nr 3 1 2 3 在證明定理3 1 3 之前 我們首先給出m 重非齊次馬氏鏈的切普曼一柯爾莫 哥洛夫方程 簡(jiǎn)稱c k 方程 及相關(guān)引理 引理3 1 1 c k 方程 設(shè) 以 月 0 1 2 為一m 重非齊次馬氏鏈 p l 如 3 1 3 定義 則對(duì)任意七 0 z 0 n 所一1 及任意 s i s 4 有 p k 0 ji i f f p uir 3 1 2 4 1 7 江蘇大學(xué)碩士學(xué)位論文 證明當(dāng)l m 1 k 1 時(shí)有 p c k o 礦 p 以 1 以 0 以 j p 瓦 以 瓦 r tj 瓦 以一 e s e x o 以 i r ti x 以 丈 e s 尸 瓦 j l k 咒 l 矽 p j l 一 一e s 3 1 2 5 當(dāng)1 o v i e s i e s 3 1 3 0 j 則乒是遍歷的 下面我們給出定理3 1 3 的證明 證明對(duì)任意 s s 及任意 m l 有 l p 2 l 一p 2 j l i l l e s 刪曠 川加以 叫2 b 叫 陲則1 卅琉m jls 咖 丟蹦引 汩u l f 兄 i e 陲則l 卅 p jllb巾一善烈 i 冶 jls l 2 以 j j f f e j s f 以u(píng)r m l i p 川 一p jl r 2 l z l p j l l 巴 l l p q l 一p 1 l i j l l 一p j l l i l 島 m 一p 1 l 1 3 1 3 1 f e 3 由 3 1 2 2 3 1 3 1 有 l i m p c 2 j lr p 2 j 曠 3 l 3 2 由歸納法可得 對(duì)任意正整數(shù)v 有 1 9 江蘇大學(xué)碩士學(xué)位論文 l i m p ir m p i n 3 1 3 3 由于p 是遍歷的 由引理3 1 2 對(duì)任惹 s r s 存在曩使得 i m p i 萬(wàn) 3 1 3 4 t 瑚 取i e 整數(shù)v o 使o v 0 k 對(duì)任意櫛 m 1 及 s i s 由引理3 1 1 有 p j l i 一乃i i f e s 一 h w 叱加下 l 0 存在k k 0 當(dāng)v o k 時(shí) 加下乃l 嘉 3 1 3 6 以k 代替 3 1 3 5 中的v o 對(duì)任意 m 1 七 k o 有 j l i 一乃l 0 及k 0 存在n n 0 使當(dāng)心 k k n 時(shí) 即 k n 7 k n 時(shí)有 k r p 傅b 曠 叫聊 巾 懌齋 3 1 3 8 因此 對(duì)任意 m 一1 及f 0 當(dāng)k m a x n k n 9 k 時(shí)有 i p u i 一乃懌f 3 1 3 9 江蘇大學(xué)碩士學(xué)位論文 由s 的任意性 故有對(duì)任意 s i s 及任意n m 一1 艦 p n u 一 3 1 4 0 即 3 1 2 3 成立 定理3 1 3 證畢 由定理3 1 3 我們有 推論3 1 1 設(shè) x n z o 1 2 為一m 重有限非齊次馬氏鏈 n j i m 如 3 1 1 定義 設(shè) p p j p j i f 0 w s i s 3 1 4 1 為另一m 階轉(zhuǎn)移矩陣 如果對(duì)任意 s i s 有 l i m p j l p j i i 3 1 4 2 則 j 門 o 1 2 是強(qiáng)遍歷的 證明由引理3 1 3 及定理3 1 3 可得本推論成立 3 2m 重可列非齊次馬氏鏈的遍歷性 在上節(jié)中 我們研究了有限狀態(tài)下m 重非齊次馬氏鏈的強(qiáng) 弱遍歷性 本節(jié) 的主要目的是對(duì)可列狀態(tài)下的m 重非齊次馬氏鏈的強(qiáng)遍歷性及其絕對(duì)平均強(qiáng)遍 歷性進(jìn)行討論 通過(guò)給出m 重可列非齊次馬氏鏈強(qiáng)遍歷性及其絕對(duì)平均強(qiáng)遍歷性 的定義 分別研究m 重可列非齊次馬氏鏈滿足這種強(qiáng)遍歷性和絕對(duì)平均強(qiáng)遍歷性 的充分條件 3 2 1m 重可列非齊次馬氏鏈的強(qiáng)遍歷性 為了研究可列狀態(tài)下m 重非齊次馬氏鏈的強(qiáng)遍歷性 需要先引入m 重可列非 齊次馬氏鏈強(qiáng)遍歷性的定義 定義3 2 1 設(shè) 以 胛 o 1 2 為一m 重可列非齊次馬氏鏈 如果對(duì)任意 s i s l m 1 存在不依賴于 s 的 r 滿足 i m s u p 一p j l i m 一乃l o 3 2 1 則稱 咒 n o 1 2 一 是強(qiáng)遍歷的 2 1 江蘇大學(xué)碩士學(xué)位論文 現(xiàn)在我們給出m 重可列非齊次馬氏鏈滿足上述強(qiáng)遍歷性的定理及證明 定理3 2 1 設(shè) 以 n 0 1 2 為一m 重可列非齊次馬氏鏈 見 i m 和 p f i m 分別如 3 1 1 和 3 1 3 定義 設(shè) p p j l 為另一m 階轉(zhuǎn)移矩陣 并且設(shè)p 所確定的m 維轉(zhuǎn)移矩陣f 是遍歷的 如果對(duì)任意 j s i s 伺 l i m u p x l p m 1 有 u p x 一p u 一p j l i m i 8 u p l 見 i i m 島 j l 訌 一 p l i p j l 噱 l o e3l e3 3l s u p l 以 i i m p n j l 幔 一 以p l i p j 1 l e3l ej ej s u p l 以 i i m p j l r n 一 p r l i m p j l b l e s ir e s e sl s u p z z i p l i m is u pl p n ir f 2 一p j r f 2 o l i jr e j7 山r s u ps u p i p j lr 協(xié) i 以 礦 p r l i m l 7 也一 k e j e s 翌 j l 喝 一p 巾 b 卜8 y e l p 0 存在k 世償 0 當(dāng) k 時(shí) 羅矽u j l 乃睜 以足代替 3 2 6 中的v 0 對(duì)任意行2 腳一1 有 3 2 7 8 u p 萎i p 件 u 礦 一乃i 萎l 一 r p 省 f 一p 懂 j l 主 由 3 2 4 對(duì)上述s o 及k k s 0 存在n o 使當(dāng)膽 七一足 時(shí) 即 k k n 一n 融奄 江蘇大學(xué)碩士學(xué)位論文 s u p 善k 以川 下p j l 一隧 因此 對(duì)任意占 0 及 2 肌一1 當(dāng)七 m a x k n 一療 k 時(shí)有 s u p p j l i 一乃卜占 l e j 由占的任意性 故有 3 2 3 成立 證畢 3 2 2m 重可列非齊次馬氏鏈的絕對(duì)平均強(qiáng)遍歷性 3 2 8 3 2 9 1 9 9 4 年 楊衛(wèi)國(guó)教授提出了非齊次馬氏鏈絕對(duì)平均強(qiáng)遍歷的概念 并利用 一強(qiáng)遍歷隨機(jī)矩陣p 得到了一階可列非齊次馬氏鏈絕對(duì)平均強(qiáng)遍歷的充分條件 1 8 本節(jié)我們將給出m 重可列非齊次馬氏鏈絕對(duì)平均強(qiáng)遍歷的概念 并給出i 1 1 重可列非齊次馬氏鏈滿足這種絕對(duì)平均強(qiáng)遍歷的一個(gè)充分條件 從而將非齊次馬 氏鏈的絕對(duì)平均強(qiáng)遍歷性從一階的情況推廣到了高階 定義3 2 2 設(shè) 以 廳 0 12 是一m 重可列非齊次馬氏鏈如3 1 1 定義 如果對(duì)任意 s i s 七 小一1 存在不依賴于i s 的萬(wàn) 使得 嬲i 1 薈ns u p z k p t 川下乃一 3 2 1 0 則稱 以 療 o 1 2 是絕對(duì)平均強(qiáng)遍歷的 定理3 2 2 設(shè) 瓦 療 o 12 為一m 重可列非齊次馬氏鏈 以 j i m 和 p i 分別如 3 1 1 和 3 1 3 定義 設(shè) p p i 尸 為另一m 階轉(zhuǎn)移矩陣 且設(shè)p 所確定的m 維轉(zhuǎn)移矩陣盧是遍歷的 如果對(duì)任意 j s i m s m 有 怒吉 耋 s u p 善伽曠 叫巾 o 3 2 1 1 則對(duì)任意正整數(shù)v 有 江蘇大學(xué)碩士學(xué)位論文 惡吉 妻 s u p z i p v 川下川巾 l o 3 2 1 2 并存在乃使對(duì)任意 s i s k m 一1 有 艦吉薔ns u p l j e s l t p 礦 一乃l 證明對(duì)任意 s i e s 有 3 2 1 3 寺 萎n 甲孫p 巾下以巾 i 寺 妻 s u p 萎陲仇 曠 以 l l j 2 一萎p 妒物 引r 南 l 去 耋 s u p 萎i 萎以 曠 見十l 一萎見 l f 卅 p h l 去 妻 s u p x b x 川 剛h b 一萎時(shí)礦m j 2 l 吉 耋 s u p z z l p 小 惡 加知以h 巾知?jiǎng)?吉 耋 s u p s u p z i 砌h 玨 i 萎船礦h i 圭 s u p j l 一p j l 嚏 l k z m 1 7 e s 丟 妻 s u p z p t 州下p 川n 3 2 1 4 由 3 2 1 1 和 3 2 1 4 知 艦吉 妻 s u p j e s 妒w 下p j l l 0 由歸納法可得 對(duì)任意正整數(shù)v 有 3 2 1 2 成立 由于f 是遍歷的 由引理3 1 2 對(duì)任意 e s i s 存在乃使得 憋p 忙 j l i 2 江蘇大學(xué)碩士學(xué)位論文 從而有 艦8 u p j e s 炒 巾 一乃印 3 2 1 5 取任一整數(shù)v o 1 對(duì)任意j s i s j m 一1 由引理3 1 1 有 去善ns u p 丟i k p m j l n 一乃 丟喜s u p r t e s l t 礦b 礦 一乃f i 1 未 s u p 善l t 少 u 曠 一乃 孚 溪s u p z 據(jù)z 擴(kuò)v o 川一 b 曠h 2 一v o i 未 甲薹l 薈 擴(kuò)吲曠曠地 卜 訓(xùn)一 叱 i 寺 未 s u p 薈麾 穢吲曠曠臚伽下乃 一 l 孚 i 1 熹 s u p 萎薈i 一 t f 叱 礦 l s u p l t w 龜p 叱 l 一p 叱 i l i i 未n s u p 萎薈b t 曠礦 吲烈巾下乃 2 療v o i 1 毫s u