Questions? Call 800-624-6242

| Items in cart [0]

PAPERBACK
price:\$52.75

Probability and Algorithms (1992) Commission on Physical Sciences, Mathematics, and Applications (CPSMA)

Citation Manager

. "3 Approximate Counting Via Markov Chains." Probability and Algorithms. Washington, DC: The National Academies Press, 1992.

Please select a format:

 Page 32

The following HTML text is provided to enhance online readability. Many aspects of typography translate only awkwardly to HTML. Please use the page image as the authoritative form to ensure accuracy.

Probability and Algorithms

could (in principle) analyze the working of the algorithm in order to calculate the chance p of getting the identity permutation. Then we can say that the number of permutations equals 1/p.

But now suppose we have a hard counting problem for which we cannot find an explicit formula for |S|. The purpose of this chapter is to describe a remarkable technique for constructing randomized algorithms that count S approximately. This technique, developed in recent years, has two ingredients. The first idea is that in some settings, having an algorithm for generating an approximately uniform random element of S can be used re-cursively to estimate approximately the size |S|. We illustrate this with two examples in the next section. The second idea is that we can obtain an approximately uniform random element of S by running a suitable Markov chain on state-space S for sufficiently many steps. This idea and the particular chains used in the two examples are discussed in §3.3. The latter idea is fundamentally similar to the use of Markov chains in the Metropolis 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. Our Markov chains are simpler to analyze and permit rigorous discussion of polynomial-time convergence issues that seem too hard for rigorous treatment in the context of simulated annealing.

3.2Recursive Estimation of Size

Example: Volume of a Convex Set (Dyer et ah, 1989, 1991). Consider the problem of estimating the volume vol(K) of a convex set K in n-dimensional space, for large n. Suppose we are told that , where B(r) is the ball of radius r = r(n). It is believed that there is no polynomial-time deterministic algorithm to approximate vol(K). But suppose we have a means of simulating, at unit cost, a random point in K whose distribution is approximately uniform. Specify some subset K1 with and for which vol(K1)/vol(K) is not near 0 or 1. Then by simulating m random points in K and counting the proportion p(1) that fall within K1,

Now specify a decreasing sequence of such convex subsets

 Page 32
 Front Matter (R1-R10) 1 Introduction (1-16) 2 Simulated Annealing (17-30) 3 Approximate Counting Via Markov Chains (31-38) 4 Probabilistic Algorithms for Speedup (39-52) 5 Probabilistic Algorithms for Defeating Adversaries (53-64) 6 Pseudorandom Numbers (65-86) 7 Probabilistic Analysis of Packing and Related Partitioning Problems (87-108) 8 Probability and Problems in Euclidean Combinatorial Optimization (109-130) 9 Probabilistic Analysis in Linear Programming (131-148) 10 Randomization in Parallel Algorithms (149-160) 11 Randomly Wired Multistage Networks (161-174) 12 Missing Pieces, Derandomization, and Concluding Remarks (175-178)