Seminar

Language English
From 2010/03/12 13:00
To 2010/03/12 14:30
PlaceRoom 552, Building No.3, Faculty of Science, Kyoto University
Seminar NameBreak-up Geometry Analysis Seminar
Title Mixing times and new Cheeger inequalities for finite Markov chains¡¡
Field Analysis
Other
SpeakersRavi Montenegroȇ
AffiliationUniversity of Massachusetts Lowell
AbstractThe Perron-Frobenius theorem guarantees that a finite
stochastic Matrix satisfying the reversibility
condition has a real valued eigenbasis with eigenvalues
.
The spectral gap governs key properties of
the associated random walk. Several authors have shown lower bounds
on this gap in terms of geometric quantities on the underlying state
space, known as Cheeger inequalities. We show sharp Cheeger-like lower
bounds on , both in the edge-expansion sense of Jerrum and
Sinclair, the vertex-expansion notion of Alon, and a mixture of
both. Cheeger-like lower bounds on follow as well,
in terms of a notion of a fairly natural notion of edge-expansion
which is yet entirely new.
Linkhttp://www.math.kyoto-u.ac.jp/~kumagai/DGA.html