Rapidly Mixing Markov Chains
The computational di culty of the problems of counting the elements of a nite set of combinatorial structures has led to the development of random ized algorithms The problem of generating at random an element of a set with some property is central for various randomized algorithms because of its connection with counting problem A technique based on Markov chain is used to generate uniformly at random the element of set This leads to polynomial time randomized algorithm if the Markov chain is rapidly mixing