m阶马氏链关于广义随机选择系统的极限定理

主要研究广义随机选择系统中的m阶非齐次马氏链随机转移概率调和平均的a.s.收敛的强极限定理.在证明中采用了一种把网微分法与条件矩母函数相结合应用于马氏链强极限定理研究的新途径.作为推论,得到m阶非齐次马氏链随机条件概率一个公平比的强极限定理,并将已有的结果加以推广.     

两种万维网搜索算法的比较

Google 创始人sergey Brin 和Lawrence Page 把万维网搜索算法PageRank 定义成某个非周期不可约马氏链的唯一平稳分布.本文讨论了万维网搜索算法中使用的两个重要的马氏链-maximal 不可约马氏链和minimal 不可约马氏链-收敛到平稳分布的收敛速度.结果表明,在阻尼因子α>1/2~(1/2)时,maximal 马氏链比minimal 马氏链的收敛速度快.本文也给出了minimal 马氏链k 步转移矩阵的表达式,及其平稳分布关于参数α的各阶导数和Maclaurin 级数展开.     

M阶非齐次马氏链随机转移概率调和平均的一类强极限定理

主要研究任意m阶非齐次马氏链的随机转移概率调和平均的a.s.收敛的强极限定理.在证明中采用了一种把网微分法与条件矩母函数相结合应用于马氏链强极限定理研究的新途径.作为推论,得到m阶非齐次马氏链的一个公平比的强极限定理,并将已有的结果加以推广.     

马氏链集间转移的一类强大数定律

本文研究了马氏链从一个状态子集到另一个状态子集的转移概率的极限性质.利用Doob鞅收敛定理,获得了任意随机序列的强大数定律、马氏链泛函的强大数定律和强遍历定理.推广了马氏链传统转移概率的极限性质和强极限定理.     

带马氏切换的马氏过程的指数收敛速度

设 (X(t), Z(t))是以[0,∞) ×{1, 2,…, n₀} 为状态空间的强马氏过程, 其第一分量 X(t) 依赖于第二分量 Z(t), 而第二分量 Z(t) 是一个马氏链. 应用耦合方法, 估计了(X(t), Z(t)) 的转移概率依全变差范数收敛于其不变概率测度的指数收敛速度.     

离散时间马氏链的L~2几何收敛

对于离散时间马氏链,转移概率矩阵P关于平稳分布可逆的条件下,给出过程L2几何收敛速率与谱隙之间的关系,并得到最优L2几何收敛速率与最优几何遍历速率的一致性.     

树上二重非齐次马氏链随机转移概率的极限性质

研究树上二重非齐次马氏链随机转移概率的调和平均极限性质,作为推论,得到了树上非齐次马氏链以及非齐次马氏链上的随机转移概率调和平均极限性质.     

基于马氏链拟合的一种非负变权组合预测算法及其应用

通过马氏链拟合的方法求取一种新的非负时变权组合预测算法公式.主要工作是:一、对组合预测问题以最小误差为准则给出了马氏链的状态和状态概率初步估计;二、用马氏链拟合状态概率分布时变规律,通过约束多元自回归模型导出了一步转移概率阵的LS解;三、给出一种非负时变权组合预测公式并举一应用实例.     

树上非齐次马氏链随机转移概率的极限性质

收稿研究树上非齐次马氏链随机转移概率的调和平均极限性质,所得结果将非齐次马氏链上随机转移概率调和平均性质推广到树图上.     

马氏环境中树指标马氏链随机转移概率调和平均的强极限性质

本文研究了离散状态下随机环境中树指标马氏链,证明了该过程在概率空间中可以实现,同时阐明了马氏环境下树指标马氏链与树指标马氏双链的等价性.获得了有限状态下马氏环境中树指标马氏链的随机转移概率调和平均的强极限性质.     

Sensitive equilibria for ergodic stochastic games with countable state spaces

We consider stochastic games with countable state spaces and unbounded immediate payoff functions. Our assumptions on the transition structure of the game are based on a recent work by Meyn and Tweedie [19] on computable bounds for geometric convergence rates of Markov chains. The main results in this paper concern the existence of sensitive optimal strategies in some classes of zero-sum stochastic games. By sensitive optimality we mean overtaking or 1-optimality. We also provide a new Nash equilibrium theorem for a class of ergodic nonzero-sum stochastic games with denumerable state spaces.     

