Markov随机模型的算法研究

综述了国际上关于Markov过程及相关随机模型算法的研究现状 ,包括平稳解、瞬态解、首达时间、多维可数状态Markov过程的算法研究等 ,并讨论了进一步工作的展望 .     

二维可数状态Markov过程的瞬态解

不少文献研究了有限状态Markov过程(以下简记为MP)或可数状态特殊MP的瞬态解,如Grassmann,Gross和Miller,Kohlas,Reibman和Trivedi,Tijms和Zhang和Coyle。最近,一般可数状态MP的瞬态解已为Hsu和Yuan所解决,他们给出了具有一致误差的算法。但在二维状态空间时,通常只能处理一维(称为水平)为可数状态。而另一维(称之为位相)为有限状态的情形,即使对研究平稳解的某些重要方法而言也是如此,例如Neuts及其他所有处理矩阵几何解的文献。然而在实际应用中,往往要遇到二维可数状态的情形,例如具有无限容量缓冲器的两级排队(见文献[9],但其中只处理了具有有限容量缓冲器的两级排队)和双输入匹配服务系统(见徐光煇等,但其中只处理了一个输入具有有限缓冲器的情形)等。因此考虑二维可数状态瞬态解的算法就很有必要。有了二维可数的结果,相应地就可处理更多维的但其中只有两维为可数的情形,也容易自然推广到三维或更多维可数状态MP的瞬态解的算法。这样,很多随机模型的瞬态解问题就能得到圆满的解决。     

可数状态马氏过程的瞬态解及其算法

有限状态马氏过程瞬态解(在时刻t,过程处于各状态的概率)的求解算法已有不少工作,如Grassmann,Gross和Miller,Reibman和Trivedi等.可数状态马氏过程的瞬态解算法却只有几种特殊的情形被讨论过,如Grassmann在初始时刻系统中无顾客的条件下,讨论了系统M|M|1的瞬时性态的求解算法;Zhang和Coyle在初始时刻过程处于1水平时,得到了拟生灭过程的瞬态解算法.本文则在任意初始条件下,研究一般可数状态马氏过     

QNQL过程:(H,Q)-过程及其应用举例

1(H,Q)-过程随机过程研究者众,应用面广,例如Markov过程.Markov过程中以最小Markov链(即最小齐次可列Markov过程)发展得最成熟.这类过程的一大特点就是任一状态的逗留时间服从负指数分布.显然这个限制太严格.在本世纪50年代,Levy等人放弃了这个限制,但保留过程在其一列跳跃点上构成一个Markov链的性质,而引入了半Markov过程的概念并加以研究,得到这种过程的概率分布所满足的(向后)方程.例如,顾客到达时间间隔为独立同分布随机变量的排队系统的输入过程N(t)(N(t)表示在(0,t)时间内到达顾客的数目)就是半Markov过程的典型例子.到了80年代,Davis把对半Markov过程在相邻两个跳跃点之间只取一个常值(即只逗留于一个状态)的假设放宽为一段确定的光滑曲线,而在跳跃点上保持了Markov性,并借助于一个附加变量,引入了逐段确定的Markov过程的概念并加以研究,得到这类过程的广无穷小母元.GI/G/1排队系统的等待时间W(t)就是这类过程的典型例子.但仍有许多应用上十分有意义的随机过程不在考虑之列.这些过程是:具有一列有Markov性的跳跃点(不排除还有其他跳跃点),而在这种两个相邻跳跃点之间过程的轨道不一定是一段确定的光滑曲线,而是一段随机过程,这段随机过程的轨道也许是连续的,也许还有跳跃点,如:M/G/1,GI/M/1     

关于两参数Markov过程的强芽Markov性

本文把文献[1]所定义的关于单参数Markov过程强芽Markov性的概念移植到两参数Markov过程(即文献[2]中的~*-Markov过程)中,并得到了~*-Markov过程关于停线的两种强芽Markov性.同时,也证明了~*-Markov过程具有文献[3]意义下的强Markov性,且更具普遍性。此外,在文献[4]的基础上,证明了两参数Markov过程关于平面上任何开集具有芽Markov性,从而得到了文献[2]所希望的结果。     

图的二分问题唯一全局最优解实例与骨架计算复杂性

