Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
3 Approximate Counting Via Markov Chains
3 Approximate Counting Via Markov Chains
Pages 31-38
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 31... ...
having a bounded-time algorithm for generating a uniform random element of S As an elementary illustration, we aD know that there are n!
|
From page 32... ...
The latter idea is fundamentally similar to the use of Markov chains in the Metropm lis algorithm, which underlies the simulated annealing algorithm discussed in Chapter 2. The difference is that here we seek to simulate a uniform distribution rather than a distribution that is deliberately biased towards minima of a cost function.
|
From page 33... ...
Let us show how to do so, given a method of simulating approximately uniform random matchings. Enumerate the vertices as s~,s2, lS;n.
|
From page 34... ...
The simplest way to define such a chain is to define a regular graph structure with vertex-set S In this graph setting, let the Markov chain be a simple random walk on the graph, at each step moving from the current vertex s to a vertex s' chosen uniformly from the neighbors of s.
|
From page 35... ...
- O 3.4 Estimating Mixing Times There is a glaring gap to bridge before we can use the Markov chain method as an honest randomized algorithm. In the simplest use of this method, we wiD run the chain for some number k of steps and employ the final state as our "approximately uniforms random element.
|
From page 36... ...
The real issue is not the choice of definition but the development of widely applicable techniques that enable some mixing time to be bounded. One interesting technique is to relate mixing times to the quantity r-.
|
From page 37... ...
We mentioned that the Markov chain method was just a specialization of the Metropolis algorithm for simulating a given probability distribution by inventing a suitable Markov chain. Physicists have long used that algorithm for simulation but typically have been unable to justify rigorously the results of the simulation by proving bounds on the mixing time.
|
From page 38... ...
Jerrum (1989) , Approximate counting, uniform generation and rapidly mixing Markov chains, Inform.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.