Stratified Random Walks on the N-Cube

this paper we present a method for analyzing a general class of random walks on the n-cube. These walks have the property that the transition probabilities (only) depend on the level (or weight) of the point the walk happens to be at, which is why we refer to them as stratified walks. All our walks will be reversible, and will have uniform stationary distributions. Our main goal will be to bound the rate at which the evolving distribution converges to its stationary distribution as a function of the number of steps taken by the walk. In particular, we will illustrate the method with several specific examples, giving for the first time sharp bounds on the mixing times of these walks. For example, one special case is the following walk on Q n (suggested by David Aldous [A94]): From x = (x 1 ; : : : ; x n ) 2 Q n , choose a random pair (i; j) of distinct indices and move to