Search

The purpose of this paper is to provide a complete description of the eigenvalues of the generator of a neutral multi-type Moran model, and the applications to the study of the speed of convergence to stationarity. The Moran model we consider is a non-reversible in general, continuoustime Markov chain with an unknown stationary distribution. Specifically, we consider N individuals such that each one of them is of one type among K possible allelic types. The individuals interact in two ways: by an independent irreducible mutation process and by a reproduction process, where a pair of individuals is randomly chosen, one of them dies and the other reproduces. Our main result provides explicit expressions for the eigenvalues of the infinitesimal generator matrix of the Moran process, in terms of the eigenvalues of the jump rate matrix. As consequences of this result, we study the convergence in total variation of the process to stationarity and show a lower bound for the mixing time of the Moran process. Furthermore, we study in detail the spectral decomposition of the neutral multi-allelic Moran model with parent independent mutation scheme, which is the unique mutation scheme that makes the neutral Moran process reversible. Under the parent independent mutation, we also prove the existence of a cutoff phenomenon in the chi-square and the total variation distances when initially all the individuals are of the same type and the number of individuals tends to infinity. Additionally, in the absence of reproduction, we prove that the total variation distance to stationarity of the parent independent mutation process when initially all the individuals are of the same type has a Gaussian profile. [ABSTRACT FROM AUTHOR]

The Fredrickson-Andersen one spin facilitated model belongs to the class of Kinetically Constrained Spin Models. It is a non attractive process with positive spectral gap. In this paper we give a precise result on the relaxation for this process on an interval [1, L] starting from any initial configuration. A consequence of this result is that this process exhibits cutoff at time L/(2v) with window O(√L) for a certain positive constant v. The key ingredient is the study of the evolution of the leftmost empty site in a filled infinite half-line called the front. In the process of the proof, we improve recent results about the front motion by showing that it evolves at speed v according to a uniform central limit theorem. [ABSTRACT FROM AUTHOR]

We consider a random walk on the hyperoctahedral group Bn generated by the signed permutations of the forms (i,n) and (-i,n) for 1≤i≤n. We call this the flip-transpose top with random shuffle on Bn. We find the spectrum of the transition probability matrix for this shuffle. We prove that the mixing time for this shuffle is of order nlogn. We also show that this shuffle exhibits the cutoff phenomenon. In the appendix, we show that a similar random walk on the demihyperoctahedral group Dn also has a cutoff at (n-1/2)logn. [ABSTRACT FROM AUTHOR]

Consider a sequence of continuous-time irreducible reversible Markov chains and a sequence of initial distributions, μn. Instead of performing a worst case analysis, one can study the rate of convergence to the stationary distribution starting from these initial distributions. The sequence is said to exhibit (total variation) μn-cutoff if the convergence to stationarity in total variation distance is abrupt, w.r.t. this sequence of initial distributions. In this work we give a characterization of μn-cutoff (and also of total-variation mixing) for an arbitrary sequence of initial distributions μn (in the above setup). Our characterization is expressed in terms of hitting times of sets which are “worst" (in some sense) w.r.t. μn. Consider a Markov chain on whose stationary distribution is л. Let tH(α) := maxxϵΩ,A⊆ : л(A) > α 피x[TA] be the expected hitting time of the set of stationary probability at least α which is “worst in expectation" (starting from the worst starting state). The connection between tH(·) and the mixing time of the chain was previously studied by Aldous and later by Lovász and Winkler, and was recently refined by Peres and Sousi and independently by Oliveira. In this work we further refine this connection and show that μn-cutoff can be characterized in terms of con- centration of hitting times (starting from μn) of sets which are worst in expectation w.r.t. μn. Conversely, we construct a counter-example which demonstrates that in general cutoff (as opposed to cutoff w.r.t. a certain sequence of initial distributions) cannot be characterized in this manner. Finally, we also prove that there exists an absolute constant C such that for any Markov chain ϵ(tH(ϵ) - tH(1 - ϵ)) 6 Ctrel∣ log ϵ∣, for all 0 < ϵ < 1/2, where trel is the inverse of the spectral gap of the additive symmetrization 1/ 2 (P + P*). [ABSTRACT FROM AUTHOR]

The location and width of the time window in which a sequence of processes converges to equilibrum are given under conditions of exponential convergence. The location depends on the side: the left-window and right-window cutoffs may have different locations. Bounds on the distance to equilibrium are given for both sides. Examples prove that the bounds are tight. [ABSTRACT FROM AUTHOR]