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).