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