On the approximation of optimal stochastic controls

The stochastic maximum principle gives a necessary condition for the optimal control problem for diffusions. If the controlled diffusion is approximated by a controlled Markov chain, and if approximating controls are chosen to maximize a Hamiltonian for the chain, then it is shown using weak convergence that the chains converge to a diffusion with a control satisfying the necessary condition of the maximum principle, and the corresponding costs also converge.     

Optimal p--cyclic SOR

Summary. Our purpose in this paper is to extend --cyclic SOR theory to consistent singular systems and to apply the results to the solution of large scale systems arising, {\em e.g.,} in queueing network problems in Markov analysis. Markov chains and queueing models lead to structured singular linear systems and are playing an increasing role in the understanding of complex phenomena arising in computer, communication and transportation systems. For certain important classes of singular problems, we develop a convergence theory for --cyclic SOR, and show how to repartition for optimal convergence. Results by Kontovasilis, Plemmons and Stewart on the concept of convergence of SOR in an {\em extended} sense are rigorously analyzed and applied to the solution of periodic Markov chains with period . Received October 20, 1992 / Revised version received September 14, 1993     

Convergence rates for reversible Markov chains without the assumption of nonnegative definite matrices

Explicit convergence rates in geometric and strong ergodicity for denumerable discrete time Markov chains with general reversible transition matrices are obtained in terms of the geometric moments or uniform moments of the hitting times to a fixed point. Another way by Lyapunov’s drift conditions is also used to derive these convergence rates. As a typical example, the discrete time birth-death process (random walk) is studied and the explicit criteria for geometric ergodicity are presented.     

Convergence of difference additive functionals under local conditions on their characteristics

For additive functionals defined on a sequence of Markov chains that approximate a Markov process, we establish the convergence of functionals under the condition of local convergence of their characteristics (mathematical expectations).     

Wasserstein convergence rates for random bit approximations of continuous Markov processes

We determine the convergence speed of a numerical scheme for approximating one-dimensional continuous strong Markov processes. The scheme is based on the construction of certain Markov chains whose laws can be embedded into the process with a sequence of stopping times. Under a mild condition on the process' speed measure we prove that the approximating Markov chains converge at fixed times at the rate of 1/4 with respect to every p-th Wasserstein distance. For the convergence of paths, we prove any rate strictly smaller than 1/4. Our results apply, in particular, to processes with irregular behavior such as solutions of SDEs with irregular coefficients and processes with sticky points.     

渐近循环马氏链的收敛速度

引入了渐近循环马氏链的概念,它是循环马氏链概念的推广.首先研究了在强遍历的条件下,可列循环马氏链的收敛速度,作为主要结论给出了当满足不同条件时可列渐近循环马氏链的C-强遍历性,一致C-强遍历性和一致C-强遍历的收敛速度     

On the convergence of 2-dimensional markov chains in quadrants with boundary reflection

The aim of this paper is to prove a limit theorem on the weak convergence of a family of rescaled Markov chains in a quadrant with boundary reflection. The limiting process is specified in terms of solutions of a certain submartingale problem in the style used by Varadhan and Williams. The obtained result is then applied to the problem of approximating an arbitrary Brownian motion with oblique reflection in a wedge by a family of Markov chains.     

Convergence of locally and globally interacting Markov chains

We study the long run behaviour of interactive Markov chains on infinite product spaces. In view of microstructure models of financial markets, the interaction has both a local and a global component. The convergence of such Markov chains is analyzed on the microscopic level and on the macroscopic level of empirical fields. We give sufficient conditions for convergence on the macroscopic level. Using a perturbation of the Dobrushin–Vasserstein contraction technique we show that macroscopic convergence implies weak convergence of the underlying Markov chain. This extends the basic convergence theorem of Vasserstein for locally interacting Markov chains to the case where an additional global component appears in the interaction.     

Blackwell Optimality in the Class of Markov Policies for Continuous-Time Controlled Markov Chains

This paper deals with Blackwell optimality for continuous-time controlled Markov chains with compact Borel action space, and possibly unbounded reward (or cost) rates and unbounded transition rates. We prove the existence of a deterministic stationary policy which is Blackwell optimal in the class of all admissible (nonstationary) Markov policies, thus extending previous results that analyzed Blackwell optimality in the class of stationary policies. We compare our assumptions to the corresponding ones for discrete-time Markov controlled processes.     

A Local Limit Theorem for a Family of Non-Reversible Markov Chains

By proving a local limit theorem for higher-order transitions, we determine the time required for necklace chains to be close to stationarity. Because necklace chains, built by arranging identical smaller Markov chains around a directed cycle, are not reversible, have little symmetry, do not have uniform stationary distributions, and can be nearly periodic, prior general bounds on rates of convergence of Markov chains either do not apply or give poor bounds. Necklace chains can serve as test cases for future techniques for bounding rates of convergence.     

