Any finite graph, G, together with a distinguished "initial vertex," determines a natural random walk on the vertices of G. In the case when G is undirected and connected, several important quantities can be associated with this walk, including the expected cover time (the first time when every vertex has been visited) and the mixing time (the number of steps before the distribution on the vertex set is within variation distance 1/2 of the stationary distribution). Recent work of Winkler and Zuckerman has identified the importance of a new quantity, the blanket time (or multiple cover time). This is the expected number of steps required before the distribution induced by the history of the walk closely approximates the stationary distribution.
We show that in the case when the walk is on a Cayley graph, one can employ Diaconis' satisfying representation-theoretic framework for bounding the mixing time of a random walk to address the blanket time problem. This approach relates walks on certain semi-direct products to the blanket time problem and applies Wigner's method of "little groups" for elucidating the structure of the representations of such groups. As an example of this new framework, we recover several classical results about random walks on the circle.
Joint work with S. Ravi Kumar.