Comparison of Three Web Search Algorithms

In this paper we discuss three important kinds of Markov chains used in Web search algorithms-the maximal irreducible Markov chain, the miuimal irreducible Markov chain and the middle irreducible Markov chain, We discuss the stationary distributions, the convergence rates and the Maclaurin series of the stationary distributions of the three kinds of Markov chains. Among other things, our results show that the maximal and minimal Markov chains have the same stationary distribution and that the stationary distribution of the middle Markov chain reflects the real Web structure more objectively. Our results also prove that the maximal and middle Markov chains have the same convergence rate and that the maximal Markov chain converges faster than the minimal Markov chain when the damping factor α 〉1/√2.     

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.     

Eigentime identity for transient Markov chains

An eigentime identity is proved for transient symmetrizable Markov chains. For general Markov chains, if the trace of Green matrix is finite, then the expectation of first leap time is uniformly bounded, both of which are proved to be equivalent for single birth processes. For birth-death processes, the explicit formulas are presented. As an application, we give the bounds of exponential convergence rates of (sub-) Markov semigroup Pt from l_∞ to l_∞.     

Absolute continuity of the invariant measure in piecewise deterministic Markov Processes having degenerate jumps

We consider piecewise deterministic Markov processes with degenerate transition kernels of the house-of-cards- type. We use a splitting scheme based on jump times to prove the absolute continuity, as well as some regularity, of the invariant measure of the process. Finally, we obtain finer results on the regularity of the one-dimensional marginals of the invariant measure, using integration by parts with respect to the jump times.     

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

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

Nash inequalities for finite Markov chains

This paper develops bounds on the rate of decay of powers of Markov kernels on finite state spaces. These are combined with eigenvalue estimates to give good bounds on the rate of convergence to stationarity for finite Markov chains whose underlying graph has moderate volume growth. Roughly, for such chains, order (diameter) steps are necessary and suffice to reach stationarity. We consider local Poincaré inequalities and use them to prove Nash inequalities. These are bounds onl ₂-norms in terms of Dirichlet forms andl ₁-norms which yield decay rates for iterates of the kernel. This method is adapted from arguments developed by a number of authors in the context of partial differential equations and, later, in the study of random walks on infinite graphs. The main results do not require reversibility.     

Bounds on regeneration times and convergence rates for Markov chains

In many applications of Markov chains, and especially in Markov chain Monte Carlo algorithms, the rate of convergence of the chain is of critical importance. Most techniques to establish such rates require bounds on the distribution of the random regeneration time T that can be constructed, via splitting techniques, at times of return to a “small set” C satisfying a minorisation condition P(x,·)(·), xC. Typically, however, it is much easier to get bounds on the time τ_C of return to the small set itself, usually based on a geometric drift function , where . We develop a new relationship between T and τ_C, and this gives a bound on the tail of T, based on ,λ and b, which is a strict improvement on existing results. When evaluating rates of convergence we see that our bound usually gives considerable numerical improvement on previous expressions.     

On an upwind difference scheme for strongly degenerate parabolic equations modelling the settling of suspensions in centrifuges and non-cylindrical vessels

We prove the convergence of an explicit monotone finite difference scheme approximating an initial-boundary value problem for a spatially one-dimensional quasilinear strongly degenerate parabolic equation, which is supplied with two zero-flux boundary conditions. This problem arises in a model of sedimentation–consolidation processes in centrifuges and vessels with varying cross-sectional area. We formulate the definition of entropy solution of the model in the sense of Kružkov and prove the convergence of the scheme to the unique BV entropy solution of the problem. The scheme and the model are illustrated by numerical examples.     

关于随机环境中的马尔可夫过程的简介——纪念李国平院士吴新谋教授诞辰100周年

该文系统地介绍随机环境中的马尔可夫过程. 共4章, 第一章介绍依时的随机环境中的马尔可夫链(MCTRE), 包括MCTRE的存在性及等价描述; 状态分类; 遍历理论及不变测度; p-θ 链的中心极限定理和不变原理. 第二章介绍依时的随机环境中的马尔可夫过程(MPTRE), 包括MPTRE的基本概念; 随机环境中的q -过程存在唯一性; 时齐的q -过程;MPTRE的构造及等价性定理.第三章介绍依时的随机环境中的分枝链(MBCRE), 包括有限维的和无穷维的MBCRE的模型和基本概念; 它们的灭绝概念;两极分化; 增殖率等.第四章介绍依时依空的随机环境中的马尔可夫链(MCSTRE), 包括MCSTRE的基本概念、构造; 依时依空的随机环境中的随机徘徊(RWSTRE)的中心极限定理、不变原理.     

Fuzzy Markov Chains and Decision-Making

Decision-making in an environment of uncertainty and imprecision for real-world problems is a complex task. In this paper it is introduced general finite state fuzzy Markov chains that have a finite convergence to a stationary (may be periodic) solution. The Cesaro average and the -potential for fuzzy Markov chains are defined, then it is shown that the relationship between them corresponds to the Blackwell formula in the classical theory of Markov decision processes. Furthermore, it is pointed out that recurrency does not necessarily imply ergodicity. However, if a fuzzy Markov chain is ergodic, then the rows of its ergodic projection equal the greatest eigen fuzzy set of the transition matrix. Then, the fuzzy Markov chain is shown to be a robust system with respect to small perturbations of the transition matrix, which is not the case for the classical probabilistic Markov chains. Fuzzy Markov decision processes are finally introduced and discussed.     

