随机排列最优成组剖分的算法

本文研究随机排列的最优成组剖分问题。这一问题源于铁路列车的最优调度计划方法的设计问题。寻找切实可行的有效算法是问题的焦点。1978年这一问题被列入文献的公开问题之一。1986年许国志、陈庆华和刘继勇提出猜测:此乃NP-完全问题,即多项式时间的算法可能不会存在,除非NP=P。 本文引入一种强同构剪枝策略,以标号树形上的隐式枚举法为工具,得到了上述问题精确最优解的一个算法。其计算时间复杂度为O(n³2^n-2),其中n为随机排列中相异数字的个数。算法在给定n的条件下,     

交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式

研究集生产、运输和销售为一体的多个制造商在随机市场环境下的两阶段随机非合作博弈问题.首先,建立了该两阶段随机非合作博弈问题的模型,然后将其转化为两阶段随机变分不等式(Stochastic Variational Inequality,简称SVI).在温和的假设条件下,证明了该问题存在均衡解,并通过Progressive Hedging Method(简称PHM)进行求解.最后,通过改变模型中随机变量的分布和成本参数,分析与研究厂商的市场行为.     

具有线性乘积白噪声的随机非自治吊桥方程的随机指数吸引子

本文考虑具有线性乘积白噪声的随机非自治吊桥方程长时间行为.首先,建立了所研究共圈系统的适定性;第二步,研究了该系统随机吸引子的存在性;第三步,当随机系数趋于0时,得到了随机吸引子的上半连续性;第四步,通过``迭代''法证明了随机吸引子在高正则空间中的正则性;最后,给出了该系统随机指数吸引子的存在性,同时得到了吸引子的有限分形维数.     

随机微分方程高阶分裂步(θ1,θ2,θ3)方法的强收敛性

本文首先提出一类高阶分裂步（θ₁,θ₂,θ₃）方法求解由非交换噪声驱动的非自治随机微分方程.其次在漂移项系数满足多项式增长和单边Lipschitz条件下,证明了当1/2 ≤ θ₂ ≤ 1时该方法是1阶强收敛的.此类方法包含很多经典的方法：如随机θ-Milstein方法,向后分裂步Milstein方法等.最后数值实验验证了所得结论.     

中立型随机延迟微分方程分裂步θ方法的强收敛性

中立型随机延迟微分方程常出现在一些科学技术和工程领域中.本文在漂移系数和扩散系数关于非延迟项满足全局Lipschitz条件,关于延迟项满足多项式增长条件以及中立项满足多项式增长条件下,证明了分裂步θ方法对于中立型随机延迟微分方程的强收敛阶为1/2.数值实验也验证了这一理论结果.     

关于一类随机非线性算子方程的若干问题的研究（英文）

本文推广了两个重要的不等式,并且利用随机不动点指数理论研究了一类随机非线性算子方程的随机解的存在性问题,主要结果推广了著名的Altman定理.最后给出主要结果在随机非线性积分方程中的一个应用.     

一个一般的多值随机算子的随机不动点定理

近年来,由于理论和应用上的需要,随机不动点定理的研究获得了很大进展.许多重要的不动点定理的随机类比已相继得到证明。本文的定理2.1是一个一般的随机不动点定理,它推广了重要的 Chuong 的结果.利用这个定理,结合非随机不动点定理立即可以得到许多非随机不动点定理的随机类比.例如,[1,2,4,6]中的结果都是本定理的特例。     

因子von Neumann代数中套子代数上Jordan同构的刻画

本文研究了套子代数上由零积确定的子集中保Jordan积的线性映射与同构和反同构的关系.证明了若对任意的A,B∈algMβ且AB=0,有Φ(A■B)=Φ(A)■Φ(B)成立,则Φ是同构或反同构.其中,algMβ,algMγ是因子von Neumann代数M中的两个非平凡套子代数,Φ:algMβ→algMγ是一个保单位线性双射.     

带有乘积白噪音的非自治随机波方程的随机吸引子

研究了带有乘积白噪音的非自治随机波方程.首先证明解在一个有界球外的一致小性,然后对解在有界的区域内进行分解,得到解的渐近紧性,最后得到了带有乘积白噪音的非自治随机波方程的随机吸引子的存在性.     

平均场倒向重随机微分方程及其应用

研究了平均场倒向随重机微分方程, 得到了平均场倒向重随机微分方程解的存在唯一性.基于平均场倒向重随机微分方程的解, 给出了一类非局部随机偏微分方程解的概率解释.讨论了平均场倒向重随机系统的最优控制问题, 建立了庞特利亚金型的最大值原理.最后讨论了一个平均场倒向重随机线性二次最优控制问题, 展示了上述最大值原理的应用.     

