Browsing by Author "Saloff-Coste, Laurent"

Now showing 1 - 7 of 7

COMPARISON OF CUTOFFS BETWEEN LAZY WALKS AND MARKOVIAN SEMIGROUPS
(2013-12-01)
Chen, Guan-Yu
;
Saloff-Coste, Laurent
;
應用數學系
;
Department of Applied Mathematics
We make a connection between the continuous time and lazy discrete time Markov chains through the comparison of cutoffs and mixing time in total variation distance. For illustration, we consider finite birth and death chains and provide a criterion on cutoffs using eigenvalues of the transition matrix.
Computing cutoff times of birth and death chains
(2015-07-18)
Chen, Guan-Yu
;
Saloff-Coste, Laurent
;
應用數學系
;
Department of Applied Mathematics
Earlier work by Diaconis and Saloff-Coste gives a spectral criterion for a maximum separation cutoff to occur for birth and death chains. Ding, Lubetzky and Peres gave a related criterion for a maximum total variation cutoff to occur in the same setting. Here, we provide complementary results which allow us to compute the cutoff times and windows in a variety of examples.
On the mixing time and spectral gap for birth and death chains
(2013-01-01)
Chen, Guan-Yu
;
Saloff-Coste, Laurent
;
應用數學系
;
Department of Applied Mathematics
For birth and death chains, we derive bounds on the spectral and mixing time in terms of birth and death rates. Together with the results of et al. (2010), this provides a criterion for the existence of a cutoff in terms of the birth and death rates. A variety of illustrative examples are treated.
Spectral computations for birth and death chains
(2014-01-01)
Chen, Guan-Yu
;
Saloff-Coste, Laurent
;
應用數學系
;
Department of Applied Mathematics
We consider the spectrum of birth and death chains on an n-path. An iterative scheme is proposed to compute any eigenvalue with exponential convergence rate independent of n. This allows one to determine the whole spectrum in order n(2) elementary operations. Using the same idea, we also provide a lower bound on the spectral gap, which is of the correct order on some classes of examples. (C) 2013 Elsevier B.V. All rights reserved.
The cutoff phenomenon for ergodic Markov processes
(2008-01-20)
Chen, Guan-Yu
;
Saloff-Coste, Laurent
;
應用數學系
;
Department of Applied Mathematics
We consider the cutoff phenomenon in the context of families of ergodic Markov transition functions. This includes classical examples such as families of ergodic finite Markov chains and Brownian motion on families of compact Riemannian manifolds. We give criteria for the existence of a cutoff when convergence is measured in L(p)-norm, 1 < p < infinity. This allows us to prove the existence of a cutoff in cases where the cutoff time is not explicitly known. In the reversible case, for 1 < p <= infinity, we show that a necessary and sufficient condition for the existence of a max-L(p) cutoff is that the product of the spectral gap by the max-L(p) mixing time tends to infinity. This type of condition was suggested by Yuval Peres. Illustrative examples are discussed.
The L(2)-cutoff for reversible Markov processes
(2010-04-01)
Chen, Guan-Yu
;
Saloff-Coste, Laurent
;
應用數學系
;
Department of Applied Mathematics
We consider the problem of proving the existence of an L(2)-cutoff for families of ergodic Markov processes started from given initial distributions and associated with reversible (more, generally, normal) Markov semigroups. This includes classical examples such as families of finite reversible Markov chains and Brownian motion on compact Riemannian manifolds. We give conditions that are equivalent to the existence of an L(2)-cutoff and describe the L(2)-cutoff time in terms of the spectral decomposition. This is illustrated by several examples including the Ehrenfest process and the biased (p, q)-random walk on the non-negative integers, both started froth an arbitrary point. (C) 2009 Elsevier Inc. All rights reserved.
The L-2-cutoff for reversible Markov processes
(2010-04-01)
Chen, Guan-Yu
;
Saloff-Coste, Laurent
;
應用數學系
;
Department of Applied Mathematics
We consider the problem of proving the existence of an L-2-cutoff for families of ergodic Markov processes started from given initial distributions and associated with reversible (more, generally, normal) Markov semigroups. This includes classical examples such as families of finite reversible Markov chains and Brownian motion on compact Riemannian manifolds. We give conditions that are equivalent to the existence of an L-2-cutoff and describe the L-2-cutoff time in terms of the spectral decomposition. This is illustrated by several examples including the Ehrenfest process and the biased (p, q)-random walk on the non-negative integers, both started froth an arbitrary point. (C) 2009 Elsevier Inc. All rights reserved.