Explicit criteria on separation cutoff for birth and death chains

The criteria on separation cutoff for birth and death chains were obtained by Diaconis and Saloff-Coste in 2006. These criteria are involving all eigenvalues. In this paper, we obtain the explicit criterion, which depends only on the birth and death rates. Furthermore, we present two ways to estimate moments of the fastest strong stationary time and then give another but equivalent criterion explicitly.     

Random doubly stochastic tridiagonal matrices

Let \begin{align*}{\mathcal T}\end{align*}n be the compact convex set of tridiagonal doubly stochastic matrices. These arise naturally in probability problems as birth and death chains with a uniform stationary distribution. We study ‘typical’ matrices T∈ \begin{align*}{\mathcal T}\end{align*}n chosen uniformly at random in the set \begin{align*}{\mathcal T}\end{align*}n. A simple algorithm is presented to allow direct sampling from the uniform distribution on \begin{align*}{\mathcal T}\end{align*}n. Using this algorithm, the elements above the diagonal in T are shown to form a Markov chain. For large n, the limiting Markov chain is reversible and explicitly diagonalizable with transformed Jacobi polynomials as eigenfunctions. These results are used to study the limiting behavior of such typical birth and death chains, including their eigenvalues and mixing times. The results on a uniform random tridiagonal doubly stochastic matrices are related to the distribution of alternating permutations chosen uniformly at random.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 403–437, 2013     

The cutoff phenomenon for randomized riffle shuffles

We study the cutoff phenomenon for generalized riffle shuffles where, at each step, the deck of cards is cut into a random number of packs of multinomial sizes which are then riffled together. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes

In this paper we define and analyze convergence of the geometric random walks, which are certain random walks on vector spaces over finite fields. We show that the behavior of such walks is given by certain random matroid processes. In particular, the mixing time is given by the expected stopping time, and the cutoff is equivalent to sharp threshold. We also discuss some random geometric random walks as well as some examples and symmetric cases.     

THE ERGODICITY FOR BI-IMMIGRATION BIRTH AND DEATH PROCESSES IN RANDOM ENVIRONMENT

The concepts of bi-immigration birth and death density matrix in random environment and bi-immigration birth and death process in random environment are introduced. For any bi-immigration birth and death matrix in random environment Q（θ） with birth rate λ 〈 death rate μ, the following results are proved, （1） there is an unique q-process in random environment, P^-（θ＊（0）;t） = （p^-（θ^＊（0）;t,i,j）,i,j ≥ 0）, which is ergodic, that is, lim t→∞（θ^＊（0）;t,i,j） = π^-（θ^＊（0）;j） ≥0 does not depend on i ≥ 0 and ∑j≥0π （θ＊（0）;j） = 1, （2） there is a bi-immigration birth and death process in random enjvironment （X^＊ = {X^＊,t ≥ 0},ε^＊ = {εt,t ∈ （-∞, ∞）}） with random transition matrix P^-（θ^＊ （0）;t） such that X^＊ is a strictly stationary process.     

随机环境中马氏链的最小闭集

主要研究了随机环境中马氏链的最小闭集的一些性质,并就保守集C在何种情况下存在最小闭子集的开问题结合Foguel的L1-理论进行了讨论,得到了一些结果.     

Identities for stopped markov chains and their applications

In this paper we obtain identities for some stopped Markov chains. These identities give a unified approach to many problems in optimal stopping of a Markovian sequence, extinction probability of a Markovian branching process and martingale theory.     

Lower bounds for covering times for reversible Markov chains and random walks on graphs

For simple random walk on aN-vertex graph, the mean time to cover all vertices is at leastcN log(N), wherec>0 is an absolute constant. This is deduced from a more general result about stationary finite-state reversible Markov chains. Under weak conditions, the covering time for such processes is at leastc times the covering time for the corresponding i.i.d. process.     

Markov chains in random environments and random iterated function systems

We consider random iterated function systems giving rise to Markov chains in random (stationary) environments. Conditions ensuring unique ergodicity and a ``pure type' characterization of the limiting ``randomly invariant' probability measure are provided. We also give a dimension formula and an algorithm for simulating exact samples from the limiting probability measure.

     

Strong stationary duality for continuous-time Markov chains. Part I: Theory

LetX(t), 0t<, be an ergodic continuous-time Markov chain with finite or countably infinite state space. We construct astrong stationary dual chainX ^* whose first hitting times yield bounds on the convergence to stationarity forX. The development follows closely the discrete-time theory of Diaconis and Fill.^(2,3) However, for applicability it is important that we formulate our results in terms of infinitesimal rates, and this raises new issues.     

