英语原文共 68 页，剩余内容已隐藏，支付完成后下载完整资料
第四章
马尔科夫链
4.1 引言与例子
考虑只取有限个或可数个可能值的随机过程{}。若不另外说明，过程可能取得值的集合将以非负整数集{0,1,2,...}来表示。若，就说过程在n时刻处于状态i，我们假设每当过程处于状态i，则在下一时刻将处
于状态j的概率是固定的。也即假设对一切状态以及所有的有（4.1.1）
这样的随机过程称为马尔科夫链。方程(4.1.1)可解释为，对马尔科夫链，给定过去的状态以及现在的状态，将来的状态的条件分布与过去的状态独立，只依赖于现在的状态，这称为马尔科夫性。的值代表处于状态i的过程下一步转移到状态j的概率。由于概率是非负的，且过程必须转移到某个状态，所以有
以P记一步转移概率的矩阵，从而
命题4.1.1
若是一个简单的随机游动，则
4.2 切尔曼——柯尔莫哥洛夫方程及状态分类
我们已经定义了一步转移概率。现在我们定义n步转移概率为处于状态i过程的经n次转移后处于状态j的概率。即
当然有。切普曼—柯尔莫哥洛夫方程提供了计算n步转移概率的方法。这些方程是：对一切n,mge;0，一切i,j,有
(4.2.1)
可如下建立他们
若以记n步转移概率的矩阵，则由(4.2.1)断言
其中的点代表矩阵乘法。因此，
于是可以由矩阵P自乘n次而算出。
若对某个nge;0有gt;0，则称从状态i可到达状态j。两个相互可到达的状态i和j称为相通的，记作。
命题4.2.1
相通是一种等价关系，即：
(i)
(ii)若，则
(iii)若及，则
命题4.2.2 若，则d(i)=d(j)。
命题4.2.3
状态j为常返的当且仅当。
结论4.2.4
若i是常返的，且,则j是常返的。
结论4.2.5
若，且j是常返的，则。
4.3 极限定理
容易证明，若状态j是滑过的，则对一切i
这意味着从i出发进入状态j的平均次数是有限的，作为一个推论，对滑过状态j，时，。
以记返回状态j所需的平均转移步数，即
将进入状态j解释为更新，从第三章的命题3.3.1，3.3.4及3.4.1，我们得到下述定理。
定理 4.3.1
若i与j相通，则
(i)
(ii)
(iii)若j是非周期的，则
(iv) 若j有周期d，则
若状态j是常返的，则时我们称它是正常返的，而时称为零常返的。若我们令
则一个常返状态j，当时为正常返，当时为零常返。
命题4.3.2
正（零）常返性是一个类性质。
一个正常返的非周期状态称为遍力的。在给出一个如何在遍历情形得到极限概率的定理之前，我们需要以下定义。
定义 对于马尔可夫链，一个概率分布称为平稳的，若
若的概率分布（譬如）是平稳分布，则
且由归纳法得
因此，若初始概率分布是平稳分布，那对一切有相同的分布。事实上因是马尔可夫链，由此易得知对每个mge;O , 对每个n具有相同的分布；换言之是一个平稳过程。
定理4.3.3 一个不可约非周期马尔可夫链属于下列两种情况之一：
(i)状态或全是滑过的或全是零常返的；此时对一切时，且不存在平稳分布。
(ii)状态全是正常常返的，即
此时，是平稳分布，且不存在任何其它的平稳分布。
4.4 类之间的转移与赌徒输光问题
在本节中我们证明常返类是闭的，即一旦进入就永不离开。
命题4.4.1
设R是一个常返的状态类。若，则。
命题4.4.2
若j是常返的，则概率组满足
其中R记与j相通的状态的集合。
4.5 分支过程
考虑一个由能产生同类后代的个体组成的群体。每一个体生命结束时以概率 ，产生了j个新的后代，与别的个体产生的后代个数相互独立。初始的个体数以表示，称为第零代的总数，第零代的后代构成第一代，其总数记作。一般地 ，以记第 n 代的总数。此马尔可夫链称为分支过程 。
假设，注意到
其中表示第 n-1代的第i个个体的后代个数，我们可以计算的均值。对取条件得
其中mu;是每个个体的后代个数的均值。
以记从单个个体开始群体迟早灭绝的概率。
对初始个体的后代个数取条件，可以导出一个确定的方程，如下:
给定，群体最终灭绝当且仅当第一代的成员为始祖的j个家族最终灭绝。由于各家族假定是独立活动的，而任一家族灭绝的概率都是，所以得到
（4.5.1）
事实上可证明下列
定理4.5.1 设及，则
(i)是满足的最小正数。
(ii)的充要条件是。
4.6 马尔科夫链的应用
4.6.1 算法有效性的马尔科夫链模型
在运筹学与计算机科学中，某些算法以如下的方式进行：目标是要决定N个有序元素中的最优者，算法以其中一个元素开始，而后逐次移动到更好的元素，直到到达最优者为止。（最重要的例子可能是线性规划的单纯形算法，该算法试图要求一个受线性约束条件的线性函数的最大值，此时一个元素对应于可行区域 的一个端点。）如果从“最差的情况”的角度考察算法的效率，那么一般都能构造出大致需N-1步才到达最佳元素的例子。本节中我们将对必需的步数给出一个简单的概率模型。特别地，我们考虑一个马尔可夫链，它从任何状态等可能地进入到任一更好的状态。
考虑一个马尔科夫链，其，而
以记以状态i转移到状态1的步数，对初始转移取条件可得的一个递推公式：
（4.6.1）
从开始，逐一看到
不难猜想，且可用归纳法证明
然而，为了更完全地描述，我们利用表达式
其中
上述表达式的重要性来自下列
引理4.6.1
是独立的，且
命题4.6.2
(i)
(ii)
(iii)对充分大的N,渐进泊松分布，均值为logN。
4.6.2 应用于游程——一个连续状态空间的马尔科夫链
考虑一列数。如果我们在之前立一竖线，每当就在与之间立一竖线，那么两条竖线之间的段落称为游程。例如，部分序列3,5,8,2,4,3,1包括四个游程，如下所示
|3,5,8|2,4|3|1
这样，每个游程是序列的一个上升的段落。
现假设，是独立同分布的（0，1）上均匀分布的随机变量，我们感兴趣的是逐个游程的长度的分布，例如以记初始的游程的长度，那么至少是m当且仅当前m-l个值是依次上升的，可见
其后的游程的分布也容易得到，如果我们知道这一游程的初始值x。因为若一游程起始于x，则
（4.6.2）
因为要游程长至少是m，其后的m-1个值都必须大于x且必须依次增大。
为了得到一个给定的游程长度的无条件分布，以记第n个游程的初始值。容易看到是一具有连续状态空间的马尔可夫链，为了计算p(y|x），在一个游程从初始值x开始的条件下，下一游程起始于y的概率密度，作如下的推导：
其中是第n个游程之长。此潜程长为m，且下一游程起始于y，如果
(i)其后的m-1个值是依次增加且全部大于x；
(ii)第m个值必须等于y；
(iii)前m-1个值的最大者必超过y。
因此
对m求和得
所以，是一马尔可夫链，具有连续状态空间（0,1）且转移概率密度由上式给定。
为了得到的极限分布，我们先冒险作一个猜测，而后利用类似于定理4.3.3的结果来验证我们的猜测。是第一个游程的初始值，在（0,1）上均匀分布。然而，只要有一个值小于其前一值，后一游程便开始。因而看来有理由认为，小于y的这样的值所占的比例长时间之后要等于一个（0,1）上均匀分布的随机变量在小于第二个相互独立的（0,1）上均匀分布变量的条件下，小于y的概率。由于
所以，的极限密度等于
似乎是合理的。［此极限密度的第二种直接的推导如下：每一个取值y的，将是一个新游程的起点，如果它的前一个值大于y，因此初始值在（y,y dy）中的游程发生的速率看来等于，所以初始值在（y,y dy）中的游程所占比例将是。。]因为可对连续状态空间的马尔可夫链证明一个类似于定理4.3.3的定理，所以为了证明上面的猜测，我的需验证：
这时就归结为证明
或
只要利用下列恒等式很容易证得此式：
这样，我们已证明第n个游程的初始值的极限密度是。因此第n个游程的长度的极限分布为
（4.6.3）
为了计算一个游程的平均长度，注意到由（4.6.2）有
从而
上述极限也可以从(4.6.3)算的如下：
它导致有趣的恒等式
4.6.3 名词排序规则——移前一位规则的最优性
假设给定n个元素，将它们按某种顺序排列，每次要求取出其中一个元素，然后放回并将n个元素重新排序，每次取出（与过去独立）的概率为。感兴趣的问题是要确定一种最优排序规则以便使长时间后被取出的元素的平均位置最小。显然若己知，则最优的排序规则就是每次都按照的递减次序去安排诸元素。事实上，即使诸未知，我们也能渐近地做到，即每次依照各元素己被取出的次数的递减次序去排列它们。然而，问题会变得更有趣，如果我们不允许有上述排序规则所必要的存储记忆的功能，却对重新排序的规则作如下的限制：每次元素的重新排序只允许依赖于现在的排列次序及这次取出的元素的位置 。
对于一个给定的重新排序规则，被取出的元素的平均位置至少在理论上可以通过分析有n!个状态的马尔可夫链得到，这个马尔可夫链在任一时刻的状态就是元素这时的排列次序。然而，对这么多的状态，分析很快变成不可行的，所以我们把问题简化，假定概率满足：
这时，因为从第二列第n个元素，在被取出的概率相等的意义下是无区别的，被取出的元素的平均位置可以通过分析简单得多的、只有n个状态的马尔可夫链得到，这马尔可夫链的状态就是的位置。在对概率作这样的假设之下，在一大类规则之中，把取出的元素移到前面一个位置上去的“移前一位规则”是最优的。
考虑如下限定的一类规则，当取出的元素是在位置i上时，把此元素移到位置上去，而其它的元素的相对位置保持不动。此外假设，对及有。集合就刻划了一个规则。
对于给定的一个此类规则，令
换句话说，对任意的i，任何位置i,i 1,...,i K(i)上的一个元素如果被取出，将被移到小于或等于i的位置上。
对于一个特定的上述类型的规则R（譬如说对于它K(i）=k(i),i=1,2,...,n)，在使用此规则时的平稳分布记为：
此外，令
记号意味着上述概率是极限概率。在写下稳态方程之前，值注意以下事实：
(i)任何元素每次至多朝后移动一个位置。
(ii)如果一个元素处于位置i，再且既不是它也不是它后面的k(i)个位置上的元素被取出，则它将仍然在位置i上。
(iii)任何处于诸位置i,i 1,...,i k(i)上的元素若被取出，它将被移到le;i的位置上。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[409441]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
