| Rapidly Mixing Markov Chains (2001) | |||||||||||||||||
Abstract | |||||||||||||||||
| The computational difficulty of the problems of counting the elements of a finite set of combinatorial structures has led to the development of randomized 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. Contents 1 | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||