Bounds on the l2spectrum for markov chains and markov processes: A generalization of cheeger’s inequality

Gregory F. Lawler; Alan D. Sokal

doi:10.1090/S0002-9947-1988-0930082-9

Bounds on the l²spectrum for markov chains and markov processes: A generalization of cheeger’s inequality

Gregory F. Lawler, Alan D. Sokal

Research output: Contribution to journal › Article › peer-review

Abstract

We prove a general version of Cheeger’s inequality for discretetime Markov chains and continuous-time Markovian jump processes, both reversible and nonreversible, with general state space. We also prove a version of Cheeger’s inequality for Markov chains and processes with killing. As an application, we prove L²exponential convergence to equilibrium for random walk with inward drift on a class of countable rooted graphs.

Original language	English (US)
Pages (from-to)	557-580
Number of pages	24
Journal	Transactions of the American Mathematical Society
Volume	309
Issue number	2
DOIs	https://doi.org/10.1090/S0002-9947-1988-0930082-9
State	Published - Oct 1988

ASJC Scopus subject areas

Mathematics(all)
Applied Mathematics

Access to Document

10.1090/S0002-9947-1988-0930082-9

Cite this

@article{3910ee41b3f44677b5ce19cd8487ef5d,

title = "Bounds on the l2spectrum for markov chains and markov processes: A generalization of cheeger{\textquoteright}s inequality",

abstract = "We prove a general version of Cheeger{\textquoteright}s inequality for discretetime Markov chains and continuous-time Markovian jump processes, both reversible and nonreversible, with general state space. We also prove a version of Cheeger{\textquoteright}s inequality for Markov chains and processes with killing. As an application, we prove L2exponential convergence to equilibrium for random walk with inward drift on a class of countable rooted graphs.",

author = "Lawler, {Gregory F.} and Sokal, {Alan D.}",

year = "1988",

month = oct,

doi = "10.1090/S0002-9947-1988-0930082-9",

language = "English (US)",

volume = "309",

pages = "557--580",

journal = "Transactions of the American Mathematical Society",

issn = "0002-9947",

publisher = "American Mathematical Society",

number = "2",

}

TY - JOUR

T1 - Bounds on the l2spectrum for markov chains and markov processes

T2 - A generalization of cheeger’s inequality

AU - Lawler, Gregory F.

AU - Sokal, Alan D.

PY - 1988/10

Y1 - 1988/10

N2 - We prove a general version of Cheeger’s inequality for discretetime Markov chains and continuous-time Markovian jump processes, both reversible and nonreversible, with general state space. We also prove a version of Cheeger’s inequality for Markov chains and processes with killing. As an application, we prove L2exponential convergence to equilibrium for random walk with inward drift on a class of countable rooted graphs.

AB - We prove a general version of Cheeger’s inequality for discretetime Markov chains and continuous-time Markovian jump processes, both reversible and nonreversible, with general state space. We also prove a version of Cheeger’s inequality for Markov chains and processes with killing. As an application, we prove L2exponential convergence to equilibrium for random walk with inward drift on a class of countable rooted graphs.

UR - http://www.scopus.com/inward/record.url?scp=0000941412&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000941412&partnerID=8YFLogxK

U2 - 10.1090/S0002-9947-1988-0930082-9

DO - 10.1090/S0002-9947-1988-0930082-9

M3 - Article

AN - SCOPUS:0000941412

VL - 309

SP - 557

EP - 580

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

SN - 0002-9947

IS - 2

ER -

Bounds on the l²spectrum for markov chains and markov processes: A generalization of cheeger’s inequality

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this