Hypergroup deformations and Markov chains

Persi Diaconis and Phil Hanlon in their interesting paper⁽⁴⁾ give the rates of convergence of some Metropolis Markov chains on the cubeZ ^d (2). Markov chains on finite groups that are actually random walks are easier to analyze because the machinery of harmonic analysis is available. Unfortunately, Metropolis Markov chains are, in general, not random walks on group structure. In attempting to understand Diaconis and Hanlon's work, the authors were led to the idea of a hypergroup deformation of a finite groupG, i.e., a continuous family of hypergroups whose underlying space isG and whose structure is naturally related to that ofG. Such a deformation is provided forZ ^d (2), and it is shown that the Metropolis Markov chains studied by Diaconis and Hanlon can be viewed as random walks on the deformation. A direct application of the Diaconis-Shahshahani Upper Bound Lemma, which applies to random walks on hypergroups, is used to obtain the rate of convergence of the Metropolis chains starting at any point. When the Markov chains start at 0, a result in Diaconis and Hanlon⁽⁴⁾ is obtained with exactly the same rate of convergence. These results are extended toZ ^d (3).Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.     

二重非齐次马氏链的遍历性及其应用

给出二重非齐次马氏链的强遍历性,绝对平均强遍历性,Cesaro平均收敛的概念．利用二维马氏链的遍历性和C-K方程,建立了二维马氏链与二重非齐次马氏链遍历性的关系．并讨论了齐次二重马氏链绝对平均强遍历与强遍历的等价性．最后给出Cesaro平均收敛在马氏决策过程和信息论中应用．     

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.     

STRONG LAW OF LARGE NUMBERS AND SHANNON-MCMILLAN THEOREM FOR MARKOV CHAINS FIELD ON CAYLEY TREE

1 lntroductionA tr(t(t is a grapl1 G = {T, E) wllicl1 is co1l11ected a11d colltai1ls no cir(.uits. Give11 a11y twov(irtic'is 't / P E T, let crP bc tl1e ullique patl1 col111ecti11g,v aIld /]. Defille tl1e graph distal1cc(l(rr, p) to hc the Ilu1llber of edges co11tained in the path crP.We discuss ulainly tl1e rooted Cayley tree TC,2(i.e.,binary tree. See Fig.1). In tlle Cayleytree Tc,2,tl1e root (denoted by 0) llas OIlly two 11(tiglll)(irs al1d all otller vertices have threeneighbors. A…     

关于可列非齐次马氏链的若干极限定理

设{Xn,n≥0}是一列非齐次马尔科夫链,{an,n≥0}是一列固定的非负整数序列.首先构造了一个带参数的广义似然比函数,然后利用Borel-Cantelli引理证明随机变量序列几乎处处收敛性,得到了关于可列非齐次马氏链序偶广义平均的若干极限定理,推广了已有的结果.     

Markov chain mixing time on cycles

Mixing time quantifies the convergence speed of a Markov chain to the stationary distribution. It is an important quantity related to the performance of MCMC sampling. It is known that the mixing time of a reversible chain can be significantly improved by lifting, resulting in an irreversible chain, while changing the topology of the chain. We supplement this result by showing that if the connectivity graph of a Markov chain is a cycle, then there is an Ω(n²) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle.     

On the class of Markov chains with finite convergence time

We study the necessary and sufficient conditions for a finite ergodic Markov chain to converge in a finite number of transitions to its stationary distribution. Using this result, we describe the class of Markov chains which attain the stationary distribution in a finite number of steps, independent of the initial distribution. We then exhibit a queueing model that has a Markov chain embedded at the points of regeneration that falls within this class. Finally, we examine the class of continuous time Markov processes whose embedded Markov chain possesses the property of rapid convergence, and find that, in the case where the distribution of sojourn times is independent of the state, we can compute the distribution of the system at time t in the form of a simple closed expression.     

Convergence of Markov Chains in Information Divergence

Information theoretic methods are used to prove convergence in information divergence of reversible Markov chains. Also some ergodic theorems for information divergence are proved.      

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.

     

Stationary Analysis of a Fluid Queue Driven by Some Countable State Space Markov Chain

Motivated by queueing systems playing a key role in the performance evaluation of telecommunication networks, we analyze in this paper the stationary behavior of a fluid queue, when the instantaneous input rate is driven by a continuous-time Markov chain with finite or infinite state space. In the case of an infinite state space and for particular classes of Markov chains with a countable state space, such as quasi birth and death processes or Markov chains of the G/M/1 type, we develop an algorithm to compute the stationary probability distribution function of the buffer level in the fluid queue. This algorithm relies on simple recurrence relations satisfied by key characteristics of an auxiliary queueing system with normalized input rates.