imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| = Parameter Estimation = | | == Lovász Local Lemma== |
| Consider the following abstract problem of parameter estimation.
| | Given a sequence of events <math>A_1,A_2,\ldots,A_n</math>, we use the '''dependency graph''' to describe the dependencies between these events. |
| | |
| Let <math>U</math> be a finite set of known size, and let <math>G\subseteq U</math>. We want to estimate the ''parameter'' <math>|G|</math>, i.e. the size of <math>G</math>, or equivalently, the density (or frequency) <math>\frac{|G|}{|U|}</math>.
| |
| | |
| We assume two devices:
| |
| * A '''uniform sampler''' <math>\mathcal{U}</math>, which uniformly and independently samples a member of <math>U</math> upon each calling.
| |
| * A '''membership oracle''' of <math>G</math>, denoted <math>\mathcal{O}</math>. Given as the input an <math>x\in U</math>, <math>\mathcal{O}(x)</math> indicates whether or not <math>x</math> is a member of <math>G</math>.
| |
| | |
| Equipped by <math>\mathcal{U}</math> and <math>\mathcal{O}</math>, we can have the following '''Monte Carlo method''':
| |
| *Choose <math>N</math> independent samples from <math>U</math> by the uniform sampler <math>\mathcal{U}</math>, represented by the random variables <math>X_1,X_2,\ldots, X_N</math>.
| |
| * Let <math>Y_i</math> be the indicator random variable defined as <math>Y_i=\mathcal{O}(X_i)</math>, namely, <math>Y_i</math> indicates whether <math>X_i\in G</math>.
| |
| * Define the estimator random variable for <math>|G|</math> as
| |
| ::<math>Z=\frac{|U|}{N}\sum_{i=1}^N Y_i</math>
| |
| * Define the estimator random variable for <math>\alpha=\frac{|G|}{|U|}</math> as
| |
| ::<math>\overline{Y}=\frac{1}{N}\sum_{i=1}^N Y_i</math>.
| |
| | |
| It is easy to see that <math>\mathbf{E}[Z]=|G|</math> and <math>\mathbf{E}[\overline{Y}]=\alpha</math>.
| |
| We might hope that with high probability the values of <math>Z</math> and <math>\overline{Y}</math> are close to their respective expectations. Formally, <math>Z</math> is called an '''<math>\epsilon</math>-approximation''' of <math>|G|</math> if
| |
| :<math>
| |
| (1-\epsilon)|G|\le Z\le (1+\epsilon)|G|.
| |
| </math>
| |
| And <math>\overline{Y}</math> is called an '''<math>(\epsilon,\delta)</math>-estimator''' for <math>\alpha</math> if
| |
| :<math>
| |
| \Pr[|\overline{Y}-\alpha|\le \epsilon]\ge 1-\delta.
| |
| </math>
| |
| | |
| The following general theorem bounds the reliance between the accuracy of estimation and the number of samples.
| |
|
| |
|
| {{Theorem | | {{Theorem |
| |Theorem (estimator theorem)| | | |Definition| |
| :Let <math>\alpha=\frac{|G|}{|U|}</math>. The following holds: | | :Let <math>A_1,A_2,\ldots,A_n</math> be a sequence of events. A graph <math>D=(V,E)</math> on the set of vertices <math>V=\{1,2,\ldots,n\}</math> is called a '''dependency graph''' for the events <math>A_1,\ldots,A_n</math> if for each <math>i</math>, <math>1\le i\le n</math>, the event <math>A_i</math> is mutually independent of all the events <math>\{A_j\mid (i,j)\not\in E\}</math>. |
| :1. <math>Z</math> is an <math>\epsilon</math>-approximation to <math>|G|</math> with probability at least <math>1-\delta</math> if
| |
| ::<math>N\ge\frac{4}{\epsilon^2 \alpha}\ln\frac{2}{\delta}</math>.
| |
| :2. <math>\overline{Y}</math> is an <math>(\epsilon,\delta)</math>-estimator for <math>\alpha</math> if
| |
| ::<math>N\ge\frac{4}{\epsilon^2}\ln\frac{2}{\delta}</math>.
| |
| }} | | }} |
| {{Proof|
| |
| Recall that <math>Y_i</math> indicates whether the <math>i</math>-th sample is in <math>G</math>. Let <math>Y=\sum_{i=1}^NY_i</math>. Then we have <math>Z=\frac{|U|}{N}Y</math>, and hence the event <math>(1-\epsilon)|G|\le Z\le (1+\epsilon)|G|</math> is equivalent to that <math>(1-\epsilon)\frac{|G|}{|U|}N\le Y\le (1+\epsilon)\frac{|G|}{|U|}N</math>. Note that each <math>Y_i</math> is a Bernoulli trial that succeeds with probability <math>\frac{|G|}{|U|}</math>, thus <math>\mathbb{E}[Y]=\frac{|G|}{|U|}N</math>. Then the rest is due to Chernoff bound.}}
| |
|
| |
|
| A counting algorithm for the set <math>G</math> has to deal with the following three issues:
| | The notion of mutual independence between an event and a set of events is formally defined as follows. |
| # Implement the membership oracle <math>\mathcal{O}</math>. This is usually straightforward, or assumed by the model.
| | {{Theorem|Definition| |
| # Implement the uniform sampler <math>\mathcal{U}</math>. This can be straightforward or highly nontrivial, depending on the problem.
| | :An event <math>A</math> is said to be '''mutually independent''' of events <math>B_1,B_2,\ldots, B_k</math>, if for any disjoint <math>I^+,I^-\subseteq\{1,2,lots,k\}</math>, it holds that |
| # Deal with exponentially small <math>\alpha=\frac{|G|}{|U|}</math>. This requires us to cleverly choose the universe <math>U</math>. And this part usually uses some beautiful ideas.
| | ::<math>\Pr\left[A\mid \bigwedge_{i\in I^+}B_i\wedge \bigwedge_{i\in I^-}\overline{B_i}\right]=\Pr[A]</math>. |
| | |
| = Counting DNFs =
| |
| A disjunctive normal form (DNF) formular is a disjunction (OR) of clauses, where each clause is a conjunction (AND) of literals. For example:
| |
| :<math>(x_1\wedge \overline{x_2}\wedge x_3)\vee(x_2\wedge x_4)\vee(\overline{x_1}\wedge x_3\wedge x_4)</math>. | |
| Note the difference from the conjunctive normal forms (CNF).
| |
| | |
| Given a DNF formular <math>\phi</math> as the input, the problem is to count the number of satisfying assignments of <math>\phi</math>. This problem is [http://en.wikipedia.org/wiki/Sharp-P-complete '''#P-complete''']. So we do not expect to have a polynomial-time algorithm for exact solving the problem. Instead we are seeking for approximation algorithms. Interestingly, even though the computational complexity of the problem is so high, it admits some very nice approximation algorithm which has very good approximation ratio (theoretically speaking). We need to introduce some general concepts for approximation algorithms.
| |
| | |
| {{Theorem|FPTAS (Fully Polynomial-Time Approximation Scheme)|
| |
| :Consider a computational problem <math>f:\{0,1\}^*\to \mathbb{Z}^+</math> whose outputs are positive integers.
| |
| | |
| :A '''FPTAS (fully polynomial-time approximation scheme)''' for <math>f</math> is an algorithm <math>\mathcal{A}</math> that takes the following inputs:
| |
| :*an input instance <math>x</math> of problem <math>f</math>, which we use <math>n=|x|</math> to denote its length; | |
| :*a real number <math>0<\epsilon<1</math>; | |
| :and in time polynomial in both <math>n</math> and <math>\frac{1}{\epsilon}</math>, returns an output <math>\mathcal{A}(x,\epsilon)</math> such that
| |
| ::<math>
| |
| (1-\epsilon)f(x)\le\mathcal{A}(x,\epsilon)\le (1+\epsilon)f(x).
| |
| </math> | |
| }} | | }} |
|
| |
|
| The adverb "fully" stresses the polynomial reliance on not just the input size <math>n</math> but also the approximation parameter <math>\frac{1}{\epsilon}</math>. An FPTAS may approximate the true value of the output within any accuracy in polynomial time, though the polynomial becomes larger when the approximation is more accurate. Moreover, the running time grows just polynomially with repeat to the accuracy bounds. Theoretically speaking, FPTAS is the best we can get for computational hard problems, though in practice sometimes the polynomial bound might be too large even for a moderate <math>\epsilon</math>.
| | ;Example |
| | :Let <math>X_1,X_2,\ldots,X_m</math> be a set of ''mutually independent'' random variables. Each event <math>A_i</math> is a predicate defined on a number of variables among <math>X_1,X_2,\ldots,X_m</math>. Let <math>v(A_i)</math> be the unique smallest set of variables which determine <math>A_i</math>. The dependency graph <math>D=(V,E)</math> is defined by |
| | :::<math>(i,j)\in E</math> iff <math>v(A_i)\cap v(A_j)\neq \emptyset</math>. |
|
| |
|
| The FPRAS (fully polynomial-time randomized approximation scheme), on the other hand, is the randomized relaxation of FPTAS. | | The following lemma, known as the Lovász local lemma, first proved by Erdős and Lovász in 1975, is an extremely powerful tool, as it supplies a way for dealing with rare events. |
|
| |
|
| {{Theorem|FPRAS (Fully Polynomial-time Randomized Approximation Scheme)| | | {{Theorem |
| :Consider a computational problem <math>f:\{0,1\}^*\to \mathbb{Z}^+</math> whose outputs are positive integers. | | |Lovász Local Lemma (symmetric case)| |
| | | :Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold: |
| :A '''FPRAS (fully polynomial-time randomized approximation scheme)''' for <math>f</math> is a randomized algorithm <math>\mathcal{A}</math> that takes the following inputs:
| | :#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>; |
| :*an input instance <math>x</math> of problem <math>f</math>, which we use <math>n=|x|</math> to denote its length; | | :#the maximum degree of the dependency graph for the events <math>A_1,A_2,\ldots,A_n</math> is <math>d</math>, and |
| :*two real numbers <math>0<\epsilon,\delta<1</math>;
| | :::<math>ep(d+1)\le 1</math>. |
| :and in time polynomial in <math>n</math>, <math>\frac{1}{\epsilon}</math>, and <math>\log\frac{1}{\delta}</math>, returns an output <math>\mathcal{A}(x,\epsilon,\delta)</math> such that | | :Then |
| ::<math> | | ::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>. |
| \Pr\left[(1-\epsilon)f(x)\le\mathcal{A}(x,\epsilon,\delta)\le (1+\epsilon)f(x)\right]\ge 1-\delta. | |
| </math> | |
| }} | | }} |
|
| |
|
| Note that the reliance on the ''confidence error'' <math>\delta</math> is polynomial in <math>\log\frac{1}{\delta}</math>, instead of <math>\frac{1}{\delta}</math>. This is because due to the Chernoff bound, the confidence error can be reduced in an exponential rate by independent repetitions. This motivates the following simpler but equivalent definition of FPRAS, which only considers the special confidence error <math>\delta=\frac{1}{3}</math>. Apparently, this is a more natural way to relax the FPTAS to randomized algorithms as it mimics the way of generalizing class '''P''' to '''BPP''' for decision problems. If you are familiar with the Chernoff bound, it is quite easy to observe the equivalence between the following definition and the above one. And this simple definition is also easier to check (you only need to verify the case for the error <math>\delta=\frac{1}{3}</math>), which makes it more convenient to apply.
| | We will prove a general version of the local lemma, where the events <math>A_i</math> are not symmetric. This generalization is due to Spencer. |
| | | {{Theorem |
| {{Theorem|FPRAS (equivalent simple version)| | | |Lovász Local Lemma (general case)| |
| :Consider a computational problem <math>f:\{0,1\}^*\to \mathbb{Z}^+</math> whose outputs are positive integers. | | :Let <math>D=(V,E)</math> be the dependency graph of events <math>A_1,A_2,\ldots,A_n</math>. Suppose there exist real numbers <math>x_1,x_2,\ldots, x_n</math> such that <math>0\le x_i<1</math> and for all <math>1\le i\le n</math>, |
| | | ::<math>\Pr[A_i]\le x_i\prod_{(i,j)\in E}(1-x_j)</math>. |
| :A '''FPRAS (fully polynomial-time randomized approximation scheme)''' for <math>f</math> is a randomized algorithm <math>\mathcal{A}</math> that takes the following inputs:
| | :Then |
| :*an input instance <math>x</math> of problem <math>f</math>, which we use <math>n=|x|</math> to denote its length;
| | ::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge\prod_{i=1}^n(1-x_i)</math>. |
| :*a real number <math>0<\epsilon<1</math>;
| |
| :and in time polynomial in <math>n</math> and <math>\frac{1}{\epsilon}</math>, returns an output <math>\mathcal{A}(x,\epsilon)</math> such that
| |
| ::<math> | |
| \Pr\left[(1-\epsilon)f(x)\le\mathcal{A}(x,\epsilon)\le (1+\epsilon)f(x)\right]\ge \frac{2}{3}. | |
| </math>
| |
| }}
| |
| | |
| The Monte Carlo method for the parameter estimation problem would give us an FPRAS if the sampler and membership oracle are poly-time realizable and the fraction <math>\alpha=\frac{|G|}{|U|}</math> is bounded from below by a <math>\frac{1}{\mathrm{poly}(n)}</math>.
| |
| | |
| However, for the DNF counting problem, naively applying the Monte Carlo method (treat the set of all <math>2^n</math> truth assignments as <math>U</math> and the set of DNF solutions as <math>G</math>) will not give a good algorithm. The problem is that the fraction <math>\alpha=\frac{|G|}{|U|}</math> can be exponentially small:
| |
| :Suppose that there are <math>n</math> variables. Let <math>U=\{\mathrm{true},\mathrm{false}\}^n</math> be the set of all truth assignments of the <math>n</math> variables. Let <math>G=\{x\in U\mid \phi(x)=\mathrm{true}\}</math> be the set of satisfying assignments for <math>\phi</math>. The straightforward use of Monte Carlo method samples <math>N</math> assignments from <math>U</math> and check how many of them satisfy <math>\phi</math>. This algorithm fails when <math>|G|/|U|</math> is exponentially small, namely, when exponentially small fraction of the assignments satisfy the input DNF formula. | |
| | |
| So instead of naively considering the space of satisfying solutions and the space of all solutions, we represent the space of satisfying solutions to a DNF formula as a union of sets of satisfying solutions to the individual clauses, and count this union of sets. This gives us an abstract problem called the union of sets problem.
| |
| | |
| ==The union of sets problem==
| |
| We reformulate the DNF counting problem in a more abstract framework, called the '''union of sets''' problem.
| |
| | |
| {{Theorem|The union of sets problem|
| |
| :Let <math>V</math> be a finite universe.
| |
| :'''Input''': <math>m</math> subsets <math>H_1,H_2,\ldots,H_m\subseteq V</math> of the universe;
| |
| :'''Output''': the size of the union set <math>H=\bigcup_{i=1}^m H_i</math>
| |
| }} | | }} |
|
| |
|
| To make the algorithm work, we make the following assumptions: | | To see that the general LLL implies symmetric LLL, we set <math>x_i=\frac{1}{d+1}</math> for all <math>i=1,2,\ldots,n</math>. Then we have <math>\left(1-\frac{1}{d+1}\right)^d>\frac{1}{\mathrm{e}}</math>. |
| # For all <math>i</math>, the value of <math>|H_i|</math> can be computed efficiently.
| |
| # It is possible to sample uniformly from each individual <math>H_i</math>.
| |
| # For any <math>x\in V</math>, it can be determined efficiently whether <math>x\in H_i</math>.
| |
| | |
| DNF counting can be easily put into this general framework: Suppose that the DNF formula is a disjunction (<math>\vee</math>) of <math>m</math> clauses <math>C_1,C_2,\ldots,C_m</math> on <math>n</math> variables, where each clause <math>C_i</math> is a conjunction (<math>\wedge</math>) of <math>k_i</math> literals. Without loss of generality, we may assume that in each clause, each variable appears at most once. The satisfying solutions to this DNF can be represented as a union of <math>m</math> sets as follows:
| |
| * <math>V=\{\text{true},\text{false}\}^n</math> is the set of all <math>2^n</math> truth assignments.
| |
| * Each <math>H_i=\{x\in\{\text{true},\text{false}\}^n\mid x\mbox{ satisfies }C_i\}</math> is the set of satisfying assignments for the <math>i</math>-th clause <math>C_i</math> of the DNF formula.
| |
| Then the union of sets <math>H=\bigcup_i H_i</math> gives the set of satisfying assignments for the DNF formula <math>C_1\vee C_2\vee\cdots \vee C_m</math>. Its size <math>|H|</math> gives the number of satisfying assignments for the DNF.
| |
| | |
| Furthermore, the three assumptions above can also be guaranteed in this construction:
| |
| # Since each clause <math>C_i</math> is a conjunction of <math>k_i</math> literals, it is easy to see that <math>|H_i|=2^{n-k_i}</math>, which is obviously efficiently computable.
| |
| # Sampling from each <math>H_i</math> is very easy: we just fix the assignments of the <math>k_i</math> variables involved in the corresponding clause <math>C_i</math> to satisfy <math>C_i</math> (there is exactly one such choice), and sample uniformly and independently the rest <math>(n-k_i)</math> variable assignments.
| |
| # For each assignment <math>x</math>, it is easy to check whether it satisfies a clause <math>C_i</math>, thus it is easy to determine whether <math>x\in H_i</math>.
| |
| | |
| ==The coverage algorithm==
| |
| We now introduce the coverage algorithm for the union of sets problem.
| |
| | |
| Consider the multiset <math>U</math> defined by
| |
| :<math>U=H_1\uplus H_2\uplus\cdots \uplus H_m</math>,
| |
| where <math>\uplus</math> denotes the multiset union. It is more convenient to define <math>U</math> as the set
| |
| :<math>U=\{(x,i)\mid x\in H_i\}</math>.
| |
| For each <math>x\in H</math>, there may be more than one instances of <math>(x,i)\in U</math>. We may choose the <math>(x,i)</math> with the minimum <math>i</math>, and collect all such <math>(x,i)</math> to form a set <math>G</math>.
| |
| | |
| Formally, the set <math>G</math> is defined as
| |
| :<math>G=\{(x,i)\in U\mid \forall (x,j)\in U, j\le i\}</math>.
| |
| Every <math>x\in H</math> corresponds to a unique <math>(x,i)\in G</math> where <math>i</math> is the smallest among <math>x\in H_i</math>.
| |
|
| |
|
| The following proposition is obvious
| | Assume the condition in the symmetric LLL: |
| {{Theorem|Proposition|
| | :#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>; |
| #<math>G\subseteq U</math>; | | :#<math>ep(d+1)\le 1</math>; |
| #<math>|G|=|H|\,</math>.
| | then it is easy to verify that for all <math>1\le i\le n</math>, |
| }} | | :<math>\Pr[A_i]\le p\le\frac{1}{e(d+1)}<\frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^d\le x_i\prod_{(i,j)\in E}(1-x_j)</math>. |
| | Due to the general LLL, we have |
| | :<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge\prod_{i=1}^n(1-x_i)=\left(1-\frac{1}{d+1}\right)^n>0</math>. |
| | This proves the symmetric LLL. |
|
| |
|
| Therefore, the estimation of the size of the union set <math>H\bigcup_{i=1}^mH_i</math> is reduced to the estimation of the size of the subset <math>G\subseteq U</math>, where <math>U</math> is the multiset union of <math>H_1, H_2,\ldots, H_m</math> and <math>H</math>. Note that now the fraction <math>\alpha=|G|/|U|</math> becomes large enough. As long as we can implement a uniform sampler for <math>U</math> and a membership oracle for <math>G</math>, we can apply the estimator theorem to get a good approximation algorithm for <math>|G|=|H|</math>.
| | Now we prove the general LLL by the original induction proof. |
| | |
| An uniform sample from <math>U</math> can be implemented as follows.
| |
| {{Theorem|Uniform sampler for <math>U</math>|
| |
| * generate an <math>i\in\{1,2,\ldots,m\}</math> with probability <math>\frac{|H_i|}{\sum_{i=1}^m|H_i|}</math>;
| |
| * uniformly sample an <math>x\in H_i</math>, and return <math>(x,i)</math>.
| |
| }}
| |
| It is easy to see that this gives a uniform member of <math>U</math>. And this uniform sampler is efficient as long as each <math>|H_i|</math> is efficiently computable and we have an efficient uniform sample for each <math>H_i</math>, both of which are assumed.
| |
| | |
| It is also easy to implement the membership oracle for <math>G</math>:
| |
| {{Theorem|Membership oracle for <math>G</math>|
| |
| upon each query <math>(x,i)</math>:
| |
| :if <math>i</math> is the smallest among all <math>j</math> that <math>x\in H_j</math>
| |
| :: return "yes";
| |
| :else return "no";
| |
| }}
| |
| By definition of <math>G</math>, it is easy to see this membership oracle works, and it is efficient if the membership of each <math>H_i</math> can be efficiently determined, which is also assumed.
| |
| | |
| We now only need to lower bound the fraction
| |
| :<math>\alpha=\frac{|G|}{|U|}</math>.
| |
| | |
| {{Theorem|Proposition|
| |
| :<math>\alpha\ge\frac{1}{m}</math>.
| |
| }}
| |
| {{Proof| | | {{Proof| |
| For every <math>x\in H</math>, there are at most <math>m</math> different pairs <math>(x,i)</math> in <math>U</math>, thus <math>|U|\le m|H|</math>. And we already know that <math>|G|=|H|</math>.
| | First, apply the chain rule. We have |
| }}
| | :<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=\prod_{i=1}^n\Pr\left[\overline{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]=\prod_{i=1}^n\left(1-\Pr\left[{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\right)</math>. |
| | |
| Applying the estimator theorem, this gives us an algorithm which returns an <math>\epsilon</math>-approximation of <math>|H|</math> with probability at least <math>1-\delta</math>, by making at most <math>\frac{4m}{\epsilon^2}\ln\frac{2}{\delta}</math> calls to the uniform random sampler for <math>U</math> and the membership oracle for <math>G</math>, due to the three efficiency assumptions, both of which can be efficiently implemented. The resulting algorithm is called the '''coverage algorithm'''.
| |
| | |
| Applying the coverage algorithm to the DNF counting, which as we have discussed above, is a special case for the union of set problem, we have an FPRAS.
| |
| {{Theorem|Theorem (Karp-Luby, 1983)| | |
| :There exists an FPRAS for the DNF counting problem.
| |
| }} | |
| | |
| = Count Matchings = | |
| Recall that a matching <math>M</math> in a graph <math>G(V,E)</math> is a subset <math>M\subseteq E</math> of edges such that no vertex in <math>V</math> is incident to more than one edges in <math>M</math>, i.e. a matching is an "edge-version" of independent set.
| |
| | |
| Let us consider a more complicated counting problem, counting the number matchings in an input graph. The problem is formally defined as follows.
| |
| :'''Input''': an indirected graph <math>G(V,E)</math>;
| |
| :'''Output''': <math>Z(G)=</math> number of matchings in <math>G</math>.
| |
| | |
| Note that we count all matchings, not just maximum or maximal matchings. For example, an empty set (containing no edge) is always a matching.
| |
| | |
| This problem is '''#P-complete'''. In fact, it is among the first few problems known to be '''#P-complete'''. The studies of the computational complexity and efficient approximation algorithms for this problem pioneer the fields of counting complexity and randomized algorithms.
| |
|
| |
|
| == A self-reduction procedure == | | Next we prove by induction on <math>m</math> that for any set of <math>m</math> events <math>i_1,\ldots,i_m</math>, |
| We show a generic self-reduction procedure due to Jerrum-Valiant-Vazirani, which reduces a counting problem to the problems of smaller instances. This technique does not just work for counting matchings, but may also work a wide range of counting version of CSPs (constraint satisfaction problem) who show self-reducibility property.
| | :<math>\Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]\le x_{i_1}</math>. |
| | The local lemma follows immediately by the above chain rule. |
|
| |
|
| Fix an input graph <math>G(V,E)</math>. Let <math>Z(G)</math> be the number of matchings in <math>G</math>.
| | For <math>m=1</math>, this is obvious because |
| | :<math>\Pr[A_{i_1}]\le x_{i_1}\prod_{(i_1,j)\in E}(1-x_j)\le x_{i_1}</math>. |
|
| |
|
| We consider the uniform probability distribution over all matchings in <math>G</math>. Let <math>X</math> be such a random matching sampled uniformly at random from all matchings in <math>G</math>. More formally, for any <math>M\subseteq E</math>,
| | For general <math>m</math>, let <math>i_2,\ldots,i_k</math> be the set of vertices adjacent to <math>i_1</math> in the dependency graph, i.e. event <math>A_{i_1}</math> is mutually independent of <math>A_{i_{k+1}},A_{i_{k+2}},\ldots, A_{i_{m}}</math>. |
| | By conditional probability, we have |
| :<math> | | :<math> |
| \Pr[X=M]= | | \Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right] |
| \begin{cases} | | =\frac{\Pr\left[ A_i\wedge \bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]} |
| \frac{1}{Z(G)} & \mbox{if }M\mbox{ is a matching in }G,\\ | | {\Pr\left[\bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]} |
| 0 & \mbox{otherwise.}\\
| | </math>. |
| \end{cases} | | First, we bound the numerator. Due to that <math>A_{i_1}</math> is mutually independent of <math>A_{i_{k+1}},A_{i_{k+2}},\ldots, A_{i_{m}}</math>, we have |
| </math> | |
| | |
| Consider the special matching <math>M=\emptyset</math>. It clearly holds that <math>\Pr[X=\emptyset]=\frac{1}{Z(G)}</math>, thus
| |
| :<math> | | :<math> |
| Z(G)=\frac{1}{\Pr[X=\emptyset]}.
| | \begin{align} |
| | \Pr\left[ A_{i_1}\wedge \bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right] |
| | &\le\Pr\left[ A_{i_1}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]\\ |
| | &=\Pr[A_{i_1}]\\ |
| | &\le x_{i_1}\prod_{(i_1,j)\in E}(1-x_j). |
| | \end{align} |
| </math> | | </math> |
| Thus we can estimate <math>Z(G)</math> by estimating the probability <math>\Pr[X=\emptyset]</math>.
| |
|
| |
| We denote <math>E=\{e_1,e_2,\ldots,e_m\}</math>, where the order of edges <math>e_1,e_2,\ldots,e_m</math> is arbitrary.
| |
|
| |
|
| {|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
| | Next, we bound the denominator. Applying the chain rule, we have |
| |
| |
| :The random matching <math>X</math> can be seen as a random vector <math>X=(X_1,X_2,\ldots,X_m)</math>, where each <math>X_i</math> indicates whether <math>e_i</math> appears in the random matching <math>X</math>.
| |
| Thus the probability <math>\Pr[X=\emptyset]</math> is usually called a '''''joint probability''''' of the random vector <math>X</math>.
| |
| The joint probability can be represented as a product of '''''marginal probabilities''''' by the chain rule.
| |
| :<math> | | :<math> |
| \Pr[X=(0,0,\ldots,0)] = \prod_{i=1}^m\Pr[X_i=0\mid \forall j<i,X_j=0]. | | \Pr\left[\bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right] |
| | =\prod_{j=2}^k\Pr\left[\overline{A_{i_j}}\mid \bigwedge_{\ell=j+1}^m\overline{A_{i_\ell}}\right] |
| </math> | | </math> |
| |}
| | which by the induction hypothesis, is at least |
| | |
| Back to the matching problem, note that the event <math>X=\emptyset</math> is equivalent to the event that <math>\forall i, e_i\not\in X</math>.
| |
| Due to the chain rule, we have
| |
| :<math> | | :<math> |
| \begin{align} | | \prod_{j=2}^k(1-x_{i_j})=\prod_{\{i_1,i_j\}\in E}(1-x_j) |
| \Pr[X=\emptyset]
| |
| &=
| |
| \Pr[\forall i, e_i\not\in X]\\
| |
| &=
| |
| \prod_{i=1}^m\Pr[e_i\not\in X\mid \forall j<i,e_i\not\in X]\\ | |
| &=
| |
| \prod_{i=1}^m(1-\Pr[e_i\in X\mid \forall j<i,e_i\not\in X]).
| |
| \end{align}
| |
| </math> | | </math> |
| | where <math>E</math> is the set of edges in the dependency graph. |
|
| |
|
| For a graph <math>G(V,E)</math> and an edge <math>e</math>, we use
| | Altogether, we prove the induction hypothesis |
| :<math> | | :<math> |
| P_G(e)=\Pr[e\in X]
| | \Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right] |
| | \le\frac{x_{i_1}\prod_{(i_1,j)\in E}(1-x_j)}{\prod_{\{i_1,i_j\}\in E}(1-x_j)}\le x_{i_1}. |
| </math> | | </math> |
| to denote the marginal probability of <math>e</math> being occupied by a uniformly random matching <math>X</math> in <math>G</math>.
| |
|
| |
| {{Theorem|Observation (self-reduction)|
| |
| :Let <math>G_i=G\setminus\{e_1,e_2,\ldots,e_{i-1}\}</math> be the subgraph of <math>G</math> obtained from removing the first <math>(i-1)</math> edges from <math>G</math>.
| |
| :It holds that
| |
| ::<math>P_{G_i}(e_i)=\Pr[e_i\in X\mid \forall j<i,e_i\not\in X]</math>
| |
| }}
| |
|
| |
|
| This observation can be easily proved by the following "telescopic product" version of the chain rule. Note that with the notation <math>G_i</math> we have <math>G_1=G</math> and <math>G_{m+1}=\emptyset</math> to be the empty graph.
| | Due to the chain rule, it holds that |
| :<math> | | :<math> |
| \begin{align} | | \begin{align} |
| \Pr[X=\emptyset] | | \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right] |
| &= | | &=\prod_{i=1}^n\Pr\left[\overline{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\\ |
| \frac{1}{Z(G)} | | &=\prod_{i=1}^n\left(1-\Pr\left[A_i\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\right)\\ |
| =
| | &\ge\prod_{i=1}^n\left(1-x_i\right). |
| \frac{Z(G_{m+1})}{Z(G_1)} | |
| = | |
| \prod_{i=1}^m\frac{Z(G_{i+1})}{Z(G_i)}. | |
| \end{align} | | \end{align} |
| </math> | | </math> |
| On the other hand, each term in the product is
| |
| :<math>\frac{Z(G_{i+1})}{Z(G_i)}=\frac{|\{\text{matchings formed by edges }e_{i+1},e_{e+2},\ldots,e_{m}\}|}{|\{\text{matchings formed by edges }e_i,e_{i+1},\ldots,e_{m}\}|}
| |
| =\Pr[e_i\not\in X\mid \forall j<i,e_j\not\in X].
| |
| </math>
| |
| So the above observation is proved.
| |
|
| |
| ==From counting to sampling ==
| |
| With the above observation and recalling that <math>Z(G)=\frac{1}{\Pr[X=\emptyset]}</math>, we have
| |
| :<math>
| |
| Z(G)=\frac{1}{\Pr[X=\emptyset]}=\prod_{i=1}^m\frac{1}{(1-P_{G_i}(e_i))}.
| |
| </math>
| |
|
| |
| The number of matchings in graph <math>G</math>, <math>Z(G)</math>, can be efficiently approximated if the marginal probabilities <math>P_{G_i}(e_i)</math> can be efficiently approximated, where the latter can be achieved by doing the statistical experiments by sampling uniform random matchings in graph <math>G_i</math>.
| |
|
| |
| This generic process is described in more details as follows:
| |
| # If we can sample a uniform (or ''almost uniform'', whose meaning to be specified later) random matching from any graph <math>G</math> in polynomial time, then due to the estimator theorem, we can have an '''<math>(\epsilon,\delta)</math>-estimator''' of each <math>P_{G_i}(e_i)</math>. This estimator runs in time polynomial in <math>n=|V|</math>, <math>\frac{1}{\epsilon}</math>, and <math>\log\frac{1}{\delta}</math>, and returns an estimation <math>\hat{P}_i</math> for each <math>P_{G_i}(e_i)</math> such that <math>|\hat{P}_i-P_{G_i}(e_i)|>\epsilon</math> holds with probability at most <math>\delta</math>.
| |
| # The above <math>(\epsilon,\delta)</math>-estimators are efficient approximations of marginal probabilities with small ''additive errors''. To get an FPRAS for <math>Z(G)</math>, whose error is multiplicative, we still need that each <math>P_{G_i}(e_i)</math> is bounded away from 1. i.e. there is a constant <math>c>0</math> such that it always holds that <math>P_{G_i}(e_i)\le 1-c</math>. For matching, this is always guaranteed. We have the following lemma.
| |
| {{Theorem|Lemma|
| |
| :For any graph <math>G</math> and edge <math>e</math>, it always holds that <math>P_G(e)\le \frac{1}{2}</math>.
| |
| }} | | }} |
| :This lemma holds for quite obvious reasons: If <math>e</math> is an isolated edge (with both endpoints of degree 1), then it is covered by an uniformly random matching <math>X</math> with probability exactly 1/2. And more edges sharing vertices with <math>e</math> can not increase this probability.
| |
|
| |
| With the above lemma, the task of designing a FPRAS for the number of matchings in an input graph is reduced to the task of uniformly sampling a matching in the input graph in polynomial time. In fact, precisely uniform sampling such complicated structure is quite difficult, but there are ways to ''almost uniform sampling'' matchings or other complicated structures in polynomial time. This is achieved by '''random walks''' in a very large but fast converging Markov chain.
| |