Cover times for sequences of random walks on random graphs

Speaker: Yoshihiro Abe

Date: Thu, Jun 21, 2012

Location: PIMS, University of British Columbia

Conference: PIMS-MPrime Summer School in Probability

Subject: Mathematics, Probability

Class: Scientific

Abstract:

We can classify cover times for sequences of random walks on random graphs into two types: One type is the class of cover times approximated by the maximal hitting times scaled by the logarithm of the size of vertex sets. The other type is the class of cover times approximated by the maximal hitting times. These types are characterized by the volume, effective resistances, and geometric properties of random graphs. We classify some examples, such as the supercritical Galton-Watson family trees and the incipient infinite cluster for the critical Galton-Watson family tree.