A stabilization law for two semi-infinite interacting strings of characters

We consider a Markov chain that describes the evolution of two interacting strings of symbols. The transitions probalitities of this Markov chain depend only on the rightmost symbols of both strings. The main goal of the present paper is to prove a limit theorem (stabilization law): the distribution of the rightmost symbols converges to some limit correlation function.1 Partially supported by FAPESP (2002/01501-9) and RFBR (02-01-00415)2 Partially supported by RFBR (02-01-00415)     

Phylogenetic Inference for Binary Data on Dendograms Using Markov Chain Monte Carlo

Abstract

Using a stochastic model for the evolution of discrete characters among a group of organisms, we derive a Markov chain that simulates a Bayesian posterior distribution on the space of dendograms. A transformation of the tree into a canonical cophenetic matrix form, with distinct entries along its superdiagonal, suggests a simple proposal distribution for selecting candidate trees “close” to the current tree in the chain. We apply the consequent Metropolis algorithm to published restriction site data on nine species of plants. The Markov chain mixes well from random starting trees, generating reproducible estimates and confidence sets for the path of evolution.     

Continuous-time limit of repeated interactions for a system in a confining potential

We study the continuous-time limit of a class of Markov chains coming from the evolution of classical open systems undergoing repeated interactions. This repeated interaction model has been initially developed for dissipative quantum systems in Attal and Pautrat (2006) and was recently set up for the first time in Deschamps (2012) for classical dynamics. It was particularly shown in the latter that this scheme furnishes a new kind of Markovian evolutions based on Hamilton’s equations of motion. The system is also proved to evolve in the continuous-time limit with a stochastic differential equation. We here extend the convergence of the evolution of the system to more general dynamics, that is, to more general Hamiltonians and probability measures in the definition of the model. We also present a natural way to directly renormalize the initial Hamiltonian in order to obtain the relevant process in a study of the continuous-time limit. Then, even if Hamilton’s equations have no explicit solution in general, we obtain some bounds on the dynamics allowing us to prove the convergence in law of the Markov chain on the system to the solution of a stochastic differential equation, via the infinitesimal generators.     

Uniqueness of quantum Markov chains associated with an XY-model on a cayley tree of order 2

We propose the construction of a quantum Markov chain that corresponds to a “forward” quantum Markov chain. In the given construction, the quantum Markov chain is defined as the limit of finite-dimensional states depending on the boundary conditions. A similar construction is widely used in the definition of Gibbs states in classical statistical mechanics. Using this construction, we study the quantum Markov chain associated with an XY-model on a Cayley tree. For this model, within the framework of the given construction, we prove the uniqueness of the quantum Markov chain, i.e., we show that the state is independent of the boundary conditions.     

广义Bethe树指标可列马氏链场关于广义随机选择系统的一类局部极限定理

研究任意广义Bethe树指标马尔可夫链场二元泛函关于广义随机选择系统的一类局部极限定理.作为推论得到了广义随机选择系统中任意Cayley树上状态频率和状态序偶的一类极限定理.证明中采用了一种研究马尔可夫链场的较新颖的分析方法.     

The Central Limit Theorem for Markov Chains with General State Space

We consider a Markov chain with general state space and an embedded Markov chain sampled at the times of successive returns to a subsetA₀ of the state space.We assume that the latter chain is uniformly ergodic but the originalMarkov chain need not possess this property.We develop amodification of the spectralmethod and utilize it in proving the central limit theorem for theMarkov chain under consideration.     

Stationary analysis of the shortest queue problem

In this paper, we derive an approximation for throughput of TCP Compound connections under random losses. Throughput expressions for TCP Compound under a deterministic loss model exist in the literature. These are obtained assuming that the window sizes are continuous, i.e., a fluid behavior is assumed. We validate this model theoretically. We show that under the deterministic loss model, the TCP window evolution for TCP Compound is asymptotically periodic and is independent of the initial window size. We then consider the case when packets are lost randomly and independently of each other. We discuss Markov chain models to analyze performance of TCP in this scenario. We use insights from the deterministic loss model to get an appropriate scaling for the window size process and show that these scaled processes, indexed by p, the packet error rate, converge to a limit Markov chain process as p goes to 0. We show the existence and uniqueness of the stationary distribution for this limit process. Using the stationary distribution for the limit process, we obtain approximations for throughput, under random losses, for TCP Compound when packet error rates are small. We compare our results with ns2 simulations which show a good match and a better approximation than the fluid model at low p.     

Quasi-Stationarity of Discrete-Time Markov Chains with Drift to Infinity

We consider a discrete-time Markov chain on the non-negative integers with drift to infinity and study the limiting behavior of the state probabilities conditioned on not having left state 0 for the last time. Using a transformation, we obtain a dual Markov chain with an absorbing state such that absorption occurs with probability 1. We prove that the state probabilities of the original chain conditioned on not having left state 0 for the last time are equal to the state probabilities of its dual conditioned on non-absorption. This allows us to establish the simultaneous existence, and then equivalence, of their limiting conditional distributions. Although a limiting conditional distribution for the dual chain is always a quasi-stationary distribution in the usual sense, a similar statement is not possible for the original chain.     

马氏环境中可数马氏链的Poisson极限率

研究了马氏环境中的可数马氏链,主要证明了过程于小柱集上的回返次数是渐近地服从Poisson分布。为此,引入熵函数h,首先给出了马氏环境中马氏链的Shannon-Mc Millan-Breiman定理,还给出了一个非马氏过程Posson逼近的例子。当环境过程退化为一常数序列时,便得到可数马氏链的Poisson极限定理。这是有限马氏链Pitskel相应结果的拓广。     

