October 13, 2004

Yuval Peres

Metric embeddings and Markov chains have been interacting fruitfully with theoretical computer Science; we discuss a notion that combines them.  A family F of metric spaces has (uniform) Markov type 2, if for any stationary reversible finite Markov chain in a space from F, the expected distance squared $E(D_t^2)$ from the starting point to the location after $t$ steps grows at most at a uniform linear rate. 

This notion is due to K. Ball (1992), who showed its importance for Lipshitz extensions.  E.g $L^2$ has uniform Markov type 2, but expander graphs and hypercubes do not. Saying this quantitatively yields "robust" lower bounds on distortion of embeddings, that are sharp in many cases.  Recently, we showed that $L^p$ for fixed finite $p>2$, trees and Gromov hyperbolic graphs all have uniform Markov type $2$; it is open whether planar graphs have this property. 

(joint work with A. Naor, S. Sheffield and O. Schramm).