Concentration for Markov chain cover times
ABSTRACT:
I will talk about an old (1991) result, which says: If the mean cover time
E[V] of a Markov chain is large compared to the maximum mean hitting time,
then V/E[V] is close to 1. This is derived via a concentration result for
IID random subsets of a finite set. An interesting ingredient is a ``see
one step into the future" variant of the martingale maximal inequality.
BIO:
David Aldous is a professor at U.C. Berkeley who is visiting MSR for the
year, and is a Fellow of the Royal Society. He specializes in
mathematical probability; a central theme is the study of large finite
random structures, obtaining asymptotic behavior as the size tends to
infinity via consideration of some suitable infinite random structure. His
current focus is on spatial random networks. Aldous is best known for the
unfinished monograph "Reversible Markov chains and random walks on
graphs".