The statistics of words on rings

We analyze sequences of letters on a ring. Our objective is to determine the statistics of the occurrences of a set of r‐letter words when the sequence is chosen as a periodic Markov chain of order ≤ r ? 1. We first obtain a generating function for the associated probability distribution and then display its Poisson limit. For an i.i.d. letter sequence, correction terms to the Poisson limit are given. Finally, we indicate how a hidden Markov chain fits into this scheme. © 2005 Wiley Periodicals, Inc.     

Mean Buffer Contents in Discrete-Time Single-Server Queues with Heterogeneous Sources

We consider discrete-time single-server queues fed by independent, heterogeneous sources with geometrically distributed idle periods. While being active, each source generates some cells depending on the state of the underlying Markov chain. We first derive a general and explicit formula for the mean buffer contents in steady state when the underlying Markov chain of each source has finite states. Next we show the applicability of the general formula to queues fed by independent sources with infinite-state underlying Markov chains and discrete phase-type active periods. We then provide explicit formulas for the mean buffer contents in queues with Markovian autoregressive sources and greedy sources. Further we study two limiting cases in general settings, one is that the lengths of active periods of each source are governed by an infinite-state absorbing Markov chain, and the other is the model obtained by the limit such that the number of sources goes to infinity under an appropriate normalizing condition. As you will see, the latter limit leads to a queue with (generalized) M/G/∞ input sources. We provide sufficient conditions under which the general formula is applicable to these limiting cases.AMS subject classification: 60K25, 60K37, 60J10This revised version was published online in June 2005 with corrected coverdate     

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

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

A Poisson limit theorem for a strongly ergodic non-homogeneous Markov chain

A strongly ergodic non-homogeneous Markov chain is considered in the paper. As an analog of the Poisson limit theorem for a homogeneous Markov chain recurring to small cylindrical sets, a Poisson limit theorem is given for the non-homogeneous Markov chain. Meanwhile, some interesting results about approximation independence and probabilities of small cylindrical sets are given.     

A Conditional CLT which Fails for Ergodic Components

We show that the conditional central limit theorem can take place for a stationary process defined on a nonergodic dynamical system while this last does not satisfy the central limit theorem for any ergodic component. There exists an ergodic Markov chain such that the conditional central limit theorem is satisfied for an invariant measure but fails to hold for almost all starting points.      

Two-sided taboo limits for Markov processes and associated perfect simulation

In this paper, we study the two-sided taboo limit processes that arise when a Markov chain or process is conditioned on staying in some set A for a long period of time. The taboo limit is time-homogeneous after time 0 and time-inhomogeneous before time 0. The time-reversed limit has this same qualitative structure. The precise transition structure at the taboo limit is identified in the context of discrete- and continuous-time Markov chains, as well as diffusions. In addition, we present a perfect simulation algorithm for generating exact samples from the quasi-stationary distribution of a finite-state Markov chain.     

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

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

Switching diffusion logistic models involving singularly perturbed Markov chains: Weak convergence and stochastic permanence

Focusing on stochastic dynamics involve continuous states as well as discrete events, this article investigates stochastic logistic model with regime switching modulated by a singular Markov chain involving a small parameter. This Markov chain undergoes weak and strong interactions, where the small parameter is used to reflect rapid rate of regime switching among each state class. Two-time-scale formulation is used to reduce the complexity. We obtain weak convergence of the underlying system so that the limit has much simpler structure. Then we utilize the structure of limit system as a bridge, to invest stochastic permanence of original system driving by a singular Markov chain with a large number of states. Sufficient conditions for stochastic permanence are obtained. A couple of examples and numerical simulations are given to illustrate our results.     

Almost Sure Central Limit Theorem for Partial Sums of Markov Chain

The authors prove an almost sure central limit theorem for partial sums based on an irreducible and positive recurrent Markov chain using logarithmic means,which realizes the extension of the almost sure central limit theorem for partial sums from an i.i.d.sequence of random variables to a Markov chain.     

Fluctuations of interacting Markov chain Monte Carlo methods

We present a multivariate central limit theorem for a general class of interacting Markov chain Monte Carlo algorithms used to solve nonlinear measure-valued equations. These algorithms generate stochastic processes which belong to the class of nonlinear Markov chains interacting with their empirical occupation measures. We develop an original theoretical analysis based on resolvent operators and semigroup techniques to analyze the fluctuations of their occupation measures around their limiting values.     

The Limit Behaviour of Imprecise Continuous-Time Markov Chains

We study the limit behaviour of a nonlinear differential equation whose solution is a superadditive generalisation of a stochastic matrix, prove convergence, and provide necessary and sufficient conditions for ergodicity. In the linear case, the solution of our differential equation is equal to the matrix exponential of an intensity matrix and can then be interpreted as the transition operator of a homogeneous continuous-time Markov chain. Similarly, in the generalised nonlinear case that we consider, the solution can be interpreted as the lower transition operator of a specific set of non-homogeneous continuous-time Markov chains, called an imprecise continuous-time Markov chain. In this context, our convergence result shows that for a fixed initial state, an imprecise continuous-time Markov chain always converges to a limiting distribution, and our ergodicity result provides a necessary and sufficient condition for this limiting distribution to be independent of the initial state.