Abstract
We compute tight lower bounds on the log-Sobolev constant of a class of inductively defined Markov chains, which contains the bases — exchange walks for balanced matroids studied by Feder and Mihail. As a corollary, we obtain improved upper bounds for the mixing time of a variety of Markov chains. An example: the "natural" random walk on spanning trees of a graph G as proposed by Broder — which has been studied by a number of authors — mixes in time O(mn log n),wheren is the number of vertices of G and m the number of edges. This beats the best previous upper bound on this walk by a factor n2.