MULTIPLE COVER TIME

Motivated by applications in Markov estimation and distributed computi ng, we define the blanket time of an undirected graph G to be the expe cted time for a random walk to hit every vertex of G within a constant factor of the number of times predicted by the stationary distributio n. Thus the blanket time is, essentially, the number of steps required of a random walk in order that the observed distribution reflect the stationary distribution. We provide substantial evidence for the follo wing conjecture: that the blanket time of a graph never exceeds the co ver time by more than a constant factor. In other words, at the cost o f a multiplicative constant one can hit every vertex often instead of merely once. We prove the conjecture in the case where the cover time and maximum hitting time differ by a logarithmic factor. This case inc ludes almost all graphs, as well as most ''natural'' graphs: the hyper cube, k-dimensional lattices for k greater than or equal to 2, balance d k-ary trees, and expanders. We further prove the conjecture for perh aps the most natural graphs not falling in the above case: paths and c ycles. Finally, we prove the conjecture in the case of independent sto chastic processes. (C) 1996 John Wiley & Sons, Inc.