A sequential data assimilation method based on the properties of a diffusion-type process

Data assimilation method, as commonly used in numerical ocean and atmospheric circulation models, produces an estimation of state variables in terms of stochastic processes. This estimation is based on limit properties of a diffusion-type process which follows from the convergence of a sequence of Markov chains with jumps. The conditions for this convergence are investigated. The optimisation problem and the optimal filtering problem associated with the search of the best possible approximation of the true state variable are posed and solved. The results of a simple numerical experiment are discussed. It is shown that the proposed data assimilation method works properly and can be used in practical applications, particularly in meteorology and oceanography.     

Exponential Convergence Rates of Markov Chains under a Weaken Minorization Condition

In this paper, we obtain the quantitative bound of the exponential convergence rates of Markov chains under a weaken minorization condition, using the coupling method and the analytic approach. And also, we obtain the convergence rates for continuous time Markov processes.     

Ergodic and adaptive control of hidden Markov models

A partially observed stochastic system is described by a discrete time pair of Markov processes. The observed state process has a transition probability that is controlled and depends on a hidden Markov process that also can be controlled. The hidden Markov process is completely observed in a closed set, which in particular can be the empty set and only observed through the other process in the complement of this closed set. An ergodic control problem is solved by a vanishing discount approach. In the case when the transition operators for the observed state process and the hidden Markov process depend on a parameter and the closed set, where the hidden Markov process is completely observed, is nonempty and recurrent an adaptive control is constructed based on this family of estimates that is almost optimal.     

The Cross-Entropy Method for Combinatorial and Continuous Optimization

We present a new and fast method, called the cross-entropy method, for finding the optimal solution of combinatorial and continuous nonconvex optimization problems with convex bounded domains. To find the optimal solution we solve a sequence of simple auxiliary smooth optimization problems based on Kullback-Leibler cross-entropy, importance sampling, Markov chain and Boltzmann distribution. We use importance sampling as an important ingredient for adaptive adjustment of the temperature in the Boltzmann distribution and use Kullback-Leibler cross-entropy to find the optimal solution. In fact, we use the mode of a unimodal importance sampling distribution, like the mode of beta distribution, as an estimate of the optimal solution for continuous optimization and Markov chains approach for combinatorial optimization. In the later case we show almost surely convergence of our algorithm to the optimal solution. Supporting numerical results for both continuous and combinatorial optimization problems are given as well. Our empirical studies suggest that the cross-entropy method has polynomial in the size of the problem running time complexity.     

随机有序马尔可夫链收敛速度显式界的注记

弱化Scott与Tweedie在计算马氏链收敛速度界时的条件,即变一步转移概率为m(m≥1)步转移概率,并运用不同于Scott与Tweedie的方法,计算出马氏链几何收敛速度r~n的界,从而推广了已有的结论.     

m重非齐次马氏链的Cesaro平均收敛性

引入m重非齐次马氏链的Cesaro平均收敛的概念,给出并证明m重非齐次马氏链的一个Cesaro平均收敛定理.作为应用,得到了m重非齐次马氏链熵率存在的一个定理.     

Two extensions of asymptotic methods in controlled Markov chains

The application of the Skorokhod representation of martingales and of the local asymptotic normality to derive limit inequalities for the cost in controlled finite state Markov chains is reviewed. The inequalities are usable in self-optimizing control. The methods are taken from the references listed but, with the exception of proposition 4, the results are formulated for Markov chains for the first time.     

A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces

Phylogenetic trees are commonly used to model the evolutionary relationships among a collection of biological species. Over the past fifteen years, the convergence properties for Markov chains defined on phylogenetic trees have been studied, yielding results about the time required for such chains to converge to their stationary distributions. In this work we derive an upper bound on the relaxation time of two Markov chains on rooted binary trees: one defined by nearest neighbor interchanges (NNI) and the other defined by subtree prune and regraft (SPR) moves.     

双根树上二阶非齐次马氏链的强大数定律和Shannon-McMillan定理

本文首先研究了双根树上转移矩阵为逐点转移的二阶非齐次马氏链的强极限定理,同时得到双根树上二阶非齐次马氏链的强大数定律.最后,给出了双根树上二阶非齐次马氏链几乎处处收敛意义下的Shannon-McMillan定理.     

Subgeometric ergodicity for continuous-time Markov chains

In this paper, subgeometric ergodicity is investigated for continuous-time Markov chains. Several equivalent conditions, based on the first hitting time or the drift function, are derived as the main theorem. In its corollaries, practical drift criteria are given for ?-ergodicity and computable bounds on subgeometric convergence rates are obtained for stochastically monotone Markov chains. These results are illustrated by examples.