The cutoff phenomenon for Ehrenfest chains

We consider families of Ehrenfest chains and provide a simple criterion on the L^p$L^p$-cutoff and the L^p$L^p$-precutoff with specified initial states for 1≤p<∞$1\le p<\infty$. For the family with an L^p$L^p$-cutoff, a cutoff time is described and a possible window is given. For the family without an L^p$L^p$-precutoff, the exact order of the L^p$L^p$-mixing time is determined. The result is consistent with the well-known conjecture on cutoffs of Markov chains proposed by Peres in 2004, which says that a cutoff exists if and only if the multiplication of the spectral gap and the mixing time tends to infinity.     

Local uniformity properties for glauber dynamics on graph colorings

We investigate some local properties which hold with high probability for randomly selected colorings of a fixed graph with no short cycles. In a number of related works, establishing these particular properties has been a crucial step towards proving rapid convergence for the single‐site Glauber dynamics, a Markov chain for sampling colorings uniformly at random. For a large class of graphs, this approach yields the most efficient known algorithms for sampling random colorings. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Isomorphism theorems for Markov chains

The isomorphism theorem of Dynkin is definitely an important tool to investigate the problems raised in terms of local times of Markov processes. This theorem concerns continuous time Markov processes. We give here an equivalent version for Markov chains.     

First return probabilities of birth and death chains and associated orthogonal polynomials

For a birth and death chain on the nonnegative integers, integral representations for first return probabilities are derived. While the integral representations for ordinary transition probabilities given by Karlin and McGregor (1959) involve a system of random walk polynomials and the corresponding measure of orthogonality, the formulas for the first return probabilities are based on the corresponding systems of associated orthogonal polynomials. Moreover, while the moments of the measure corresponding to the random walk polynomials give the ordinary return probabilities to the origin, the moments of the measure corresponding to the associated polynomials give the first return probabilities to the origin.

As a by-product we obtain a new characterization in terms of canonical moments for the measure of orthogonality corresponding to the first associated orthogonal polynomials. The results are illustrated by several examples.

     

Distributions of lifetime after explosion for birth and death processes

How long can a process live after explosion for a birth and death process with explosion and lifespan σ,X ={X(t),t<σ}?Distribution of lifetime from explosion to the end of life, expected lifetime and probability of explosion which means the end of life are found.     

The N‐limit of spectral gap of a class of birth–death Markov chains

We extend Zeifman's method for bounding the spectral gap and obtain the asymptotical behaviour, as N→∞, of the spectral gap of a class of birth–death Markov chains known as random walks on a complete graph of size N. Copyright © 2000 John Wiley & Sons, Ltd.     

The bilateral birth–death chain generated by the associated Jacobi polynomials

We give a probabilistic interpretation of the associated Jacobi polynomials, which can be constructed from the three-term recurrence relation for the classical Jacobi polynomials by shifting the integer index n by a real number t. Under certain restrictions, this will give rise to a doubly infinite tridiagonal stochastic matrix, which can be interpreted as the one-step transition probability matrix of a discrete-time bilateral birth–death chain with state space on $\mathbb{Z}$. We also study the unique UL and LU stochastic factorizations of the transition probability matrix, as well as the discrete Darboux transformations and corresponding spectral matrices. Finally, we use all these results to provide an urn model on the integers for the associated Jacobi polynomials.     

The type problem for random walks on trees

We consider the question of whether the simple random walk (SRW) on an infinite tree is transient or recurrent. For random-trees (all vertices of distancen from the root of the tree have degreed _n , where {d _n } are independent random variables), we prove that the SRW is a.s. transient if lim inf _n n E(log(d _n-1))>1 and a.s. recurrent if lim sup _n n E(log(d _n-1))<1. For random trees in which the degrees of the vertices are independently 2 or 3, with distribution depending on the distance from the root, a partial classification of type is obtained.Research supported in part by NSF DMS 8710027.     

Necessary embedding conditions for state-wise monotone Markov chains

In previous work, the embedding problem is examined within the entire set of discrete-time Markov chains. However, for several phenomena, the states of a Markov model are ordered categories and the transition matrix is state-wise monotone. The present paper investigates the embedding problem for the specific subset of state-wise monotone Markov chains. We prove necessary conditions on the transition matrix of a discrete-time Markov chain with ordered states to be embeddable in a state-wise monotone Markov chain regarding time-intervals with length 0.5: A transition matrix with a square root within the set of state-wise monotone matrices has a trace at least equal to 1.