Intersection and mixing times for reversible chains

Yuval Peres, Thomas Sauerwald, Perla Sousi, Alexandre Stauffer

Research output: Contribution to journalArticle

2 Citations (Scopus)
57 Downloads (Pure)

Abstract

Suppose X and Y are two independent irreducible Markov chains on n states. We consider the intersection time, which is the first time their trajectories intersect. We show for reversible and lazy chains that the total variation mixing time is always upper bounded by the expected intersection time taken over the worst starting states. For random walks on trees we show the two quantities are equivalent. We obtain an expression for the expected intersection time in terms of the eigenvalues for reversible and transitive chains. For such chains we also show that it is up to constants the geometric mean of n and E[I], where I is the number of intersections up to the uniform mixing time. Finally for random walks on regular graphs we obtain sharp inequalities that relate the expected intersection time to maximum hitting time and mixing time.
Original languageEnglish
Article number12
JournalElectronic Journal of Probability
Volume22
Early online date3 Feb 2017
DOIs
Publication statusPublished - 2017

Fingerprint

Mixing Time
Intersection
Random walk
Hitting Time
Sharp Inequality
Geometric mean
Total Variation
Regular Graph
Intersect
Markov chain
Trajectory
Eigenvalue

Keywords

  • math.PR
  • 60J10

Cite this

Intersection and mixing times for reversible chains. / Peres, Yuval; Sauerwald, Thomas; Sousi, Perla; Stauffer, Alexandre.

In: Electronic Journal of Probability, Vol. 22, 12, 2017.

Research output: Contribution to journalArticle

Peres, Yuval ; Sauerwald, Thomas ; Sousi, Perla ; Stauffer, Alexandre. / Intersection and mixing times for reversible chains. In: Electronic Journal of Probability. 2017 ; Vol. 22.
@article{cc6dcdee0a7f42729dd22001caaaf2e1,
title = "Intersection and mixing times for reversible chains",
abstract = "Suppose X and Y are two independent irreducible Markov chains on n states. We consider the intersection time, which is the first time their trajectories intersect. We show for reversible and lazy chains that the total variation mixing time is always upper bounded by the expected intersection time taken over the worst starting states. For random walks on trees we show the two quantities are equivalent. We obtain an expression for the expected intersection time in terms of the eigenvalues for reversible and transitive chains. For such chains we also show that it is up to constants the geometric mean of n and E[I], where I is the number of intersections up to the uniform mixing time. Finally for random walks on regular graphs we obtain sharp inequalities that relate the expected intersection time to maximum hitting time and mixing time.",
keywords = "math.PR, 60J10",
author = "Yuval Peres and Thomas Sauerwald and Perla Sousi and Alexandre Stauffer",
year = "2017",
doi = "10.1214/16-EJP18",
language = "English",
volume = "22",
journal = "Electronic Journal of Probability",
issn = "1083-6489",
publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Intersection and mixing times for reversible chains

AU - Peres, Yuval

AU - Sauerwald, Thomas

AU - Sousi, Perla

AU - Stauffer, Alexandre

PY - 2017

Y1 - 2017

N2 - Suppose X and Y are two independent irreducible Markov chains on n states. We consider the intersection time, which is the first time their trajectories intersect. We show for reversible and lazy chains that the total variation mixing time is always upper bounded by the expected intersection time taken over the worst starting states. For random walks on trees we show the two quantities are equivalent. We obtain an expression for the expected intersection time in terms of the eigenvalues for reversible and transitive chains. For such chains we also show that it is up to constants the geometric mean of n and E[I], where I is the number of intersections up to the uniform mixing time. Finally for random walks on regular graphs we obtain sharp inequalities that relate the expected intersection time to maximum hitting time and mixing time.

AB - Suppose X and Y are two independent irreducible Markov chains on n states. We consider the intersection time, which is the first time their trajectories intersect. We show for reversible and lazy chains that the total variation mixing time is always upper bounded by the expected intersection time taken over the worst starting states. For random walks on trees we show the two quantities are equivalent. We obtain an expression for the expected intersection time in terms of the eigenvalues for reversible and transitive chains. For such chains we also show that it is up to constants the geometric mean of n and E[I], where I is the number of intersections up to the uniform mixing time. Finally for random walks on regular graphs we obtain sharp inequalities that relate the expected intersection time to maximum hitting time and mixing time.

KW - math.PR

KW - 60J10

U2 - 10.1214/16-EJP18

DO - 10.1214/16-EJP18

M3 - Article

VL - 22

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

SN - 1083-6489

M1 - 12

ER -