骨架分析是近年来理论计算机科学研究的热点, 对于NP-难解问题的启发式算法设计具有重要意义. 由于骨架计算复杂性研究十分困难, 现有的骨架分析方法多采用实验统计手段. 针对现有方法中存在的骨架规模小的缺陷, 给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法, 有效提高了骨架的规模. 同时, 利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题, 即在P≠NP的假设下, 不存在多项式时间的算法可以确保得到GBP问题的完整骨架. 本文的工作拓广了骨架计算复杂性研究的范围, 所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.     

二维可数状态Markov过程的首达时间

随机模型的研究中经常涉及Markov过程(以下简记为MP)首达时间的计算问题,例如在随机服务系统与网络中的等待时间、逗留时间与忙期等重要指标都是相应Markov过程的首达时间.迄今为止,不少文献讨论过某些特殊MP或Markov更新过程的这类问题,例如文献[1～5].但是对一般MP而言,只有个别论文研究过首达时间,如文献[6,7],而且在可数状态时其误差不仅难以控制,同时对时间 t也非一致.最近,Hsu和Yuan研究了在任意初始条件下一般可数MP的首达时间,并导出了具有一致误差的算法,使该问题得到了圆满的解决.然而,众所周知,上述所有结果都仅对至多一维为可数状态的多维MP成立,这远远不能满足实际应用的需要,因为在现实生活的各种随机模型中经常会遇到多维可数MP的问题,如多结点随机服务网络、多输入匹配服务系统等等.因此研究二维或多维可数MP的首达时间问题自然就显示了其重要的理论意义与应用价值.     

Hamilton系统双曲周期解的存在唯一性

人们已对Hamilton系统进行了广泛而深入的研究.主要成果集中在刻划周期解的存在性,见文献[1]及引文.近年来,Rabinowitz,Hofer等数学家进一步研究了Hamilton系统的同宿轨和异宿轨的存在性.就纯量Hamilton系统,即Duffing方程而言,人们还研究了Birkhoff型周期解的存在性和解的有界性及浑沌现象等动力行为.但是对一般Hamilton系统周期解的性态知道甚少,原因之一是目前研究Hamilton系统行之有效的方法:如临界点理论,拓扑度理论难以刻划解的性态.本文引进分量Lyapunov函数,结合临界点理论研究了如下Hamilton系统(?)-Ax (?)G(x)=p(t),(1)其中A是n阶正定实对称矩阵,G∈C~2(R~n,R~n),p(t)是连续的2π-周期向量函数,(?)G表示G的梯度.我们得到了     

向量值半Markov决策规划

关于向量值Markov决策规划,文献[1]研究了有限阶段与无限阶段模型之间的关系。文献[2,3]将标量模型的策略迭代算法推广到向量模型,给出了求最优策略的算法。其算法大致叙述如下:从任一平稳策略出发,在平稳策略类中不断进行策略迭代改进,求得不动点及其周围的可疑点,然后从可疑点开始迭代改进。上述过程反复进行,直到考察完所有平稳策略为止。最后在求出的不动点集合Γ中用穷举法求出全部最优策略。     

特征值问题的非线性化与孤子方程的数值解

1.为数众多的孤立子的发现是近年非线性科学的一大进展.描述孤子演化行为的偏微分方程有两大特点,一是它们的重要物理背景和实际应用前景,二是它们的完全可积性.已找到不少有趣的显式解.其中最重要的是纯孤子解、有限带解和极点展开解.现在的问题是,一些显式解的表达式太复杂,给计算实践带来甚大的困难,有必要寻求更为直接和简捷的算法.由于上述各种显式解中所含的参数个数有限,自然可以期望通过消去这些参数得到常微     

广义系统的概周期解

研究了广义系统的概周期解问题,得到了广义系统的概周期解存在的判据,同时,给出了应用的实例。     

Born-Oppenheimer近似下的平面氢分子离子Schr?dinger方程的精确解

目前,研究分子少体系统的经典-量子对应已经成为非线性物理中一个极为重要的课题,我们首先要了解系统的量子力学解.在分子系统中,氢分子离子是最简单的,3维氢分子离子的量子力学精确解早已求出.我们将研究更简单的情况:2维氢分子离子的量子力学精确解,这样的解对于低维物理的研究也非常有用.     

