Approximate Counting

Prev: Graph Algorithms Next: Parallel and Distributed Algorithms

Problems

11.1

In this problem we will design a Monte Carlo algorithm to estimate the value of $\pi$. Consider a circle of diameter $1$ enclosed within a square with sides of length $1$. We will sample points uniformly and independently from the square and set the indicator variable $X_t=1$ if the $t$th point is inside the circle, and set $X_t=0$ otherwise. It is clear that $E[X]=N\pi /4$, where $X$ is the sum of $N$ of these indicator variables.

Give an upper bound on the value of $N$ for which $4X/N$ gives an estimator of $\pi$ that is accurate to $d$ digits, with probability at least $1-\delta$.

---

11.2

Due to R.M. Karp, M. Luby, and N. Madras [240].

Consider the following variant of the Coverage algorithm for approximating the DNF counting problem. The $t$th trial of this algorithm first picks a random clause $C_t$, where the probability of choosing a clause $C_j$ is proportional to the number of satisfying truth assignments for it. Next, it selects a random satisfying truth assignment $a$ for the chosen clause. So far, this is exactly the same as the sampling procedure described before. Define the random variable $X_t=1/|\mathrm{cov}(a)|$, where $\mathrm{cov}(a)$ denotes the set of clauses that are satisfied by the truth assignment $a$.

The estimator for #F is the random variable

$$Y=\eta \times \sum _{t=1}^N\frac{X_t}{N},$$

where $\eta$ denotes the sum of the sizes of the coverage sets over all possible truth assignments. Prove that $Y$ is an $(ϵ,\delta )$-approximation for #F when

$$N=\frac{cm}{ϵ}\ln \frac{1}{\delta }$$

for some small constant $c$. (Hint: Use the Chernoff-type bound derived in Problem 4.7.)

---

11.3

Prove the converse of Theorem 11.4. In other words, show that given an algorithm for estimating the number of matchings in a bipartite graph, it is possible to get a near-uniform generator of matchings in the bipartite graph.

---

11.4

In this problem we will see that the problem of counting the perfect matchings in graphs with large minimum degree is also #P-complete. Suppose there is a polynomial time algorithm $A$ for counting the number of perfect matchings in a graph with minimum degree at least $\beta n$, for a constant $0<\beta <1$. Show that there must then exist a polynomial time algorithm for counting the number of perfect matchings in an arbitrary bipartite graph.

---

11.5

Consider the Markov chain induced by a random walk on a connected, undirected graph $G$ on $n$ vertices. How small can the conductance of this Markov chain be, the minimum being taken over connected, undirected graphs on $n$ vertices? How large can it be?

---

11.6

Let $G$ be a connected, undirected graph on $n$ vertices.

(a) Consider the Markov chain induced by the following random process for moving from one spanning tree of $G$ to another: pick edges $e$ and $f$ independently and uniformly at random; if the current spanning tree is $T$ and $T^{\prime }=T+e-f$ is a spanning tree, then move to the new spanning $T^{\prime }$; otherwise stay put at $T$. Show that the conductance of this Markov chain is bounded from below by $1/n^{O(1)}$.

(b) Suggest and analyze an algorithm for approximate counting of the number of spanning trees in a graph $G$, as an alternative to the matrix-tree theorem.

---

11.7

Due to A. Sinclair and M.R. Jerrum [376].

An ergodic Markov chain with transition matrix $P$ is said to be time reversible if for all $i$ and $j$, $P_{ij}{\pi }_i=P_{ji}{\pi }_j$. This is equivalent to requiring that the matrix $DP{D}^{-1}$ is symmetric, where $D$ is a diagonal matrix with $D_{ii}=\sqrt{{\pi }_i}$. Clearly, the largest eigenvalue of $P$ is ${\lambda }_1=1$; define $\lambda ={\max }_{i>1}|{\lambda }_i|$. Show that for any fixed choice of an initial state $X_0$, the relative pointwise distance of this Markov chain at time $t$ is bounded as follows:

$$\Delta (t)\le \frac{{\lambda }^t}{{\min }_i{\pi }_i}.$$

What does this imply for the random walk setting considered in Theorem 6.21?