Tubular recurrence

We introduce the directed-edge-reinforced random walk and prove that the process is equivalent to a random walk in random environment. Using Oseledec"s multiplicative ergodic theorem, we obtain recurrence and transience criteria for random walks in random environment on graphs with a certain linear structure and apply them to directed-edge-reinforced random walks. This revised version was published online in August 2006 with corrections to the Cover Date.     

Random Walks on Trees with Finitely Many Cone Types

This paper is devoted to the study of random walks on infinite trees with finitely many cone types (also called periodic trees). We consider nearest neighbour random walks with probabilities adapted to the cone structure of the tree, which include in particular the well studied classes of simple and homesick random walks. We give a simple criterion for transience or recurrence of the random walk and prove that the spectral radius is equal to 1 if and only if the random walk is recurrent. Furthermore, we study the asymptotic behaviour of return probabilitites and prove a local limit theorem. In the transient case, we also prove a law of large numbers and compute the rate of escape of the random walk to infinity, as well as prove a central limit theorem. Finally, we describe the structure of the boundary process and explain its connection with the random walk.     

Level crossing probabilities II: Polygonal recurrence of multidimensional random walks

In part I we proved for an arbitrary one-dimensional random walk with independent increments that the probability of crossing a level at a given time n is O(n−1/2). In higher dimensions we call a random walk ‘polygonally recurrent’ if there is a bounded set, hit by infinitely many of the straight lines between two consecutive sites a.s. The above estimate implies that three-dimensional random walks with independent components are polygonally transient. Similarly a directionally reinforced random walk on Z³ in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252] is transient. On the other hand, we construct an example of a transient but polygonally recurrent random walk with independent components on Z².     

Asymptotic direction for random walks in random environments

In this paper we study the existence of an asymptotic direction for random walks in random i.i.d. environments (RWRE). We prove that if the set of directions where the walk is transient contains a non-empty open set, the walk admits an asymptotic direction. The main tool to obtain this result is the construction of a renewal structure with cones. We also prove that RWRE admits at most two opposite asymptotic directions.     

直线上独立时间随机环境中随机游动的渐近行为

主要讨论直线上独立时间随机环境中随机游动的常返性和非常返性,以及该过程的中心极限定理.     

The heavy range of randomly biased walks on trees

We focus on recurrent random walks in random environment (RWRE) on Galton–Watson trees. The range of these walks, that is the number of sites visited at some fixed time, has been studied in three different papers Andreoletti and Chen (2018), Aïdékon and de Raphélis (2017) and de Raphélis (2016). Here we study the heavy range: the number of edges frequently visited by the walk. The asymptotic behavior of this process when the number of visits is a power of the number of steps of the walk is given for all recurrent cases. It turns out that this heavy range plays a crucial role in the rate of convergence of an estimator of the environment from a single trajectory of the RWRE.     

On the Local Times of Transient Random Walks

We study the properties of the local and occupation times of certain transient random walks. First, our recent results concerning simple symmetric random walk in higher dimension are surveyed, then we start to establish similar results for simple asymmetric random walk on the line.     

Asymptotics of the Moment Generating Function for the Range of Random Walks

The range of random walks means the number of distinct sites visited at least once by the random walk before time n. We are interested in the free energy function of the range of simple symmetric random walks and determine the asymptotic behavior near the origin.     

Random Walks in Weyl Chambers and the Decomposition of Tensor Powers

We consider a class of random walks on a lattice, introduced by Gessel and Zeilberger, for which the reflection principle can be used to count the number of k-step walks between two points which stay within a chamber of a Weyl group. We prove three independent results about such reflectable walks: first, a classification of all such walks; second, many determinant formulas for walk numbers and their generating functions; third, an equality between the walk numbers and the multiplicities of irreducibles in the kth tensor power of certain Lie group representations associated to the walk types. Our results apply to the defining representations of the classical groups, as well as some spin representations of the orthogonal groups.     

Semigroups, Rings, and Markov Chains

We analyze random walks on a class of semigroups called left-regular bands. These walks include the hyperplane chamber walks of Bidigare, Hanlon, and Rockmore. Using methods of ring theory, we show that the transition matrices are diagonalizable and we calculate the eigenvalues and multiplicities. The methods lead to explicit formulas for the projections onto the eigenspaces. As examples of these semigroup walks, we construct a random walk on the maximal chains of any distributive lattice, as well as two random walks associated with any matroid. The examples include a q-analogue of the Tsetlin library. The multiplicities of the eigenvalues in the matroid walks are generalized derangement numbers, which may be of independent interest.