Pareto有效解与α-较多有效解类

如所周知,多目标规划的Pareto有效(最优)解或即非劣解,是多目标数学规划研究中的一个基本的概念。在这种解的意义下,自50年代以来,人们对于多目标规划的有关理论、方法以及它们的应用已进行了大量的研究。然而,由于Pareto有效解仅仅是关于问题的向量目标为非劣意义下的解,因此,对于一个给定的多目标规划问题,一般地说其Pareto有效解集都会相当地大,并且当目标数愈大时则更甚。这是采用正锥确定偏序来定义Pareto有     

二十世纪的10大算法

伟大的算法是计算的诗篇。对２０世纪的科学发展和工程实践产生巨大影响的１０大算法是： １．１９４６年计算蒙特卡洛过程的伦敦算法。对那些过于复杂给不出精确解的问题，该算法可使蒙特卡洛过程有效地给出问题的解。 ２．１９４７年线性规划的单纯形算法。这一优美算法解决了规划和决策过程中的共同问题。 ３．１９５０年 Ｋｒｙｌｏｖ的子空间迭代算法。该算法可快速地给出科学计算中大量存在的线性方程组的解。 ４．１９５１年矩阵计算的分解算法。这一整套技术解决了线性代数中的数值分析问题。 ５．１９５７年Ｆｏｒｔｒａｎ语言的优…     

二阶中立型微分方程解的振动性

一、引言 过去20多年以来,对于时滞微分方程解的振动性与非振动性已有许多研究成果。中立型时滞微分方程解的振动性研究始于1980年,目前已有一些作者从事这一课题的研究。 在本文中,我们研究二阶线性具有变系数的中立型方程     

一类对可列非齐次Markov链普遍成立的强大数定律

虽然关于可列非齐次Markov链的强大数定律已有不少研究。但以往的工作都对Markov链作了某些假定,本文旨在给出对任意非齐次Markov链普遍成立的一类强大数定律。作为主要结果的推论,我们在a.e.收敛的意义下,给出了任意非齐次Markov链状态序偶出现频率和转移概率的一种关系。     

Poisson方程Robin外问题的积分解

关于近年来才开始的非线性大地边值问题的研究,虽然在解的适定性方面已有若干成果,但都无法用于实际。为了建立起便于实用的解理论,我们提出了一种新的解法。在这种方法中,Poisson方程的Robin外问题起关键作用,非线性边值问题被转化为线性边值问题序列的递推求解。本文研究与最具典型意义的非线性Molodensky问题相应的Poisson方程Robin外问题的积分解,即求扰动位T的积分表示,使满足     

关于Lévy Markov性的几点注记

关于两指标过程各马氏性之间关系的问题,已有一些讨论,发现其中有些等价有些不等价。比如文献[1]举出了一个反例,说明了*-Markov性与宽过去Markov性是不等价的,从而推翻了以前关于它们等价的结论。关于*-Markov性与Lévy Markov性的一个结论是:设X是*-Markov过程,则它关于任意开集DR_+~2,有宽Lévy Markov性。我们要问:如     

八顶角反射方程的解及其杨-巴斯特化

Cherednik研究半线(Half-line)上的因子散射时首次引入了反射方程以描述端点上的反射行为.最近发现它们在量子流代数和具有非周期边界条件的可积模型中也起重要作用.Kulish等曾讨论了无谱参数的反射方程的性质、代数结构和常数解.但怎样由这种常数解得到具有谱参数的反射方程的解,即所谓的反射方程的杨-巴斯特化,仍没有解决.本文将讨论八顶角模型的反射方程的解(代数解和常数解)及其杨-巴斯特化.其杨-巴斯特化方法可推广到任意有两个不同本征值的(?)的情况.     

蛋白三态去折叠自由能计算新方法

基于三态模型中的传统假设,三态解折叠蛋白的解折叠过程可以看作是一个连续而独立的两个两态过程.本文提出一种新的三态解折叠蛋白去折叠自由能计算新方法,且将该方法用于计算三态解折叠蛋白Y79W-W83F-Cu的去折叠自由能.数据分析表明,用该方法求得的蛋白去折叠自由能较用先前报道的方法更精确.