Exponential bounds for discrete-time singularly perturbed Markov chains

This paper develops exponential type upper bounds for scaled occupation measures of singularly perturbed Markov chains in discrete time. By considering two-time scale in the Markov chains, asymptotic analysis is carried out. The cases of the fast changing transition probability matrix is irreducible and that are divisible into l ergodic classes are examined first; the upper bounds of a sequence of scaled occupation measures are derived. Then extensions to Markov chains involving transient states and/or nonhomogeneous transition probabilities are dealt with. The results enable us to further our understanding of the underlying Markov chains and related dynamic systems, which is essential for solving many control and optimization problems.     

A Note on Foster–Lyapunov Drift Condition for Recurrence of Markov Chains on General State Spaces

In this paper, we prove that the Foster–Lyapunov drift condition is necessary and sufficient for recurrence of a Markov chain on a general state space. And then an answer in the affirmative for the question presented in the monograph of Meyn and Tweedie (Markov chains and stochastic stability. Springer, Berlin, 1993, P175) is obtained.     

Perturbed Markov Chains with Damping Component

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter ε. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems for n-step transition probabilities, as well as ergodic theorems in triangular array mode.

     

Markov approximations of chains of infinite order

We consider chains whose transition probabilities depend on the whole past, with summable continuity rates. We show that Ornstein's -distance between one such chain and its canonical Markov approximations of different orders is at worst proportional to the continuity rate of the chain. The result generalizes previous bounds obtained by X. Bressaud and ourselves, while relying on a similar coupling argument. Received: 9 April 2002     

Geometric Ergodicity of Gibbs and Block Gibbs Samplers for a Hierarchical Random Effects Model

We consider fixed scan Gibbs and block Gibbs samplers for a Bayesian hierarchical random effects model with proper conjugate priors. A drift condition given in Meyn and Tweedie (1993, Chapter 15) is used to show that these Markov chains are geometrically ergodic. Showing that a Gibbs sampler is geometrically ergodic is the first step toward establishing central limit theorems, which can be used to approximate the error associated with Monte Carlo estimates of posterior quantities of interest. Thus, our results will be of practical interest to researchers using these Gibbs samplers for Bayesian data analysis.     

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.     

CONVERGENCE RATES FOR A CLASS OF EVOLUTIONARY ALGORITHMS WITH ELITIST STRATEGY

1 IntroductionOne of tlle fundamental issues about the theory of evolutionary algorithIns is their conver-gence. At present, the theoretical basis about evolutionary computation is still yery wcak['--'],especial1y for the researches into the convergeIlce rates of evolutionary a1gorithm8. Accord-illg to the literature, tllere are few results about the convergence rates[4--9], but this research..area i8 very importallt in both theory and practice. Xu and Li[l0] pointed out that the studyof the…     

A Markov Chain analysis of genetic algorithms with power of 2 cardinality alphabets

In this paper we model the run time behavior of GAs using higher cardinality representations as Markov chains, define the states of the Markov Chain and derive the transition probabilities of the corresponding transition matrix. We analyze the behavior of this chain and obtain bounds on its convergence rate and bounds on the runtime complexity of the GA. We further investigate the effects of using binary versus higher cardinality representation of a search space.     

Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise

The ergodic properties of SDEs, and various time discretizations for SDEs, are studied. The ergodicity of SDEs is established by using techniques from the theory of Markov chains on general state spaces, such as that expounded by Meyn–Tweedie. Application of these Markov chain results leads to straightforward proofs of geometric ergodicity for a variety of SDEs, including problems with degenerate noise and for problems with locally Lipschitz vector fields. Applications where this theory can be usefully applied include damped-driven Hamiltonian problems (the Langevin equation), the Lorenz equation with degenerate noise and gradient systems.The same Markov chain theory is then used to study time-discrete approximations of these SDEs. The two primary ingredients for ergodicity are a minorization condition and a Lyapunov condition. It is shown that the minorization condition is robust under approximation. For globally Lipschitz vector fields this is also true of the Lyapunov condition. However in the locally Lipschitz case the Lyapunov condition fails for explicit methods such as Euler–Maruyama; for pathwise approximations it is, in general, only inherited by specially constructed implicit discretizations. Examples of such discretization based on backward Euler methods are given, and approximation of the Langevin equation studied in some detail.