TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T06:38:40Z

172.16.65.101: /* Turán's theorem */

== Extremal Graph Theory ==

=== Mantel's theorem ===
We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n},
</math>
where the last equation is due to Euler's equality <math>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.

Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</math>.

Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>uv\not\in E</math> defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph <math>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T06:37:54Z

172.16.65.101: /* Turán's theorem */

== Extremal Graph Theory ==

=== Mantel's theorem ===
We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n},
</math>
where the last equation is due to Euler's equality <math>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.

Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</math>.

Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{r-1}\frac{n^2}{2}</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>uv\not\in E</math> defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph <math>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Existence, the probabilistic method

2010-09-13T05:12:41Z

172.16.65.101: /* Sampling */

== Counting arguments ==
;Circuit complexity

A '''boolean function''' is a function is the form <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , x_n</math>. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in '''P''' can be computed by a circuit with polynomially many gates. Thus, if we can find a function in '''NP''' that cannot be computed by any circuit with polynomially many gates, then '''NP'''<math>\neq</math>'''P'''.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

{{Theorem
|Theorem (Shannon 1949)|
:There is a boolean function <math>f:\{0,1\}^n\rightarrow \{0,1\}</math> with circuit complexity greater than <math>\frac{2^n}{3n}</math>.
}}
{{Proof|
We first count the number of boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. There are <math>2^{2^n}</math> boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Then we count the number of boolean circuit with fixed number of gates.
Fix an integer <math>t</math>, we count the number of circuits with <math>t</math> gates. By the [http://en.wikipedia.org/wiki/De_Morgan's_laws De Morgan's laws], we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable <math>x_i</math>, an inverted input variable <math>\neg x_i</math>, or the output of another gate; thus, there are at most <math>2+2n+t-1</math> possible gate inputs. It follows that the number of circuits with <math>t</math> gates is at most <math>2^t(t+2n+1)^{2t}</math>.

If <math>t=2^n/3n</math>, then
:<math>
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)<1,</math> thus, <math>2^t(t+2n+1)^{2t} < 2^{2^n}.</math>

Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function <math>f</math> which cannot be computed by any circuits with <math>2^n/3n</math> gates.
}}

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but ''almost all'' boolean functions have exponentially large circuit complexity.

=== Double counting ===
;Intersecting families;

An <math>\mathcal{F}\subseteq 2^S</math> is an '''intersecting''' family if for any <math>A,B\in\mathcal{F}</math> it holds that <math>A\cap B\neq\emptyset</math>.

Suppose that <math>n\ge 2k</math>. For <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math>, we can let all <math>A\in \mathcal{F}</math> contain one common element <math>a\in S</math> and <math>A-\{a\}</math> enumerates all <math>{n-1\choose k-1}</math> possible combinations of <math>(k-1)</math> elements in <math>S</math>. This gives us an intersecting family of size <math>|\mathcal{F}|={n-1\choose k-1}</math>.

The following theorem says that this is the largest possible cardinality an intersecting <math>\mathcal{F}</math> can achieve. The theorem was first proved by Erdős, Ko, and Rado in 1938, but published 23 years later. It is a fundamental result in the area of extremal set theory, which studies the maximum (or minimum) possible cardinality of a set system satisfying certain structural assumption. In this example, the structural assumption is intersecting.

Here we present a probabilistic proof by Katona.

{{Theorem
|Theorem (Erdős-Ko-Rado 1961)|
:Let <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is an intersecting family then <math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}
{{Proof| (due to Katona 1972).

Without loss of generality, let <math>S=[n]</math>.
For <math>i\in[n]</math>, let <math>A_i=\{(i+j)\bmod n\mid j\in[k]\}</math>. Then we make the following claim.

:'''Claim 1:''' <math>\mathcal{F}</math> can contain at most <math>k</math> many <math>A_i</math>.
The claim can be easily proved by observing that for any <math>i,j\in[n]</math> that <math>i<j</math>, <math>A_i</math> and <math>A_j</math> are disjoint if <math>j-i>k</math>, thus in order to make <math>\mathcal{F}</math> intersecting, all <math>A_i,A_j\in\mathcal{F}</math> have <math>|i-j|\le k</math>. This is violated once there are more than <math>k</math> many <math>A_i</math> in <math>\mathcal{F}</math>.

Now we prove the Erdős-Ko-Rado theorem. Let a permutation <math>\sigma</math> of <math>[n]</math> and an integer <math>i\in[n]</math> be chosen uniformly and independently at random. Let
:<math>R=\{\sigma((i+j)\bmod n)\mid j\in[k]\}, \quad\mbox{ or equivalently }R=\sigma(A_i)</math>.
By Claim 1, for any fixed permutation <math>\sigma</math>, the family <math>\mathcal{F}</math> can contain at most <math>k</math> of the sets <math>\sigma(A_i)</math>, thus conditioning on any particular <math>\sigma</math>, <math>\Pr[R\in\mathcal{F}\mid \sigma]\le\frac{k}{n}</math>. Hence
:<math>
\Pr[R\in\mathcal{F}]\le\frac{k}{n}.
</math>
On the other hand, by our construction, <math>R</math> is uniformly chosen from <math>{S\choose k}</math>, thus
:<math>
\Pr[R\in\mathcal{F}]=\frac{|\mathcal{F}|}{{n\choose k}}.
</math>
Therefore,
<math>
|\mathcal{F}|\le\frac{k}{n}{n\choose k}={n-1\choose k-1}.
</math>
}}

=== The averaging principle ===

== The Pigeonhole Principle ==

== The Probabilistic Method ==

Suppose we want prove the existence of mathematic objects with certain properties. One way to do so is to explicitly construct such an object. This kind of proofs can be interpreted as ''deterministic algorithms'' which find the object with desirable properties.

The probabilistic method provides another way of proving the existence of objects: instead of explicitly constructing an object, we define a probability space of objects in which the probability is positive that a randomly selected object has the required property.

The basic principle of the probabilistic method is very simple, and can be stated in intuitive ways:
*If an object chosen randomly from a universe satisfies a property with positive probability, then there must be an object in the universe that satisfies that property.
:For example, for a ball(the object) randomly chosen from a box(the universe) of balls, if the probability that the chosen ball is blue(the property) is >0, then there must be a blue ball in the box.
*Any random variable assumes at least one value that is no smaller than its expectation, and at least one value that is no greater than the expectation.
:For example, if we know the average height of the students in the class is <math>\ell</math>, then we know there is a students whose height is at least <math>\ell</math>, and there is a student whose height is at most <math>\ell</math>.

Although the idea of the probabilistic method is simple, it provides us a powerful tool for existential proof. In same cases, the proof itself is a ''randomized algorithm'', and if we are lucky, the algorithm could be very efficient.

=== Sampling ===
;Ramsey number

Recall the Ramsey theorem which states that in a meeting of at least six people, there are either three people knowing each other or three people not knowing each other. In graph theoretical terms, this means that no matter how we color the edges of <math>K_6</math> (the complete graph on six vertices), there must be a '''monochromatic''' <math>K_3</math> (a triangle whose edges have the same color).

Generally, the '''Ramsey number''' <math>R(k,\ell)</math> is the smallest integer <math>n</math> such that in any two-coloring of the edges of a complete graph on <math>n</math> vertices <math>K_n</math> by red and blue, either there is a red <math>K_k</math> or there is a blue <math>K_\ell</math>.

Ramsey showed in 1929 that <math>R(k,\ell)</math> is finite for any <math>k</math> and <math>\ell</math>. It is extremely hard to compute the exact value of <math>R(k,\ell)</math>. Here we give a lower bound of <math>R(k,k)</math> by the probabilistic method.

{{Theorem
|Theorem (Erdős 1947)|
:If <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math> then it is possible to color the edges of <math>K_n</math> with two colors so that there is no monochromatic <math>K_k</math> subgraph.
}}
{{Proof| Consider a random two-coloring of edges of <math>K_n</math> obtained as follows:
* For each edge of <math>K_n</math>, independently flip a fair coin to decide the color of the edge.

For any fixed set <math>S</math> of <math>k</math> vertices, let <math>\mathcal{E}_S</math> be the event that the <math>K_k</math> subgraph induced by <math>S</math> is monochromatic. There are <math>{k\choose 2}</math> many edges in <math>K_k</math>, therefore
:<math>\Pr[\mathcal{E}_S]=2\cdot 2^{-{k\choose 2}}=2^{1-{k\choose 2}}.</math>

Since there are <math>{n\choose k}</math> possible choices of <math>S</math>, by the union bound
:<math>
\Pr[\exists S, \mathcal{E}_S]\le {n\choose k}\cdot\Pr[\mathcal{E}_S]={n\choose k}\cdot 2^{1-{k\choose 2}}.
</math>
Due to the assumption, <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math>, thus there exists a two coloring that none of <math>\mathcal{E}_S</math> occurs, which means there is no monochromatic <math>K_k</math> subgraph.
}}

For <math>k\ge 3</math> and we take <math>n=\lfloor2^{k/2}\rfloor</math>, then
:<math>
\begin{align}
{n\choose k}\cdot 2^{1-{k\choose 2}}
&<
\frac{n^k}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&\le
\frac{2^{k^2/2}}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&=
\frac{2^{1+\frac{k}{2}}}{k!}\\
&<1.
\end{align}
</math>
By the above theorem, there exists a two-coloring of <math>K_n</math> that there is no monochromatic <math>K_k</math>. Therefore, the Ramsey number <math>R(k,k)>\lfloor2^{k/2}\rfloor</math> for all <math>k\ge 3</math>.

Note that for sufficiently large <math>k</math>, if <math>n= \lfloor 2^{k/2}\rfloor</math>, then the probability that there exists a monochromatic <math>K_k</math> is bounded by
:<math>
{n\choose k}\cdot 2^{1-{k\choose 2}}
<
\frac{2^{1+\frac{k}{2}}}{k!}
\ll 1,
</math>
which means that a random two-coloring of <math>K_n</math> is very likely not to contain a monochromatic <math>K_{2\log n}</math>. This gives us a very simple randomized algorithm for finding a two-coloring of <math>K_n</math> without monochromatic <math>K_{2\log n}</math>.

=== Linearity of expectation ===

;Maximum cut

Given an undirected graph <math>G(V,E)</math>, a set <math>C</math> of edges of <math>G</math> is called a '''cut''' if <math>G</math> is disconnected after removing the edges in <math>C</math>. We can represent a cut by <math>c(S,T)</math> where <math>(S,T)</math> is a bipartition of the vertex set <math>V</math>, and <math>c(S,T)=\{uv\in E\mid u\in S,v\in T\}</math> is the set of edges crossing between <math>S</math> and <math>T</math>.

We have seen how to compute min-cut: either by deterministic max-flow algorithm, or by Karger's randomized algorithm. On the other hand, max-cut is hard to compute, because it is '''NP-complete'''. Actually, the weighted version of max-cut is among the [http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems Karp's 21 NP-complete problems].

We now show by the probabilistic method that a max-cut always has at least half the edges.

{{Theorem
|Theorem|
:Given an undirected graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges, there is a cut of size at least <math>\frac{m}{2}</math>.
}}
{{Proof| Enumerate the vertices in an arbitrary order. Partition the vertex set <math>V</math> into two disjoint sets <math>S</math> and <math>T</math> as follows.
:For each vertex <math>v\in V</math>,
:* independently choose one of <math>S</math> and <math>T</math> with equal probability, and let <math>v</math> join the chosen set.

For each vertex <math>v\in V</math>, let <math>X_v\in\{S,T\}</math> be the random variable which represents the set that <math>v</math> joins. For each edge <math>uv\in E</math>, let <math>Y_{uv}</math> be the 0-1 random variable which indicates whether <math>uv</math> crosses between <math>S</math> and <math>T</math>. Clearly,
:<math>
\Pr[Y_{uv}=1]=\Pr[X_u\neq X_v]=\frac{1}{2}.
</math>

The size of <math>c(S,T)</math> is given by <math>Y=\sum_{uv\in E}Y_{uv}</math>. By the linearity of expectation,
:<math>
\mathbf{E}[Y]=\sum_{uv\in E}\mathbf{E}[Y_{uv}]=\sum_{uv\in E}\Pr[Y_{uv}=1]=\frac{m}{2}.
</math>
Therefore, there exist a bipartition <math>(S,T)</math> of <math>V</math> such that <math>|c(S,T)|\ge\frac{m}{2}</math>, i.e. there exists a cut of <math>G</math> which contains at least <math>\frac{m}{2}</math> edges.
}}

;Maximum satisfiability

Suppose that we have a number of boolean variables <math>x_1,x_2,\ldots,\in\{\mathrm{true},\mathrm{false}\}</math>. A '''literal''' is either a variable <math>x_i</math> itself or its negation <math>\neg x_i</math>. A logic expression is a '''conjunctive normal form (CNF)''' if it is written as the conjunction(AND) of a set of '''clauses''', where each clause is a disjunction(OR) of literals. For example:
:<math>
(x_1\vee \neg x_2 \vee \neg x_3)\wedge (\neg x_1\vee \neg x_3)\wedge (x_1\vee x_2\vee x_4)\wedge (x_4\vee \neg x_3)\wedge (x_4\vee \neg x_1).
</math>

The satisfiability (SAT) problem ask whether the CNF is satisfiable, i.e. there exists an assignment of variables to the values of true and false so that all clauses are true. The maximum satisfiability (MAXSAT) is the optimization version of SAT, which ask for an assignment that the number of satisfied clauses is maximized.

SAT is the first problem known to be '''NP-complete''' (the Cook-Levin theorem). MAXSAT is also '''NP-complete'''. We then see that there always exists a roughly good truth assignment which satisfies half the clauses.

{{Theorem
|Theorem|
:For any set of <math>m</math> clauses, there is a truth assignment that satisfies at least <math>\frac{m}{2}</math> clauses.
}}
{{Proof| For each variable, independently assign a random value in <math>\{\mathrm{true},\mathrm{false}\}</math> with equal probability. For the <math>i</math>th clause, let <math>X_i</math> be the random variable which indicates whether the <math>i</math>th clause is satisfied. Suppose that there are <math>k</math> literals in the clause. The probability that the clause is satisfied is
:<math>\Pr[X_k=1]\ge(1-2^{-k})\ge\frac{1}{2}</math>.

Let <math>X=\sum_{i=1}^m X_i</math> be the number of satisfied clauses. By the linearity of expectation,
:<math>
\mathbf{E}[X]=\sum_{i=1}^{m}\mathbf{E}[X_i]\ge \frac{m}{2}.
</math>
Therefore, there exists an assignment such that at least <math>\frac{m}{2}</math> clauses are satisfied.
}}

=== Alterations ===
;Independent sets
An independent set of a graph is a set of vertices with no edges between them. The following theorem gives a lower bound on the size of the largest independent set.
{{Theorem
|Theorem|
:Let <math>G(V,E)</math> be a graph on <math>n</math> vertices with <math>m</math> edges. Then <math>G</math> has an independent set with at least <math>\frac{n^2}{4m}</math> vertices.
}}
{{Proof| Let <math>S</math> be a set of vertices constructed as follows:
:For each vertex <math>v\in V</math>:
:* <math>v</math> is included in <math>S</math> independently with probability <math>p</math>,
<math>p</math> to be determined.

Let <math>X=|S|</math>. It is obvious that <math>\mathbf{E}[X]=np</math>.

For each edge <math>e\in E</math>, let <math>Y_{e}</math> be the random variable which indicates whether both endpoints of <math></math> are in <math>S</math>.
:<math>
\mathbf{E}[Y_{uv}]=\Pr[u\in S\wedge v\in S]=p^2.
</math>
Let <math>Y</math> be the number of edges in the subgraph of <math>G</math> induced by <math>S</math>. It holds that <math>Y=\sum_{e\in E}Y_e</math>. By linearity of expectation,
:<math>\mathbf{E}[Y]=\sum_{e\in E}\mathbf{E}[Y_e]=mp^2</math>.

Note that although <math>S</math> is not necessary an independent set, it can be modified to one if for each edge <math>e</math> of the induced subgraph <math>G(S)</math>, we delete one of the endpoint of <math>e</math> from <math>S</math>. Let <math>S^*</math> be the resulting set. It is obvious that <math>S^*</math> is an independent set since there is no edge left in the induced subgraph <math>G(S^*)</math>.

Since there are <math>Y</math> edges in <math>G(S)</math>, there are at most <math>Y</math> vertices in <math>S</math> are deleted to make it become <math>S^*</math>. Therefore, <math>|S^*|\ge X-Y</math>. By linearity of expectation,
:<math>
\mathbf{E}[|S^*|]\ge\mathbf{E}[X-Y]=\mathbf{E}[X]-\mathbf{E}[Y]=np-mp^2.
</math>
The expectation is maximized when <math>p=\frac{n}{2m}</math>, thus
:<math>
\mathbf{E}[|S^*|]\ge n\cdot\frac{n}{2m}-m\left(\frac{n}{2m}\right)^2=\frac{n^2}{4m}.
</math>
There exists an independent set which contains at least <math>\frac{n^2}{4m}</math> vertices.
}}

The proof actually propose a randomized algorithm for constructing large independent set:

{{Theorem
|Algorithm|
Given a graph on <math>n</math> vertices with <math>m</math> edges, let <math>d=\frac{2m}{n}</math> be the average degree.
#For each vertex <math>v\in V</math>, <math>v</math> is included in <math>S</math> independently with probability <math>\frac{1}{d}</math>.
#For each remaining edge in the induced subgraph <math>G(S)</math>, remove one of the endpoints from <math>S</math>.
}}

Let <math>S^*</math> be the resulting set. We have shown that <math>S^*</math> is an independent set and <math>\mathbf{E}[|S^*|]\ge\frac{n^2}{4m}</math>.

Combinatorics (Fall 2010)/Existence, the probabilistic method

2010-09-13T05:11:08Z

172.16.65.101: /* The Lovász Local Lemma */

== Counting arguments ==
;Circuit complexity

A '''boolean function''' is a function is the form <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , x_n</math>. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in '''P''' can be computed by a circuit with polynomially many gates. Thus, if we can find a function in '''NP''' that cannot be computed by any circuit with polynomially many gates, then '''NP'''<math>\neq</math>'''P'''.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

{{Theorem
|Theorem (Shannon 1949)|
:There is a boolean function <math>f:\{0,1\}^n\rightarrow \{0,1\}</math> with circuit complexity greater than <math>\frac{2^n}{3n}</math>.
}}
{{Proof|
We first count the number of boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. There are <math>2^{2^n}</math> boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Then we count the number of boolean circuit with fixed number of gates.
Fix an integer <math>t</math>, we count the number of circuits with <math>t</math> gates. By the [http://en.wikipedia.org/wiki/De_Morgan's_laws De Morgan's laws], we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable <math>x_i</math>, an inverted input variable <math>\neg x_i</math>, or the output of another gate; thus, there are at most <math>2+2n+t-1</math> possible gate inputs. It follows that the number of circuits with <math>t</math> gates is at most <math>2^t(t+2n+1)^{2t}</math>.

If <math>t=2^n/3n</math>, then
:<math>
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)<1,</math> thus, <math>2^t(t+2n+1)^{2t} < 2^{2^n}.</math>

Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function <math>f</math> which cannot be computed by any circuits with <math>2^n/3n</math> gates.
}}

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but ''almost all'' boolean functions have exponentially large circuit complexity.

=== Double counting ===
;Intersecting families;

An <math>\mathcal{F}\subseteq 2^S</math> is an '''intersecting''' family if for any <math>A,B\in\mathcal{F}</math> it holds that <math>A\cap B\neq\emptyset</math>.

Suppose that <math>n\ge 2k</math>. For <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math>, we can let all <math>A\in \mathcal{F}</math> contain one common element <math>a\in S</math> and <math>A-\{a\}</math> enumerates all <math>{n-1\choose k-1}</math> possible combinations of <math>(k-1)</math> elements in <math>S</math>. This gives us an intersecting family of size <math>|\mathcal{F}|={n-1\choose k-1}</math>.

The following theorem says that this is the largest possible cardinality an intersecting <math>\mathcal{F}</math> can achieve. The theorem was first proved by Erdős, Ko, and Rado in 1938, but published 23 years later. It is a fundamental result in the area of extremal set theory, which studies the maximum (or minimum) possible cardinality of a set system satisfying certain structural assumption. In this example, the structural assumption is intersecting.

Here we present a probabilistic proof by Katona.

{{Theorem
|Theorem (Erdős-Ko-Rado 1961)|
:Let <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is an intersecting family then <math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}
{{Proof| (due to Katona 1972).

Without loss of generality, let <math>S=[n]</math>.
For <math>i\in[n]</math>, let <math>A_i=\{(i+j)\bmod n\mid j\in[k]\}</math>. Then we make the following claim.

:'''Claim 1:''' <math>\mathcal{F}</math> can contain at most <math>k</math> many <math>A_i</math>.
The claim can be easily proved by observing that for any <math>i,j\in[n]</math> that <math>i<j</math>, <math>A_i</math> and <math>A_j</math> are disjoint if <math>j-i>k</math>, thus in order to make <math>\mathcal{F}</math> intersecting, all <math>A_i,A_j\in\mathcal{F}</math> have <math>|i-j|\le k</math>. This is violated once there are more than <math>k</math> many <math>A_i</math> in <math>\mathcal{F}</math>.

Now we prove the Erdős-Ko-Rado theorem. Let a permutation <math>\sigma</math> of <math>[n]</math> and an integer <math>i\in[n]</math> be chosen uniformly and independently at random. Let
:<math>R=\{\sigma((i+j)\bmod n)\mid j\in[k]\}, \quad\mbox{ or equivalently }R=\sigma(A_i)</math>.
By Claim 1, for any fixed permutation <math>\sigma</math>, the family <math>\mathcal{F}</math> can contain at most <math>k</math> of the sets <math>\sigma(A_i)</math>, thus conditioning on any particular <math>\sigma</math>, <math>\Pr[R\in\mathcal{F}\mid \sigma]\le\frac{k}{n}</math>. Hence
:<math>
\Pr[R\in\mathcal{F}]\le\frac{k}{n}.
</math>
On the other hand, by our construction, <math>R</math> is uniformly chosen from <math>{S\choose k}</math>, thus
:<math>
\Pr[R\in\mathcal{F}]=\frac{|\mathcal{F}|}{{n\choose k}}.
</math>
Therefore,
<math>
|\mathcal{F}|\le\frac{k}{n}{n\choose k}={n-1\choose k-1}.
</math>
}}

=== The averaging principle ===

== The Pigeonhole Principle ==

== The Probabilistic Method ==

Suppose we want prove the existence of mathematic objects with certain properties. One way to do so is to explicitly construct such an object. This kind of proofs can be interpreted as ''deterministic algorithms'' which find the object with desirable properties.

The probabilistic method provides another way of proving the existence of objects: instead of explicitly constructing an object, we define a probability space of objects in which the probability is positive that a randomly selected object has the required property.

The basic principle of the probabilistic method is very simple, and can be stated in intuitive ways:
*If an object chosen randomly from a universe satisfies a property with positive probability, then there must be an object in the universe that satisfies that property.
:For example, for a ball(the object) randomly chosen from a box(the universe) of balls, if the probability that the chosen ball is blue(the property) is >0, then there must be a blue ball in the box.
*Any random variable assumes at least one value that is no smaller than its expectation, and at least one value that is no greater than the expectation.
:For example, if we know the average height of the students in the class is <math>\ell</math>, then we know there is a students whose height is at least <math>\ell</math>, and there is a student whose height is at most <math>\ell</math>.

Although the idea of the probabilistic method is simple, it provides us a powerful tool for existential proof. In same cases, the proof itself is a ''randomized algorithm'', and if we are lucky, the algorithm could be very efficient.

=== Sampling ===
;Ramsey number

Recall the Ramsey theorem which states that in a meeting of at least six people, there are either three people knowing each other or three people not knowing each other. In graph theoretical terms, this means that no matter how we color the edges of <math>K_6</math> (the complete graph on six vertices), there must be a '''monochromatic''' <math>K_3</math> (a triangle whose edges have the same color).

Generally, the '''Ramsey number''' <math>R(k,\ell)</math> is the smallest integer <math>n</math> such that in any two-coloring of the edges of a complete graph on <math>n</math> vertices <math>K_n</math> by red and blue, either there is a red <math>K_k</math> or there is a blue <math>K_\ell</math>.

Ramsey showed in 1929 that <math>R(k,\ell)</math> is finite for any <math>k</math> and <math>\ell</math>. It is extremely hard to compute the exact value of <math>R(k,\ell)</math>. Here we give a lower bound of <math>R(k,k)</math> by the probabilistic method.

{{Theorem
|Theorem (Erdős 1947)|
:If <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math> then it is possible to color the edges of <math>K_n</math> with two colors so that there is no monochromatic <math>K_k</math> subgraph.
}}
{{Proof| Consider a random two-coloring of edges of <math>K_n</math> obtained as follows:
* For each edge of <math>K_n</math>, independently flip a fair coin to decide the color of the edge.

For any fixed set <math>S</math> of <math>k</math> vertices, let <math>\mathcal{E}_S</math> be the event that the <math>K_k</math> subgraph induced by <math>S</math> is monochromatic. There are <math>{k\choose 2}</math> many edges in <math>K_k</math>, therefore
:<math>\Pr[\mathcal{E}_S]=2\cdot 2^{-{k\choose 2}}=2^{1-{k\choose 2}}.</math>

Since there are <math>{n\choose k}</math> possible choices of <math>S</math>, by the union bound
:<math>
\Pr[\exists S, \mathcal{E}_S]\le {n\choose k}\cdot\Pr[\mathcal{E}_S]={n\choose k}\cdot 2^{1-{k\choose 2}}.
</math>
Due to the assumption, <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math>, thus there exists a two coloring that none of <math>\mathcal{E}_S</math> occurs, which means there is no monochromatic <math>K_k</math> subgraph.
}}

For <math>k\ge 3</math> and we take <math>n=\lfloor2^{k/2}\rfloor</math>, then
:<math>
\begin{align}
{n\choose k}\cdot 2^{1-{k\choose 2}}
&<
\frac{n^k}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&\le
\frac{2^{k^2/2}}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&=
\frac{2^{1+\frac{k}{2}}}{k!}\\
&<1.
\end{align}
</math>
By the above theorem, there exists a two-coloring of <math>K_n</math> that there is no monochromatic <math>K_k</math>. Therefore, the Ramsey number <math>R(k,k)>\lfloor2^{k/2}\rfloor</math> for all <math>k\ge 3</math>.

Note that for sufficiently large <math>k</math>, if <math>n= \lfloor 2^{k/2}\rfloor</math>, then the probability that there exists a monochromatic <math>K_k</math> is bounded by
:<math>
{n\choose k}\cdot 2^{1-{k\choose 2}}
<
\frac{2^{1+\frac{k}{2}}}{k!}
\ll 1,
</math>
which means that a random two-coloring of <math>K_n</math> is very likely not to contain a monochromatic <math>K_{2\log n}</math>. This gives us a very simple randomized algorithm for finding a two-coloring of <math>K_n</math> without monochromatic <math>K_{2\log n}</math>.

;Blocking number
Let <math>S</math> be a set. Let <math>2^{S}=\{A\mid A\subseteq S\}</math> be the power set of <math>S</math>, and let <math>{S\choose k}=\{A\mid A\subseteq S\mbox{ and }|A|=k\}</math> be the '''<math>k</math>-uniform''' of <math>S</math>.

We call <math>\mathcal{F}</math> a '''set family''' (or a '''set system''') with '''ground set''' <math>S</math> if <math>\mathcal{F}\subseteq 2^{S}</math>. The members of <math>\mathcal{F}</math> are subsets of <math>S</math>.

Given a set family <math>\mathcal{F}</math> with ground set <math>S</math>,
a set <math>T\subseteq S</math> is a '''blocking set''' of <math>\mathcal{F}</math> if all <math>A\in\mathcal{F}</math> have <math>A\cap T\neq \emptyset</math>, i.e. <math>T</math> intersects (blocks) all member set of <math>\mathcal{F}</math>.

{{Theorem
|Theorem|
:Given a set family <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>m=|\mathcal{F}|</math> and <math>n=|S|</math>, <math>\mathcal{F}</math> has a blocking set of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math>.
}}
{{Proof| Let <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>. Let <math>T</math> be a set chosen uniformly at random from <math>{S\choose \tau}</math>. We show that <math>T</math> is a blocking set of <math>\mathcal{F}</math> with a probability >0.

Fix any <math>A\in\mathcal{F}</math>. Recall that <math>\mathcal{F}\subseteq{S\choose k}</math>, thus <math>|A|=k</math>. And
:<math>
\begin{align}
\Pr[A\cap T=\emptyset]
&=
\frac{\left|{S-A\choose \tau}\right|}{\left|{S\choose \tau}\right|}\\
&=
\frac{{n-k\choose \tau}}{{n\choose\tau}}\\
&=
\frac{(n-k)\cdot(n-k-1)\cdots(n-k-\tau+1)}{n\cdot(n-1)\cdots(n-\tau+1)}\\
&<
\left(1-\frac{k}{n}\right)^{\tau}\\
&\le
\exp\left(-\frac{k\tau}{n}\right)\\
&\le
\frac{1}{m}.
\end{align}
</math>
By the union bound, the probability that there exists an <math>A\in\mathcal{F}</math> that misses <math>T</math>
:<math>
\Pr[\exists A\in\mathcal{F}, A\cap T=\emptyset]\le m\Pr[A\cap T=\emptyset]<m\cdot\frac{1}{m}=1.
</math>
Thus, the probability that <math>T</math> is a blocking set
:<math>
\Pr[\forall A\in\mathcal{F}, A\cap T\neq\emptyset]>0.
</math>
There exists a blocking set of size <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>.
}}

The theorem also hints us to a randomized algorithm. In order to make the algorithm efficient, we relax the size of <math>T</math> to <math>\tau=\frac{2n\ln m}{k}</math>. Uniformly choose <math>\tau</math> elements from <math>S</math> to form the set <math>T</math>, by the above analysis, the probability that <math>T</math> is NOT a blocking set is at most
:<math>
m\exp\left(-\frac{n\tau}{k}\right)=m\exp(-2\ln m)=\frac{1}{m}.
</math>
Thus, a blocking set is found with high probability.

=== Linearity of expectation ===

;Maximum cut

Given an undirected graph <math>G(V,E)</math>, a set <math>C</math> of edges of <math>G</math> is called a '''cut''' if <math>G</math> is disconnected after removing the edges in <math>C</math>. We can represent a cut by <math>c(S,T)</math> where <math>(S,T)</math> is a bipartition of the vertex set <math>V</math>, and <math>c(S,T)=\{uv\in E\mid u\in S,v\in T\}</math> is the set of edges crossing between <math>S</math> and <math>T</math>.

We have seen how to compute min-cut: either by deterministic max-flow algorithm, or by Karger's randomized algorithm. On the other hand, max-cut is hard to compute, because it is '''NP-complete'''. Actually, the weighted version of max-cut is among the [http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems Karp's 21 NP-complete problems].

We now show by the probabilistic method that a max-cut always has at least half the edges.

{{Theorem
|Theorem|
:Given an undirected graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges, there is a cut of size at least <math>\frac{m}{2}</math>.
}}
{{Proof| Enumerate the vertices in an arbitrary order. Partition the vertex set <math>V</math> into two disjoint sets <math>S</math> and <math>T</math> as follows.
:For each vertex <math>v\in V</math>,
:* independently choose one of <math>S</math> and <math>T</math> with equal probability, and let <math>v</math> join the chosen set.

For each vertex <math>v\in V</math>, let <math>X_v\in\{S,T\}</math> be the random variable which represents the set that <math>v</math> joins. For each edge <math>uv\in E</math>, let <math>Y_{uv}</math> be the 0-1 random variable which indicates whether <math>uv</math> crosses between <math>S</math> and <math>T</math>. Clearly,
:<math>
\Pr[Y_{uv}=1]=\Pr[X_u\neq X_v]=\frac{1}{2}.
</math>

The size of <math>c(S,T)</math> is given by <math>Y=\sum_{uv\in E}Y_{uv}</math>. By the linearity of expectation,
:<math>
\mathbf{E}[Y]=\sum_{uv\in E}\mathbf{E}[Y_{uv}]=\sum_{uv\in E}\Pr[Y_{uv}=1]=\frac{m}{2}.
</math>
Therefore, there exist a bipartition <math>(S,T)</math> of <math>V</math> such that <math>|c(S,T)|\ge\frac{m}{2}</math>, i.e. there exists a cut of <math>G</math> which contains at least <math>\frac{m}{2}</math> edges.
}}

;Maximum satisfiability

Suppose that we have a number of boolean variables <math>x_1,x_2,\ldots,\in\{\mathrm{true},\mathrm{false}\}</math>. A '''literal''' is either a variable <math>x_i</math> itself or its negation <math>\neg x_i</math>. A logic expression is a '''conjunctive normal form (CNF)''' if it is written as the conjunction(AND) of a set of '''clauses''', where each clause is a disjunction(OR) of literals. For example:
:<math>
(x_1\vee \neg x_2 \vee \neg x_3)\wedge (\neg x_1\vee \neg x_3)\wedge (x_1\vee x_2\vee x_4)\wedge (x_4\vee \neg x_3)\wedge (x_4\vee \neg x_1).
</math>

The satisfiability (SAT) problem ask whether the CNF is satisfiable, i.e. there exists an assignment of variables to the values of true and false so that all clauses are true. The maximum satisfiability (MAXSAT) is the optimization version of SAT, which ask for an assignment that the number of satisfied clauses is maximized.

SAT is the first problem known to be '''NP-complete''' (the Cook-Levin theorem). MAXSAT is also '''NP-complete'''. We then see that there always exists a roughly good truth assignment which satisfies half the clauses.

{{Theorem
|Theorem|
:For any set of <math>m</math> clauses, there is a truth assignment that satisfies at least <math>\frac{m}{2}</math> clauses.
}}
{{Proof| For each variable, independently assign a random value in <math>\{\mathrm{true},\mathrm{false}\}</math> with equal probability. For the <math>i</math>th clause, let <math>X_i</math> be the random variable which indicates whether the <math>i</math>th clause is satisfied. Suppose that there are <math>k</math> literals in the clause. The probability that the clause is satisfied is
:<math>\Pr[X_k=1]\ge(1-2^{-k})\ge\frac{1}{2}</math>.

Let <math>X=\sum_{i=1}^m X_i</math> be the number of satisfied clauses. By the linearity of expectation,
:<math>
\mathbf{E}[X]=\sum_{i=1}^{m}\mathbf{E}[X_i]\ge \frac{m}{2}.
</math>
Therefore, there exists an assignment such that at least <math>\frac{m}{2}</math> clauses are satisfied.
}}

=== Alterations ===
;Independent sets
An independent set of a graph is a set of vertices with no edges between them. The following theorem gives a lower bound on the size of the largest independent set.
{{Theorem
|Theorem|
:Let <math>G(V,E)</math> be a graph on <math>n</math> vertices with <math>m</math> edges. Then <math>G</math> has an independent set with at least <math>\frac{n^2}{4m}</math> vertices.
}}
{{Proof| Let <math>S</math> be a set of vertices constructed as follows:
:For each vertex <math>v\in V</math>:
:* <math>v</math> is included in <math>S</math> independently with probability <math>p</math>,
<math>p</math> to be determined.

Let <math>X=|S|</math>. It is obvious that <math>\mathbf{E}[X]=np</math>.

For each edge <math>e\in E</math>, let <math>Y_{e}</math> be the random variable which indicates whether both endpoints of <math></math> are in <math>S</math>.
:<math>
\mathbf{E}[Y_{uv}]=\Pr[u\in S\wedge v\in S]=p^2.
</math>
Let <math>Y</math> be the number of edges in the subgraph of <math>G</math> induced by <math>S</math>. It holds that <math>Y=\sum_{e\in E}Y_e</math>. By linearity of expectation,
:<math>\mathbf{E}[Y]=\sum_{e\in E}\mathbf{E}[Y_e]=mp^2</math>.

Note that although <math>S</math> is not necessary an independent set, it can be modified to one if for each edge <math>e</math> of the induced subgraph <math>G(S)</math>, we delete one of the endpoint of <math>e</math> from <math>S</math>. Let <math>S^*</math> be the resulting set. It is obvious that <math>S^*</math> is an independent set since there is no edge left in the induced subgraph <math>G(S^*)</math>.

Since there are <math>Y</math> edges in <math>G(S)</math>, there are at most <math>Y</math> vertices in <math>S</math> are deleted to make it become <math>S^*</math>. Therefore, <math>|S^*|\ge X-Y</math>. By linearity of expectation,
:<math>
\mathbf{E}[|S^*|]\ge\mathbf{E}[X-Y]=\mathbf{E}[X]-\mathbf{E}[Y]=np-mp^2.
</math>
The expectation is maximized when <math>p=\frac{n}{2m}</math>, thus
:<math>
\mathbf{E}[|S^*|]\ge n\cdot\frac{n}{2m}-m\left(\frac{n}{2m}\right)^2=\frac{n^2}{4m}.
</math>
There exists an independent set which contains at least <math>\frac{n^2}{4m}</math> vertices.
}}

The proof actually propose a randomized algorithm for constructing large independent set:

{{Theorem
|Algorithm|
Given a graph on <math>n</math> vertices with <math>m</math> edges, let <math>d=\frac{2m}{n}</math> be the average degree.
#For each vertex <math>v\in V</math>, <math>v</math> is included in <math>S</math> independently with probability <math>\frac{1}{d}</math>.
#For each remaining edge in the induced subgraph <math>G(S)</math>, remove one of the endpoints from <math>S</math>.
}}

Let <math>S^*</math> be the resulting set. We have shown that <math>S^*</math> is an independent set and <math>\mathbf{E}[|S^*|]\ge\frac{n^2}{4m}</math>.

Combinatorics (Fall 2010)/Existence, the probabilistic method

2010-09-13T05:06:18Z

172.16.65.101: /* The Probabilistic Method */

== Counting arguments ==
;Circuit complexity

A '''boolean function''' is a function is the form <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , x_n</math>. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in '''P''' can be computed by a circuit with polynomially many gates. Thus, if we can find a function in '''NP''' that cannot be computed by any circuit with polynomially many gates, then '''NP'''<math>\neq</math>'''P'''.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

{{Theorem
|Theorem (Shannon 1949)|
:There is a boolean function <math>f:\{0,1\}^n\rightarrow \{0,1\}</math> with circuit complexity greater than <math>\frac{2^n}{3n}</math>.
}}
{{Proof|
We first count the number of boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. There are <math>2^{2^n}</math> boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Then we count the number of boolean circuit with fixed number of gates.
Fix an integer <math>t</math>, we count the number of circuits with <math>t</math> gates. By the [http://en.wikipedia.org/wiki/De_Morgan's_laws De Morgan's laws], we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable <math>x_i</math>, an inverted input variable <math>\neg x_i</math>, or the output of another gate; thus, there are at most <math>2+2n+t-1</math> possible gate inputs. It follows that the number of circuits with <math>t</math> gates is at most <math>2^t(t+2n+1)^{2t}</math>.

If <math>t=2^n/3n</math>, then
:<math>
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)<1,</math> thus, <math>2^t(t+2n+1)^{2t} < 2^{2^n}.</math>

Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function <math>f</math> which cannot be computed by any circuits with <math>2^n/3n</math> gates.
}}

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but ''almost all'' boolean functions have exponentially large circuit complexity.

=== Double counting ===
;Intersecting families;

An <math>\mathcal{F}\subseteq 2^S</math> is an '''intersecting''' family if for any <math>A,B\in\mathcal{F}</math> it holds that <math>A\cap B\neq\emptyset</math>.

Suppose that <math>n\ge 2k</math>. For <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math>, we can let all <math>A\in \mathcal{F}</math> contain one common element <math>a\in S</math> and <math>A-\{a\}</math> enumerates all <math>{n-1\choose k-1}</math> possible combinations of <math>(k-1)</math> elements in <math>S</math>. This gives us an intersecting family of size <math>|\mathcal{F}|={n-1\choose k-1}</math>.

The following theorem says that this is the largest possible cardinality an intersecting <math>\mathcal{F}</math> can achieve. The theorem was first proved by Erdős, Ko, and Rado in 1938, but published 23 years later. It is a fundamental result in the area of extremal set theory, which studies the maximum (or minimum) possible cardinality of a set system satisfying certain structural assumption. In this example, the structural assumption is intersecting.

Here we present a probabilistic proof by Katona.

{{Theorem
|Theorem (Erdős-Ko-Rado 1961)|
:Let <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is an intersecting family then <math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}
{{Proof| (due to Katona 1972).

Without loss of generality, let <math>S=[n]</math>.
For <math>i\in[n]</math>, let <math>A_i=\{(i+j)\bmod n\mid j\in[k]\}</math>. Then we make the following claim.

:'''Claim 1:''' <math>\mathcal{F}</math> can contain at most <math>k</math> many <math>A_i</math>.
The claim can be easily proved by observing that for any <math>i,j\in[n]</math> that <math>i<j</math>, <math>A_i</math> and <math>A_j</math> are disjoint if <math>j-i>k</math>, thus in order to make <math>\mathcal{F}</math> intersecting, all <math>A_i,A_j\in\mathcal{F}</math> have <math>|i-j|\le k</math>. This is violated once there are more than <math>k</math> many <math>A_i</math> in <math>\mathcal{F}</math>.

Now we prove the Erdős-Ko-Rado theorem. Let a permutation <math>\sigma</math> of <math>[n]</math> and an integer <math>i\in[n]</math> be chosen uniformly and independently at random. Let
:<math>R=\{\sigma((i+j)\bmod n)\mid j\in[k]\}, \quad\mbox{ or equivalently }R=\sigma(A_i)</math>.
By Claim 1, for any fixed permutation <math>\sigma</math>, the family <math>\mathcal{F}</math> can contain at most <math>k</math> of the sets <math>\sigma(A_i)</math>, thus conditioning on any particular <math>\sigma</math>, <math>\Pr[R\in\mathcal{F}\mid \sigma]\le\frac{k}{n}</math>. Hence
:<math>
\Pr[R\in\mathcal{F}]\le\frac{k}{n}.
</math>
On the other hand, by our construction, <math>R</math> is uniformly chosen from <math>{S\choose k}</math>, thus
:<math>
\Pr[R\in\mathcal{F}]=\frac{|\mathcal{F}|}{{n\choose k}}.
</math>
Therefore,
<math>
|\mathcal{F}|\le\frac{k}{n}{n\choose k}={n-1\choose k-1}.
</math>
}}

=== The averaging principle ===

== The Pigeonhole Principle ==

== The Probabilistic Method ==

Suppose we want prove the existence of mathematic objects with certain properties. One way to do so is to explicitly construct such an object. This kind of proofs can be interpreted as ''deterministic algorithms'' which find the object with desirable properties.

The probabilistic method provides another way of proving the existence of objects: instead of explicitly constructing an object, we define a probability space of objects in which the probability is positive that a randomly selected object has the required property.

The basic principle of the probabilistic method is very simple, and can be stated in intuitive ways:
*If an object chosen randomly from a universe satisfies a property with positive probability, then there must be an object in the universe that satisfies that property.
:For example, for a ball(the object) randomly chosen from a box(the universe) of balls, if the probability that the chosen ball is blue(the property) is >0, then there must be a blue ball in the box.
*Any random variable assumes at least one value that is no smaller than its expectation, and at least one value that is no greater than the expectation.
:For example, if we know the average height of the students in the class is <math>\ell</math>, then we know there is a students whose height is at least <math>\ell</math>, and there is a student whose height is at most <math>\ell</math>.

Although the idea of the probabilistic method is simple, it provides us a powerful tool for existential proof. In same cases, the proof itself is a ''randomized algorithm'', and if we are lucky, the algorithm could be very efficient.

=== Sampling ===
;Ramsey number

Recall the Ramsey theorem which states that in a meeting of at least six people, there are either three people knowing each other or three people not knowing each other. In graph theoretical terms, this means that no matter how we color the edges of <math>K_6</math> (the complete graph on six vertices), there must be a '''monochromatic''' <math>K_3</math> (a triangle whose edges have the same color).

Generally, the '''Ramsey number''' <math>R(k,\ell)</math> is the smallest integer <math>n</math> such that in any two-coloring of the edges of a complete graph on <math>n</math> vertices <math>K_n</math> by red and blue, either there is a red <math>K_k</math> or there is a blue <math>K_\ell</math>.

Ramsey showed in 1929 that <math>R(k,\ell)</math> is finite for any <math>k</math> and <math>\ell</math>. It is extremely hard to compute the exact value of <math>R(k,\ell)</math>. Here we give a lower bound of <math>R(k,k)</math> by the probabilistic method.

{{Theorem
|Theorem (Erdős 1947)|
:If <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math> then it is possible to color the edges of <math>K_n</math> with two colors so that there is no monochromatic <math>K_k</math> subgraph.
}}
{{Proof| Consider a random two-coloring of edges of <math>K_n</math> obtained as follows:
* For each edge of <math>K_n</math>, independently flip a fair coin to decide the color of the edge.

For any fixed set <math>S</math> of <math>k</math> vertices, let <math>\mathcal{E}_S</math> be the event that the <math>K_k</math> subgraph induced by <math>S</math> is monochromatic. There are <math>{k\choose 2}</math> many edges in <math>K_k</math>, therefore
:<math>\Pr[\mathcal{E}_S]=2\cdot 2^{-{k\choose 2}}=2^{1-{k\choose 2}}.</math>

Since there are <math>{n\choose k}</math> possible choices of <math>S</math>, by the union bound
:<math>
\Pr[\exists S, \mathcal{E}_S]\le {n\choose k}\cdot\Pr[\mathcal{E}_S]={n\choose k}\cdot 2^{1-{k\choose 2}}.
</math>
Due to the assumption, <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math>, thus there exists a two coloring that none of <math>\mathcal{E}_S</math> occurs, which means there is no monochromatic <math>K_k</math> subgraph.
}}

For <math>k\ge 3</math> and we take <math>n=\lfloor2^{k/2}\rfloor</math>, then
:<math>
\begin{align}
{n\choose k}\cdot 2^{1-{k\choose 2}}
&<
\frac{n^k}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&\le
\frac{2^{k^2/2}}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&=
\frac{2^{1+\frac{k}{2}}}{k!}\\
&<1.
\end{align}
</math>
By the above theorem, there exists a two-coloring of <math>K_n</math> that there is no monochromatic <math>K_k</math>. Therefore, the Ramsey number <math>R(k,k)>\lfloor2^{k/2}\rfloor</math> for all <math>k\ge 3</math>.

Note that for sufficiently large <math>k</math>, if <math>n= \lfloor 2^{k/2}\rfloor</math>, then the probability that there exists a monochromatic <math>K_k</math> is bounded by
:<math>
{n\choose k}\cdot 2^{1-{k\choose 2}}
<
\frac{2^{1+\frac{k}{2}}}{k!}
\ll 1,
</math>
which means that a random two-coloring of <math>K_n</math> is very likely not to contain a monochromatic <math>K_{2\log n}</math>. This gives us a very simple randomized algorithm for finding a two-coloring of <math>K_n</math> without monochromatic <math>K_{2\log n}</math>.

;Blocking number
Let <math>S</math> be a set. Let <math>2^{S}=\{A\mid A\subseteq S\}</math> be the power set of <math>S</math>, and let <math>{S\choose k}=\{A\mid A\subseteq S\mbox{ and }|A|=k\}</math> be the '''<math>k</math>-uniform''' of <math>S</math>.

We call <math>\mathcal{F}</math> a '''set family''' (or a '''set system''') with '''ground set''' <math>S</math> if <math>\mathcal{F}\subseteq 2^{S}</math>. The members of <math>\mathcal{F}</math> are subsets of <math>S</math>.

Given a set family <math>\mathcal{F}</math> with ground set <math>S</math>,
a set <math>T\subseteq S</math> is a '''blocking set''' of <math>\mathcal{F}</math> if all <math>A\in\mathcal{F}</math> have <math>A\cap T\neq \emptyset</math>, i.e. <math>T</math> intersects (blocks) all member set of <math>\mathcal{F}</math>.

{{Theorem
|Theorem|
:Given a set family <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>m=|\mathcal{F}|</math> and <math>n=|S|</math>, <math>\mathcal{F}</math> has a blocking set of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math>.
}}
{{Proof| Let <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>. Let <math>T</math> be a set chosen uniformly at random from <math>{S\choose \tau}</math>. We show that <math>T</math> is a blocking set of <math>\mathcal{F}</math> with a probability >0.

Fix any <math>A\in\mathcal{F}</math>. Recall that <math>\mathcal{F}\subseteq{S\choose k}</math>, thus <math>|A|=k</math>. And
:<math>
\begin{align}
\Pr[A\cap T=\emptyset]
&=
\frac{\left|{S-A\choose \tau}\right|}{\left|{S\choose \tau}\right|}\\
&=
\frac{{n-k\choose \tau}}{{n\choose\tau}}\\
&=
\frac{(n-k)\cdot(n-k-1)\cdots(n-k-\tau+1)}{n\cdot(n-1)\cdots(n-\tau+1)}\\
&<
\left(1-\frac{k}{n}\right)^{\tau}\\
&\le
\exp\left(-\frac{k\tau}{n}\right)\\
&\le
\frac{1}{m}.
\end{align}
</math>
By the union bound, the probability that there exists an <math>A\in\mathcal{F}</math> that misses <math>T</math>
:<math>
\Pr[\exists A\in\mathcal{F}, A\cap T=\emptyset]\le m\Pr[A\cap T=\emptyset]<m\cdot\frac{1}{m}=1.
</math>
Thus, the probability that <math>T</math> is a blocking set
:<math>
\Pr[\forall A\in\mathcal{F}, A\cap T\neq\emptyset]>0.
</math>
There exists a blocking set of size <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>.
}}

The theorem also hints us to a randomized algorithm. In order to make the algorithm efficient, we relax the size of <math>T</math> to <math>\tau=\frac{2n\ln m}{k}</math>. Uniformly choose <math>\tau</math> elements from <math>S</math> to form the set <math>T</math>, by the above analysis, the probability that <math>T</math> is NOT a blocking set is at most
:<math>
m\exp\left(-\frac{n\tau}{k}\right)=m\exp(-2\ln m)=\frac{1}{m}.
</math>
Thus, a blocking set is found with high probability.

=== Linearity of expectation ===

;Maximum cut

Given an undirected graph <math>G(V,E)</math>, a set <math>C</math> of edges of <math>G</math> is called a '''cut''' if <math>G</math> is disconnected after removing the edges in <math>C</math>. We can represent a cut by <math>c(S,T)</math> where <math>(S,T)</math> is a bipartition of the vertex set <math>V</math>, and <math>c(S,T)=\{uv\in E\mid u\in S,v\in T\}</math> is the set of edges crossing between <math>S</math> and <math>T</math>.

We have seen how to compute min-cut: either by deterministic max-flow algorithm, or by Karger's randomized algorithm. On the other hand, max-cut is hard to compute, because it is '''NP-complete'''. Actually, the weighted version of max-cut is among the [http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems Karp's 21 NP-complete problems].

We now show by the probabilistic method that a max-cut always has at least half the edges.

{{Theorem
|Theorem|
:Given an undirected graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges, there is a cut of size at least <math>\frac{m}{2}</math>.
}}
{{Proof| Enumerate the vertices in an arbitrary order. Partition the vertex set <math>V</math> into two disjoint sets <math>S</math> and <math>T</math> as follows.
:For each vertex <math>v\in V</math>,
:* independently choose one of <math>S</math> and <math>T</math> with equal probability, and let <math>v</math> join the chosen set.

For each vertex <math>v\in V</math>, let <math>X_v\in\{S,T\}</math> be the random variable which represents the set that <math>v</math> joins. For each edge <math>uv\in E</math>, let <math>Y_{uv}</math> be the 0-1 random variable which indicates whether <math>uv</math> crosses between <math>S</math> and <math>T</math>. Clearly,
:<math>
\Pr[Y_{uv}=1]=\Pr[X_u\neq X_v]=\frac{1}{2}.
</math>

The size of <math>c(S,T)</math> is given by <math>Y=\sum_{uv\in E}Y_{uv}</math>. By the linearity of expectation,
:<math>
\mathbf{E}[Y]=\sum_{uv\in E}\mathbf{E}[Y_{uv}]=\sum_{uv\in E}\Pr[Y_{uv}=1]=\frac{m}{2}.
</math>
Therefore, there exist a bipartition <math>(S,T)</math> of <math>V</math> such that <math>|c(S,T)|\ge\frac{m}{2}</math>, i.e. there exists a cut of <math>G</math> which contains at least <math>\frac{m}{2}</math> edges.
}}

;Maximum satisfiability

Suppose that we have a number of boolean variables <math>x_1,x_2,\ldots,\in\{\mathrm{true},\mathrm{false}\}</math>. A '''literal''' is either a variable <math>x_i</math> itself or its negation <math>\neg x_i</math>. A logic expression is a '''conjunctive normal form (CNF)''' if it is written as the conjunction(AND) of a set of '''clauses''', where each clause is a disjunction(OR) of literals. For example:
:<math>
(x_1\vee \neg x_2 \vee \neg x_3)\wedge (\neg x_1\vee \neg x_3)\wedge (x_1\vee x_2\vee x_4)\wedge (x_4\vee \neg x_3)\wedge (x_4\vee \neg x_1).
</math>

The satisfiability (SAT) problem ask whether the CNF is satisfiable, i.e. there exists an assignment of variables to the values of true and false so that all clauses are true. The maximum satisfiability (MAXSAT) is the optimization version of SAT, which ask for an assignment that the number of satisfied clauses is maximized.

SAT is the first problem known to be '''NP-complete''' (the Cook-Levin theorem). MAXSAT is also '''NP-complete'''. We then see that there always exists a roughly good truth assignment which satisfies half the clauses.

{{Theorem
|Theorem|
:For any set of <math>m</math> clauses, there is a truth assignment that satisfies at least <math>\frac{m}{2}</math> clauses.
}}
{{Proof| For each variable, independently assign a random value in <math>\{\mathrm{true},\mathrm{false}\}</math> with equal probability. For the <math>i</math>th clause, let <math>X_i</math> be the random variable which indicates whether the <math>i</math>th clause is satisfied. Suppose that there are <math>k</math> literals in the clause. The probability that the clause is satisfied is
:<math>\Pr[X_k=1]\ge(1-2^{-k})\ge\frac{1}{2}</math>.

Let <math>X=\sum_{i=1}^m X_i</math> be the number of satisfied clauses. By the linearity of expectation,
:<math>
\mathbf{E}[X]=\sum_{i=1}^{m}\mathbf{E}[X_i]\ge \frac{m}{2}.
</math>
Therefore, there exists an assignment such that at least <math>\frac{m}{2}</math> clauses are satisfied.
}}

=== Alterations ===
;Independent sets
An independent set of a graph is a set of vertices with no edges between them. The following theorem gives a lower bound on the size of the largest independent set.
{{Theorem
|Theorem|
:Let <math>G(V,E)</math> be a graph on <math>n</math> vertices with <math>m</math> edges. Then <math>G</math> has an independent set with at least <math>\frac{n^2}{4m}</math> vertices.
}}
{{Proof| Let <math>S</math> be a set of vertices constructed as follows:
:For each vertex <math>v\in V</math>:
:* <math>v</math> is included in <math>S</math> independently with probability <math>p</math>,
<math>p</math> to be determined.

Let <math>X=|S|</math>. It is obvious that <math>\mathbf{E}[X]=np</math>.

For each edge <math>e\in E</math>, let <math>Y_{e}</math> be the random variable which indicates whether both endpoints of <math></math> are in <math>S</math>.
:<math>
\mathbf{E}[Y_{uv}]=\Pr[u\in S\wedge v\in S]=p^2.
</math>
Let <math>Y</math> be the number of edges in the subgraph of <math>G</math> induced by <math>S</math>. It holds that <math>Y=\sum_{e\in E}Y_e</math>. By linearity of expectation,
:<math>\mathbf{E}[Y]=\sum_{e\in E}\mathbf{E}[Y_e]=mp^2</math>.

Note that although <math>S</math> is not necessary an independent set, it can be modified to one if for each edge <math>e</math> of the induced subgraph <math>G(S)</math>, we delete one of the endpoint of <math>e</math> from <math>S</math>. Let <math>S^*</math> be the resulting set. It is obvious that <math>S^*</math> is an independent set since there is no edge left in the induced subgraph <math>G(S^*)</math>.

Since there are <math>Y</math> edges in <math>G(S)</math>, there are at most <math>Y</math> vertices in <math>S</math> are deleted to make it become <math>S^*</math>. Therefore, <math>|S^*|\ge X-Y</math>. By linearity of expectation,
:<math>
\mathbf{E}[|S^*|]\ge\mathbf{E}[X-Y]=\mathbf{E}[X]-\mathbf{E}[Y]=np-mp^2.
</math>
The expectation is maximized when <math>p=\frac{n}{2m}</math>, thus
:<math>
\mathbf{E}[|S^*|]\ge n\cdot\frac{n}{2m}-m\left(\frac{n}{2m}\right)^2=\frac{n^2}{4m}.
</math>
There exists an independent set which contains at least <math>\frac{n^2}{4m}</math> vertices.
}}

The proof actually propose a randomized algorithm for constructing large independent set:

{{Theorem
|Algorithm|
Given a graph on <math>n</math> vertices with <math>m</math> edges, let <math>d=\frac{2m}{n}</math> be the average degree.
#For each vertex <math>v\in V</math>, <math>v</math> is included in <math>S</math> independently with probability <math>\frac{1}{d}</math>.
#For each remaining edge in the induced subgraph <math>G(S)</math>, remove one of the endpoints from <math>S</math>.
}}

Let <math>S^*</math> be the resulting set. We have shown that <math>S^*</math> is an independent set and <math>\mathbf{E}[|S^*|]\ge\frac{n^2}{4m}</math>.

== The Lovász Local Lemma ==

Consider a set of "bad" events <math>A_1,A_2,\ldots,A_n</math>. Suppose that <math>\Pr[A_i]\le p</math> for all <math>1\le i\le n</math>. We want to show that there is a situation that none of the bad events occurs. Due to the probabilistic method, we need to prove that
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0.
</math>
;Case 1<nowiki>: mutually independent events.</nowiki>
If all the bad events <math>A_1,A_2,\ldots,A_n</math> are mutually independent, then
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge(1-p)^n>0,
</math>
for any <math>p<1</math>.

;Case 2<nowiki>: arbitrarily dependent events.</nowiki>
On the other hand, if we put no assumption on the dependencies between the events, then by the union bound (which holds unconditionally),
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=1-\Pr\left[\bigvee_{i=1}^n A_i\right]\ge 1-np,
</math>
which is not an interesting bound for <math>p\ge\frac{1}{n}</math>. If we make no further assumption on the dependencies between the events, this bound is tight.

;Example
:Consider that a ball is uniformly thrown into one of the <math>(n+1)</math> bins. Let the "bad" events <math>A_1,A_2,\ldots,A_n</math> be defined as that <math>A_i</math> represents that the ball falls into the <math>i</math>th bin. The only good event is that the ball falls into the <math>(n+1)</math>th bin. Clearly, <math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=1-n\cdot\frac{1}{n+1}</math>. Thus the above union bound is achieved.

This example shows that dependencies between the events could cause troubles.

We would like to know what is going on between the two extreme cases: mutually independent events, and arbitrarily dependent events. The Lovász local lemma provides such a tool.

=== The local lemma ===
The local lemma is powerful tool for showing the possibility of rare event under limited dependencies. The structure of dependencies between a set of events is described by a '''dependency graph'''.

{{Theorem
|Definition|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set 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>.
}}

;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>.

This construction gives a general framework for the probability spaces with limited dependencies and is central to the constructive proof of the Lovász local lemma. In this example, each event is a predicate of variables, and the events are dependent if they depend on some common events.

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
|Theorem (The local lemma)|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold:
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
:#the maximum degree of the dependency graph for the events <math>A_1,A_2,\ldots,A_n</math> is <math>d</math>, and
:::<math>ep(d+1)\le 1</math>.
:Then
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
}}

Combinatorics (Fall 2010)/Existence, the probabilistic method

2010-09-13T05:05:45Z

172.16.65.101: /* Counting arguments */

== Counting arguments ==
;Circuit complexity

A '''boolean function''' is a function is the form <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , x_n</math>. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in '''P''' can be computed by a circuit with polynomially many gates. Thus, if we can find a function in '''NP''' that cannot be computed by any circuit with polynomially many gates, then '''NP'''<math>\neq</math>'''P'''.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

{{Theorem
|Theorem (Shannon 1949)|
:There is a boolean function <math>f:\{0,1\}^n\rightarrow \{0,1\}</math> with circuit complexity greater than <math>\frac{2^n}{3n}</math>.
}}
{{Proof|
We first count the number of boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. There are <math>2^{2^n}</math> boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Then we count the number of boolean circuit with fixed number of gates.
Fix an integer <math>t</math>, we count the number of circuits with <math>t</math> gates. By the [http://en.wikipedia.org/wiki/De_Morgan's_laws De Morgan's laws], we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable <math>x_i</math>, an inverted input variable <math>\neg x_i</math>, or the output of another gate; thus, there are at most <math>2+2n+t-1</math> possible gate inputs. It follows that the number of circuits with <math>t</math> gates is at most <math>2^t(t+2n+1)^{2t}</math>.

If <math>t=2^n/3n</math>, then
:<math>
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)<1,</math> thus, <math>2^t(t+2n+1)^{2t} < 2^{2^n}.</math>

Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function <math>f</math> which cannot be computed by any circuits with <math>2^n/3n</math> gates.
}}

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but ''almost all'' boolean functions have exponentially large circuit complexity.

=== Double counting ===
;Intersecting families;

An <math>\mathcal{F}\subseteq 2^S</math> is an '''intersecting''' family if for any <math>A,B\in\mathcal{F}</math> it holds that <math>A\cap B\neq\emptyset</math>.

Suppose that <math>n\ge 2k</math>. For <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math>, we can let all <math>A\in \mathcal{F}</math> contain one common element <math>a\in S</math> and <math>A-\{a\}</math> enumerates all <math>{n-1\choose k-1}</math> possible combinations of <math>(k-1)</math> elements in <math>S</math>. This gives us an intersecting family of size <math>|\mathcal{F}|={n-1\choose k-1}</math>.

The following theorem says that this is the largest possible cardinality an intersecting <math>\mathcal{F}</math> can achieve. The theorem was first proved by Erdős, Ko, and Rado in 1938, but published 23 years later. It is a fundamental result in the area of extremal set theory, which studies the maximum (or minimum) possible cardinality of a set system satisfying certain structural assumption. In this example, the structural assumption is intersecting.

Here we present a probabilistic proof by Katona.

{{Theorem
|Theorem (Erdős-Ko-Rado 1961)|
:Let <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is an intersecting family then <math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}
{{Proof| (due to Katona 1972).

Without loss of generality, let <math>S=[n]</math>.
For <math>i\in[n]</math>, let <math>A_i=\{(i+j)\bmod n\mid j\in[k]\}</math>. Then we make the following claim.

:'''Claim 1:''' <math>\mathcal{F}</math> can contain at most <math>k</math> many <math>A_i</math>.
The claim can be easily proved by observing that for any <math>i,j\in[n]</math> that <math>i<j</math>, <math>A_i</math> and <math>A_j</math> are disjoint if <math>j-i>k</math>, thus in order to make <math>\mathcal{F}</math> intersecting, all <math>A_i,A_j\in\mathcal{F}</math> have <math>|i-j|\le k</math>. This is violated once there are more than <math>k</math> many <math>A_i</math> in <math>\mathcal{F}</math>.

Now we prove the Erdős-Ko-Rado theorem. Let a permutation <math>\sigma</math> of <math>[n]</math> and an integer <math>i\in[n]</math> be chosen uniformly and independently at random. Let
:<math>R=\{\sigma((i+j)\bmod n)\mid j\in[k]\}, \quad\mbox{ or equivalently }R=\sigma(A_i)</math>.
By Claim 1, for any fixed permutation <math>\sigma</math>, the family <math>\mathcal{F}</math> can contain at most <math>k</math> of the sets <math>\sigma(A_i)</math>, thus conditioning on any particular <math>\sigma</math>, <math>\Pr[R\in\mathcal{F}\mid \sigma]\le\frac{k}{n}</math>. Hence
:<math>
\Pr[R\in\mathcal{F}]\le\frac{k}{n}.
</math>
On the other hand, by our construction, <math>R</math> is uniformly chosen from <math>{S\choose k}</math>, thus
:<math>
\Pr[R\in\mathcal{F}]=\frac{|\mathcal{F}|}{{n\choose k}}.
</math>
Therefore,
<math>
|\mathcal{F}|\le\frac{k}{n}{n\choose k}={n-1\choose k-1}.
</math>
}}

=== The averaging principle ===

== The Probabilistic Method ==

Suppose we want prove the existence of mathematic objects with certain properties. One way to do so is to explicitly construct such an object. This kind of proofs can be interpreted as ''deterministic algorithms'' which find the object with desirable properties.

The probabilistic method provides another way of proving the existence of objects: instead of explicitly constructing an object, we define a probability space of objects in which the probability is positive that a randomly selected object has the required property.

The basic principle of the probabilistic method is very simple, and can be stated in intuitive ways:
*If an object chosen randomly from a universe satisfies a property with positive probability, then there must be an object in the universe that satisfies that property.
:For example, for a ball(the object) randomly chosen from a box(the universe) of balls, if the probability that the chosen ball is blue(the property) is >0, then there must be a blue ball in the box.
*Any random variable assumes at least one value that is no smaller than its expectation, and at least one value that is no greater than the expectation.
:For example, if we know the average height of the students in the class is <math>\ell</math>, then we know there is a students whose height is at least <math>\ell</math>, and there is a student whose height is at most <math>\ell</math>.

Although the idea of the probabilistic method is simple, it provides us a powerful tool for existential proof. In same cases, the proof itself is a ''randomized algorithm'', and if we are lucky, the algorithm could be very efficient.

=== Sampling ===
;Ramsey number

Recall the Ramsey theorem which states that in a meeting of at least six people, there are either three people knowing each other or three people not knowing each other. In graph theoretical terms, this means that no matter how we color the edges of <math>K_6</math> (the complete graph on six vertices), there must be a '''monochromatic''' <math>K_3</math> (a triangle whose edges have the same color).

Generally, the '''Ramsey number''' <math>R(k,\ell)</math> is the smallest integer <math>n</math> such that in any two-coloring of the edges of a complete graph on <math>n</math> vertices <math>K_n</math> by red and blue, either there is a red <math>K_k</math> or there is a blue <math>K_\ell</math>.

Ramsey showed in 1929 that <math>R(k,\ell)</math> is finite for any <math>k</math> and <math>\ell</math>. It is extremely hard to compute the exact value of <math>R(k,\ell)</math>. Here we give a lower bound of <math>R(k,k)</math> by the probabilistic method.

{{Theorem
|Theorem (Erdős 1947)|
:If <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math> then it is possible to color the edges of <math>K_n</math> with two colors so that there is no monochromatic <math>K_k</math> subgraph.
}}
{{Proof| Consider a random two-coloring of edges of <math>K_n</math> obtained as follows:
* For each edge of <math>K_n</math>, independently flip a fair coin to decide the color of the edge.

For any fixed set <math>S</math> of <math>k</math> vertices, let <math>\mathcal{E}_S</math> be the event that the <math>K_k</math> subgraph induced by <math>S</math> is monochromatic. There are <math>{k\choose 2}</math> many edges in <math>K_k</math>, therefore
:<math>\Pr[\mathcal{E}_S]=2\cdot 2^{-{k\choose 2}}=2^{1-{k\choose 2}}.</math>

Since there are <math>{n\choose k}</math> possible choices of <math>S</math>, by the union bound
:<math>
\Pr[\exists S, \mathcal{E}_S]\le {n\choose k}\cdot\Pr[\mathcal{E}_S]={n\choose k}\cdot 2^{1-{k\choose 2}}.
</math>
Due to the assumption, <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math>, thus there exists a two coloring that none of <math>\mathcal{E}_S</math> occurs, which means there is no monochromatic <math>K_k</math> subgraph.
}}

For <math>k\ge 3</math> and we take <math>n=\lfloor2^{k/2}\rfloor</math>, then
:<math>
\begin{align}
{n\choose k}\cdot 2^{1-{k\choose 2}}
&<
\frac{n^k}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&\le
\frac{2^{k^2/2}}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&=
\frac{2^{1+\frac{k}{2}}}{k!}\\
&<1.
\end{align}
</math>
By the above theorem, there exists a two-coloring of <math>K_n</math> that there is no monochromatic <math>K_k</math>. Therefore, the Ramsey number <math>R(k,k)>\lfloor2^{k/2}\rfloor</math> for all <math>k\ge 3</math>.

Note that for sufficiently large <math>k</math>, if <math>n= \lfloor 2^{k/2}\rfloor</math>, then the probability that there exists a monochromatic <math>K_k</math> is bounded by
:<math>
{n\choose k}\cdot 2^{1-{k\choose 2}}
<
\frac{2^{1+\frac{k}{2}}}{k!}
\ll 1,
</math>
which means that a random two-coloring of <math>K_n</math> is very likely not to contain a monochromatic <math>K_{2\log n}</math>. This gives us a very simple randomized algorithm for finding a two-coloring of <math>K_n</math> without monochromatic <math>K_{2\log n}</math>.

;Blocking number
Let <math>S</math> be a set. Let <math>2^{S}=\{A\mid A\subseteq S\}</math> be the power set of <math>S</math>, and let <math>{S\choose k}=\{A\mid A\subseteq S\mbox{ and }|A|=k\}</math> be the '''<math>k</math>-uniform''' of <math>S</math>.

We call <math>\mathcal{F}</math> a '''set family''' (or a '''set system''') with '''ground set''' <math>S</math> if <math>\mathcal{F}\subseteq 2^{S}</math>. The members of <math>\mathcal{F}</math> are subsets of <math>S</math>.

Given a set family <math>\mathcal{F}</math> with ground set <math>S</math>,
a set <math>T\subseteq S</math> is a '''blocking set''' of <math>\mathcal{F}</math> if all <math>A\in\mathcal{F}</math> have <math>A\cap T\neq \emptyset</math>, i.e. <math>T</math> intersects (blocks) all member set of <math>\mathcal{F}</math>.

{{Theorem
|Theorem|
:Given a set family <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>m=|\mathcal{F}|</math> and <math>n=|S|</math>, <math>\mathcal{F}</math> has a blocking set of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math>.
}}
{{Proof| Let <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>. Let <math>T</math> be a set chosen uniformly at random from <math>{S\choose \tau}</math>. We show that <math>T</math> is a blocking set of <math>\mathcal{F}</math> with a probability >0.

Fix any <math>A\in\mathcal{F}</math>. Recall that <math>\mathcal{F}\subseteq{S\choose k}</math>, thus <math>|A|=k</math>. And
:<math>
\begin{align}
\Pr[A\cap T=\emptyset]
&=
\frac{\left|{S-A\choose \tau}\right|}{\left|{S\choose \tau}\right|}\\
&=
\frac{{n-k\choose \tau}}{{n\choose\tau}}\\
&=
\frac{(n-k)\cdot(n-k-1)\cdots(n-k-\tau+1)}{n\cdot(n-1)\cdots(n-\tau+1)}\\
&<
\left(1-\frac{k}{n}\right)^{\tau}\\
&\le
\exp\left(-\frac{k\tau}{n}\right)\\
&\le
\frac{1}{m}.
\end{align}
</math>
By the union bound, the probability that there exists an <math>A\in\mathcal{F}</math> that misses <math>T</math>
:<math>
\Pr[\exists A\in\mathcal{F}, A\cap T=\emptyset]\le m\Pr[A\cap T=\emptyset]<m\cdot\frac{1}{m}=1.
</math>
Thus, the probability that <math>T</math> is a blocking set
:<math>
\Pr[\forall A\in\mathcal{F}, A\cap T\neq\emptyset]>0.
</math>
There exists a blocking set of size <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>.
}}

The theorem also hints us to a randomized algorithm. In order to make the algorithm efficient, we relax the size of <math>T</math> to <math>\tau=\frac{2n\ln m}{k}</math>. Uniformly choose <math>\tau</math> elements from <math>S</math> to form the set <math>T</math>, by the above analysis, the probability that <math>T</math> is NOT a blocking set is at most
:<math>
m\exp\left(-\frac{n\tau}{k}\right)=m\exp(-2\ln m)=\frac{1}{m}.
</math>
Thus, a blocking set is found with high probability.

=== Linearity of expectation ===

;Maximum cut

Given an undirected graph <math>G(V,E)</math>, a set <math>C</math> of edges of <math>G</math> is called a '''cut''' if <math>G</math> is disconnected after removing the edges in <math>C</math>. We can represent a cut by <math>c(S,T)</math> where <math>(S,T)</math> is a bipartition of the vertex set <math>V</math>, and <math>c(S,T)=\{uv\in E\mid u\in S,v\in T\}</math> is the set of edges crossing between <math>S</math> and <math>T</math>.

We have seen how to compute min-cut: either by deterministic max-flow algorithm, or by Karger's randomized algorithm. On the other hand, max-cut is hard to compute, because it is '''NP-complete'''. Actually, the weighted version of max-cut is among the [http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems Karp's 21 NP-complete problems].

We now show by the probabilistic method that a max-cut always has at least half the edges.

{{Theorem
|Theorem|
:Given an undirected graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges, there is a cut of size at least <math>\frac{m}{2}</math>.
}}
{{Proof| Enumerate the vertices in an arbitrary order. Partition the vertex set <math>V</math> into two disjoint sets <math>S</math> and <math>T</math> as follows.
:For each vertex <math>v\in V</math>,
:* independently choose one of <math>S</math> and <math>T</math> with equal probability, and let <math>v</math> join the chosen set.

For each vertex <math>v\in V</math>, let <math>X_v\in\{S,T\}</math> be the random variable which represents the set that <math>v</math> joins. For each edge <math>uv\in E</math>, let <math>Y_{uv}</math> be the 0-1 random variable which indicates whether <math>uv</math> crosses between <math>S</math> and <math>T</math>. Clearly,
:<math>
\Pr[Y_{uv}=1]=\Pr[X_u\neq X_v]=\frac{1}{2}.
</math>

The size of <math>c(S,T)</math> is given by <math>Y=\sum_{uv\in E}Y_{uv}</math>. By the linearity of expectation,
:<math>
\mathbf{E}[Y]=\sum_{uv\in E}\mathbf{E}[Y_{uv}]=\sum_{uv\in E}\Pr[Y_{uv}=1]=\frac{m}{2}.
</math>
Therefore, there exist a bipartition <math>(S,T)</math> of <math>V</math> such that <math>|c(S,T)|\ge\frac{m}{2}</math>, i.e. there exists a cut of <math>G</math> which contains at least <math>\frac{m}{2}</math> edges.
}}

;Maximum satisfiability

Suppose that we have a number of boolean variables <math>x_1,x_2,\ldots,\in\{\mathrm{true},\mathrm{false}\}</math>. A '''literal''' is either a variable <math>x_i</math> itself or its negation <math>\neg x_i</math>. A logic expression is a '''conjunctive normal form (CNF)''' if it is written as the conjunction(AND) of a set of '''clauses''', where each clause is a disjunction(OR) of literals. For example:
:<math>
(x_1\vee \neg x_2 \vee \neg x_3)\wedge (\neg x_1\vee \neg x_3)\wedge (x_1\vee x_2\vee x_4)\wedge (x_4\vee \neg x_3)\wedge (x_4\vee \neg x_1).
</math>

The satisfiability (SAT) problem ask whether the CNF is satisfiable, i.e. there exists an assignment of variables to the values of true and false so that all clauses are true. The maximum satisfiability (MAXSAT) is the optimization version of SAT, which ask for an assignment that the number of satisfied clauses is maximized.

SAT is the first problem known to be '''NP-complete''' (the Cook-Levin theorem). MAXSAT is also '''NP-complete'''. We then see that there always exists a roughly good truth assignment which satisfies half the clauses.

{{Theorem
|Theorem|
:For any set of <math>m</math> clauses, there is a truth assignment that satisfies at least <math>\frac{m}{2}</math> clauses.
}}
{{Proof| For each variable, independently assign a random value in <math>\{\mathrm{true},\mathrm{false}\}</math> with equal probability. For the <math>i</math>th clause, let <math>X_i</math> be the random variable which indicates whether the <math>i</math>th clause is satisfied. Suppose that there are <math>k</math> literals in the clause. The probability that the clause is satisfied is
:<math>\Pr[X_k=1]\ge(1-2^{-k})\ge\frac{1}{2}</math>.

Let <math>X=\sum_{i=1}^m X_i</math> be the number of satisfied clauses. By the linearity of expectation,
:<math>
\mathbf{E}[X]=\sum_{i=1}^{m}\mathbf{E}[X_i]\ge \frac{m}{2}.
</math>
Therefore, there exists an assignment such that at least <math>\frac{m}{2}</math> clauses are satisfied.
}}

=== Alterations ===
;Independent sets
An independent set of a graph is a set of vertices with no edges between them. The following theorem gives a lower bound on the size of the largest independent set.
{{Theorem
|Theorem|
:Let <math>G(V,E)</math> be a graph on <math>n</math> vertices with <math>m</math> edges. Then <math>G</math> has an independent set with at least <math>\frac{n^2}{4m}</math> vertices.
}}
{{Proof| Let <math>S</math> be a set of vertices constructed as follows:
:For each vertex <math>v\in V</math>:
:* <math>v</math> is included in <math>S</math> independently with probability <math>p</math>,
<math>p</math> to be determined.

Let <math>X=|S|</math>. It is obvious that <math>\mathbf{E}[X]=np</math>.

For each edge <math>e\in E</math>, let <math>Y_{e}</math> be the random variable which indicates whether both endpoints of <math></math> are in <math>S</math>.
:<math>
\mathbf{E}[Y_{uv}]=\Pr[u\in S\wedge v\in S]=p^2.
</math>
Let <math>Y</math> be the number of edges in the subgraph of <math>G</math> induced by <math>S</math>. It holds that <math>Y=\sum_{e\in E}Y_e</math>. By linearity of expectation,
:<math>\mathbf{E}[Y]=\sum_{e\in E}\mathbf{E}[Y_e]=mp^2</math>.

Note that although <math>S</math> is not necessary an independent set, it can be modified to one if for each edge <math>e</math> of the induced subgraph <math>G(S)</math>, we delete one of the endpoint of <math>e</math> from <math>S</math>. Let <math>S^*</math> be the resulting set. It is obvious that <math>S^*</math> is an independent set since there is no edge left in the induced subgraph <math>G(S^*)</math>.

Since there are <math>Y</math> edges in <math>G(S)</math>, there are at most <math>Y</math> vertices in <math>S</math> are deleted to make it become <math>S^*</math>. Therefore, <math>|S^*|\ge X-Y</math>. By linearity of expectation,
:<math>
\mathbf{E}[|S^*|]\ge\mathbf{E}[X-Y]=\mathbf{E}[X]-\mathbf{E}[Y]=np-mp^2.
</math>
The expectation is maximized when <math>p=\frac{n}{2m}</math>, thus
:<math>
\mathbf{E}[|S^*|]\ge n\cdot\frac{n}{2m}-m\left(\frac{n}{2m}\right)^2=\frac{n^2}{4m}.
</math>
There exists an independent set which contains at least <math>\frac{n^2}{4m}</math> vertices.
}}

The proof actually propose a randomized algorithm for constructing large independent set:

{{Theorem
|Algorithm|
Given a graph on <math>n</math> vertices with <math>m</math> edges, let <math>d=\frac{2m}{n}</math> be the average degree.
#For each vertex <math>v\in V</math>, <math>v</math> is included in <math>S</math> independently with probability <math>\frac{1}{d}</math>.
#For each remaining edge in the induced subgraph <math>G(S)</math>, remove one of the endpoints from <math>S</math>.
}}

Let <math>S^*</math> be the resulting set. We have shown that <math>S^*</math> is an independent set and <math>\mathbf{E}[|S^*|]\ge\frac{n^2}{4m}</math>.

== The Lovász Local Lemma ==

Consider a set of "bad" events <math>A_1,A_2,\ldots,A_n</math>. Suppose that <math>\Pr[A_i]\le p</math> for all <math>1\le i\le n</math>. We want to show that there is a situation that none of the bad events occurs. Due to the probabilistic method, we need to prove that
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0.
</math>
;Case 1<nowiki>: mutually independent events.</nowiki>
If all the bad events <math>A_1,A_2,\ldots,A_n</math> are mutually independent, then
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge(1-p)^n>0,
</math>
for any <math>p<1</math>.

;Case 2<nowiki>: arbitrarily dependent events.</nowiki>
On the other hand, if we put no assumption on the dependencies between the events, then by the union bound (which holds unconditionally),
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=1-\Pr\left[\bigvee_{i=1}^n A_i\right]\ge 1-np,
</math>
which is not an interesting bound for <math>p\ge\frac{1}{n}</math>. If we make no further assumption on the dependencies between the events, this bound is tight.

;Example
:Consider that a ball is uniformly thrown into one of the <math>(n+1)</math> bins. Let the "bad" events <math>A_1,A_2,\ldots,A_n</math> be defined as that <math>A_i</math> represents that the ball falls into the <math>i</math>th bin. The only good event is that the ball falls into the <math>(n+1)</math>th bin. Clearly, <math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=1-n\cdot\frac{1}{n+1}</math>. Thus the above union bound is achieved.

This example shows that dependencies between the events could cause troubles.

We would like to know what is going on between the two extreme cases: mutually independent events, and arbitrarily dependent events. The Lovász local lemma provides such a tool.

=== The local lemma ===
The local lemma is powerful tool for showing the possibility of rare event under limited dependencies. The structure of dependencies between a set of events is described by a '''dependency graph'''.

{{Theorem
|Definition|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set 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>.
}}

;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>.

This construction gives a general framework for the probability spaces with limited dependencies and is central to the constructive proof of the Lovász local lemma. In this example, each event is a predicate of variables, and the events are dependent if they depend on some common events.

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
|Theorem (The local lemma)|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold:
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
:#the maximum degree of the dependency graph for the events <math>A_1,A_2,\ldots,A_n</math> is <math>d</math>, and
:::<math>ep(d+1)\le 1</math>.
:Then
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
}}

Combinatorics (Fall 2010)/Existence, the probabilistic method

2010-09-13T04:40:41Z

172.16.65.101: /* The local lemma */

== Counting arguments ==
;Circuit complexity

A '''boolean function''' is a function is the form <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , x_n</math>. A circuit has a unique node with outdegree zero, called the output node. Every other node is a gate. There are three types of gates: AND, OR (both with indegree two), and NOT (with indegree one).

Computations in Turing machines can be simulated by circuits, and any boolean function in '''P''' can be computed by a circuit with polynomially many gates. Thus, if we can find a function in '''NP''' that cannot be computed by any circuit with polynomially many gates, then '''NP'''<math>\neq</math>'''P'''.

The following theorem due to Shannon says that functions with exponentially large circuit complexity do exist.

{{Theorem
|Theorem (Shannon 1949)|
:There is a boolean function <math>f:\{0,1\}^n\rightarrow \{0,1\}</math> with circuit complexity greater than <math>\frac{2^n}{3n}</math>.
}}
{{Proof|
We first count the number of boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. There are <math>2^{2^n}</math> boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.

Then we count the number of boolean circuit with fixed number of gates.
Fix an integer <math>t</math>, we count the number of circuits with <math>t</math> gates. By the [http://en.wikipedia.org/wiki/De_Morgan's_laws De Morgan's laws], we can assume that all NOTs are pushed back to the inputs. Each gate has one of the two types (AND or OR), and has two inputs. Each of the inputs to a gate is either a constant 0 or 1, an input variable <math>x_i</math>, an inverted input variable <math>\neg x_i</math>, or the output of another gate; thus, there are at most <math>2+2n+t-1</math> possible gate inputs. It follows that the number of circuits with <math>t</math> gates is at most <math>2^t(t+2n+1)^{2t}</math>.

If <math>t=2^n/3n</math>, then
:<math>
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)<1,</math> thus, <math>2^t(t+2n+1)^{2t} < 2^{2^n}.</math>

Each boolean circuit computes one boolean function. Therefore, there must exist a boolean function <math>f</math> which cannot be computed by any circuits with <math>2^n/3n</math> gates.
}}

Note that by Shannon's theorem, not only there exists a boolean function with exponentially large circuit complexity, but ''almost all'' boolean functions have exponentially large circuit complexity.

=== Double counting ===
;Intersecting families;

An <math>\mathcal{F}\subseteq 2^S</math> is an '''intersecting''' family if for any <math>A,B\in\mathcal{F}</math> it holds that <math>A\cap B\neq\emptyset</math>.

Suppose that <math>n\ge 2k</math>. For <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math>, we can let all <math>A\in \mathcal{F}</math> contain one common element <math>a\in S</math> and <math>A-\{a\}</math> enumerates all <math>{n-1\choose k-1}</math> possible combinations of <math>(k-1)</math> elements in <math>S</math>. This gives us an intersecting family of size <math>|\mathcal{F}|={n-1\choose k-1}</math>.

The following theorem says that this is the largest possible cardinality an intersecting <math>\mathcal{F}</math> can achieve. The theorem was first proved by Erdős, Ko, and Rado in 1938, but published 23 years later. It is a fundamental result in the area of extremal set theory, which studies the maximum (or minimum) possible cardinality of a set system satisfying certain structural assumption. In this example, the structural assumption is intersecting.

Here we present a probabilistic proof by Katona.

{{Theorem
|Theorem (Erdős-Ko-Rado 1961)|
:Let <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>|S|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is an intersecting family then <math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}
{{Proof| (due to Katona 1972).

Without loss of generality, let <math>S=[n]</math>.
For <math>i\in[n]</math>, let <math>A_i=\{(i+j)\bmod n\mid j\in[k]\}</math>. Then we make the following claim.

:'''Claim 1:''' <math>\mathcal{F}</math> can contain at most <math>k</math> many <math>A_i</math>.
The claim can be easily proved by observing that for any <math>i,j\in[n]</math> that <math>i<j</math>, <math>A_i</math> and <math>A_j</math> are disjoint if <math>j-i>k</math>, thus in order to make <math>\mathcal{F}</math> intersecting, all <math>A_i,A_j\in\mathcal{F}</math> have <math>|i-j|\le k</math>. This is violated once there are more than <math>k</math> many <math>A_i</math> in <math>\mathcal{F}</math>.

Now we prove the Erdős-Ko-Rado theorem. Let a permutation <math>\sigma</math> of <math>[n]</math> and an integer <math>i\in[n]</math> be chosen uniformly and independently at random. Let
:<math>R=\{\sigma((i+j)\bmod n)\mid j\in[k]\}, \quad\mbox{ or equivalently }R=\sigma(A_i)</math>.
By Claim 1, for any fixed permutation <math>\sigma</math>, the family <math>\mathcal{F}</math> can contain at most <math>k</math> of the sets <math>\sigma(A_i)</math>, thus conditioning on any particular <math>\sigma</math>, <math>\Pr[R\in\mathcal{F}\mid \sigma]\le\frac{k}{n}</math>. Hence
:<math>
\Pr[R\in\mathcal{F}]\le\frac{k}{n}.
</math>
On the other hand, by our construction, <math>R</math> is uniformly chosen from <math>{S\choose k}</math>, thus
:<math>
\Pr[R\in\mathcal{F}]=\frac{|\mathcal{F}|}{{n\choose k}}.
</math>
Therefore,
<math>
|\mathcal{F}|\le\frac{k}{n}{n\choose k}={n-1\choose k-1}.
</math>
}}

== The Probabilistic Method ==

Suppose we want prove the existence of mathematic objects with certain properties. One way to do so is to explicitly construct such an object. This kind of proofs can be interpreted as ''deterministic algorithms'' which find the object with desirable properties.

The probabilistic method provides another way of proving the existence of objects: instead of explicitly constructing an object, we define a probability space of objects in which the probability is positive that a randomly selected object has the required property.

The basic principle of the probabilistic method is very simple, and can be stated in intuitive ways:
*If an object chosen randomly from a universe satisfies a property with positive probability, then there must be an object in the universe that satisfies that property.
:For example, for a ball(the object) randomly chosen from a box(the universe) of balls, if the probability that the chosen ball is blue(the property) is >0, then there must be a blue ball in the box.
*Any random variable assumes at least one value that is no smaller than its expectation, and at least one value that is no greater than the expectation.
:For example, if we know the average height of the students in the class is <math>\ell</math>, then we know there is a students whose height is at least <math>\ell</math>, and there is a student whose height is at most <math>\ell</math>.

Although the idea of the probabilistic method is simple, it provides us a powerful tool for existential proof. In same cases, the proof itself is a ''randomized algorithm'', and if we are lucky, the algorithm could be very efficient.

=== Sampling ===
;Ramsey number

Recall the Ramsey theorem which states that in a meeting of at least six people, there are either three people knowing each other or three people not knowing each other. In graph theoretical terms, this means that no matter how we color the edges of <math>K_6</math> (the complete graph on six vertices), there must be a '''monochromatic''' <math>K_3</math> (a triangle whose edges have the same color).

Generally, the '''Ramsey number''' <math>R(k,\ell)</math> is the smallest integer <math>n</math> such that in any two-coloring of the edges of a complete graph on <math>n</math> vertices <math>K_n</math> by red and blue, either there is a red <math>K_k</math> or there is a blue <math>K_\ell</math>.

Ramsey showed in 1929 that <math>R(k,\ell)</math> is finite for any <math>k</math> and <math>\ell</math>. It is extremely hard to compute the exact value of <math>R(k,\ell)</math>. Here we give a lower bound of <math>R(k,k)</math> by the probabilistic method.

{{Theorem
|Theorem (Erdős 1947)|
:If <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math> then it is possible to color the edges of <math>K_n</math> with two colors so that there is no monochromatic <math>K_k</math> subgraph.
}}
{{Proof| Consider a random two-coloring of edges of <math>K_n</math> obtained as follows:
* For each edge of <math>K_n</math>, independently flip a fair coin to decide the color of the edge.

For any fixed set <math>S</math> of <math>k</math> vertices, let <math>\mathcal{E}_S</math> be the event that the <math>K_k</math> subgraph induced by <math>S</math> is monochromatic. There are <math>{k\choose 2}</math> many edges in <math>K_k</math>, therefore
:<math>\Pr[\mathcal{E}_S]=2\cdot 2^{-{k\choose 2}}=2^{1-{k\choose 2}}.</math>

Since there are <math>{n\choose k}</math> possible choices of <math>S</math>, by the union bound
:<math>
\Pr[\exists S, \mathcal{E}_S]\le {n\choose k}\cdot\Pr[\mathcal{E}_S]={n\choose k}\cdot 2^{1-{k\choose 2}}.
</math>
Due to the assumption, <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math>, thus there exists a two coloring that none of <math>\mathcal{E}_S</math> occurs, which means there is no monochromatic <math>K_k</math> subgraph.
}}

For <math>k\ge 3</math> and we take <math>n=\lfloor2^{k/2}\rfloor</math>, then
:<math>
\begin{align}
{n\choose k}\cdot 2^{1-{k\choose 2}}
&<
\frac{n^k}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&\le
\frac{2^{k^2/2}}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
&=
\frac{2^{1+\frac{k}{2}}}{k!}\\
&<1.
\end{align}
</math>
By the above theorem, there exists a two-coloring of <math>K_n</math> that there is no monochromatic <math>K_k</math>. Therefore, the Ramsey number <math>R(k,k)>\lfloor2^{k/2}\rfloor</math> for all <math>k\ge 3</math>.

Note that for sufficiently large <math>k</math>, if <math>n= \lfloor 2^{k/2}\rfloor</math>, then the probability that there exists a monochromatic <math>K_k</math> is bounded by
:<math>
{n\choose k}\cdot 2^{1-{k\choose 2}}
<
\frac{2^{1+\frac{k}{2}}}{k!}
\ll 1,
</math>
which means that a random two-coloring of <math>K_n</math> is very likely not to contain a monochromatic <math>K_{2\log n}</math>. This gives us a very simple randomized algorithm for finding a two-coloring of <math>K_n</math> without monochromatic <math>K_{2\log n}</math>.

;Blocking number
Let <math>S</math> be a set. Let <math>2^{S}=\{A\mid A\subseteq S\}</math> be the power set of <math>S</math>, and let <math>{S\choose k}=\{A\mid A\subseteq S\mbox{ and }|A|=k\}</math> be the '''<math>k</math>-uniform''' of <math>S</math>.

We call <math>\mathcal{F}</math> a '''set family''' (or a '''set system''') with '''ground set''' <math>S</math> if <math>\mathcal{F}\subseteq 2^{S}</math>. The members of <math>\mathcal{F}</math> are subsets of <math>S</math>.

Given a set family <math>\mathcal{F}</math> with ground set <math>S</math>,
a set <math>T\subseteq S</math> is a '''blocking set''' of <math>\mathcal{F}</math> if all <math>A\in\mathcal{F}</math> have <math>A\cap T\neq \emptyset</math>, i.e. <math>T</math> intersects (blocks) all member set of <math>\mathcal{F}</math>.

{{Theorem
|Theorem|
:Given a set family <math>\mathcal{F}\subseteq{S\choose k}</math>, where <math>m=|\mathcal{F}|</math> and <math>n=|S|</math>, <math>\mathcal{F}</math> has a blocking set of size <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math>.
}}
{{Proof| Let <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>. Let <math>T</math> be a set chosen uniformly at random from <math>{S\choose \tau}</math>. We show that <math>T</math> is a blocking set of <math>\mathcal{F}</math> with a probability >0.

Fix any <math>A\in\mathcal{F}</math>. Recall that <math>\mathcal{F}\subseteq{S\choose k}</math>, thus <math>|A|=k</math>. And
:<math>
\begin{align}
\Pr[A\cap T=\emptyset]
&=
\frac{\left|{S-A\choose \tau}\right|}{\left|{S\choose \tau}\right|}\\
&=
\frac{{n-k\choose \tau}}{{n\choose\tau}}\\
&=
\frac{(n-k)\cdot(n-k-1)\cdots(n-k-\tau+1)}{n\cdot(n-1)\cdots(n-\tau+1)}\\
&<
\left(1-\frac{k}{n}\right)^{\tau}\\
&\le
\exp\left(-\frac{k\tau}{n}\right)\\
&\le
\frac{1}{m}.
\end{align}
</math>
By the union bound, the probability that there exists an <math>A\in\mathcal{F}</math> that misses <math>T</math>
:<math>
\Pr[\exists A\in\mathcal{F}, A\cap T=\emptyset]\le m\Pr[A\cap T=\emptyset]<m\cdot\frac{1}{m}=1.
</math>
Thus, the probability that <math>T</math> is a blocking set
:<math>
\Pr[\forall A\in\mathcal{F}, A\cap T\neq\emptyset]>0.
</math>
There exists a blocking set of size <math>\tau=\left\lceil\frac{n\ln m}{k}\right\rceil</math>.
}}

The theorem also hints us to a randomized algorithm. In order to make the algorithm efficient, we relax the size of <math>T</math> to <math>\tau=\frac{2n\ln m}{k}</math>. Uniformly choose <math>\tau</math> elements from <math>S</math> to form the set <math>T</math>, by the above analysis, the probability that <math>T</math> is NOT a blocking set is at most
:<math>
m\exp\left(-\frac{n\tau}{k}\right)=m\exp(-2\ln m)=\frac{1}{m}.
</math>
Thus, a blocking set is found with high probability.

=== Linearity of expectation ===

;Maximum cut

Given an undirected graph <math>G(V,E)</math>, a set <math>C</math> of edges of <math>G</math> is called a '''cut''' if <math>G</math> is disconnected after removing the edges in <math>C</math>. We can represent a cut by <math>c(S,T)</math> where <math>(S,T)</math> is a bipartition of the vertex set <math>V</math>, and <math>c(S,T)=\{uv\in E\mid u\in S,v\in T\}</math> is the set of edges crossing between <math>S</math> and <math>T</math>.

We have seen how to compute min-cut: either by deterministic max-flow algorithm, or by Karger's randomized algorithm. On the other hand, max-cut is hard to compute, because it is '''NP-complete'''. Actually, the weighted version of max-cut is among the [http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems Karp's 21 NP-complete problems].

We now show by the probabilistic method that a max-cut always has at least half the edges.

{{Theorem
|Theorem|
:Given an undirected graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges, there is a cut of size at least <math>\frac{m}{2}</math>.
}}
{{Proof| Enumerate the vertices in an arbitrary order. Partition the vertex set <math>V</math> into two disjoint sets <math>S</math> and <math>T</math> as follows.
:For each vertex <math>v\in V</math>,
:* independently choose one of <math>S</math> and <math>T</math> with equal probability, and let <math>v</math> join the chosen set.

For each vertex <math>v\in V</math>, let <math>X_v\in\{S,T\}</math> be the random variable which represents the set that <math>v</math> joins. For each edge <math>uv\in E</math>, let <math>Y_{uv}</math> be the 0-1 random variable which indicates whether <math>uv</math> crosses between <math>S</math> and <math>T</math>. Clearly,
:<math>
\Pr[Y_{uv}=1]=\Pr[X_u\neq X_v]=\frac{1}{2}.
</math>

The size of <math>c(S,T)</math> is given by <math>Y=\sum_{uv\in E}Y_{uv}</math>. By the linearity of expectation,
:<math>
\mathbf{E}[Y]=\sum_{uv\in E}\mathbf{E}[Y_{uv}]=\sum_{uv\in E}\Pr[Y_{uv}=1]=\frac{m}{2}.
</math>
Therefore, there exist a bipartition <math>(S,T)</math> of <math>V</math> such that <math>|c(S,T)|\ge\frac{m}{2}</math>, i.e. there exists a cut of <math>G</math> which contains at least <math>\frac{m}{2}</math> edges.
}}

;Maximum satisfiability

Suppose that we have a number of boolean variables <math>x_1,x_2,\ldots,\in\{\mathrm{true},\mathrm{false}\}</math>. A '''literal''' is either a variable <math>x_i</math> itself or its negation <math>\neg x_i</math>. A logic expression is a '''conjunctive normal form (CNF)''' if it is written as the conjunction(AND) of a set of '''clauses''', where each clause is a disjunction(OR) of literals. For example:
:<math>
(x_1\vee \neg x_2 \vee \neg x_3)\wedge (\neg x_1\vee \neg x_3)\wedge (x_1\vee x_2\vee x_4)\wedge (x_4\vee \neg x_3)\wedge (x_4\vee \neg x_1).
</math>

The satisfiability (SAT) problem ask whether the CNF is satisfiable, i.e. there exists an assignment of variables to the values of true and false so that all clauses are true. The maximum satisfiability (MAXSAT) is the optimization version of SAT, which ask for an assignment that the number of satisfied clauses is maximized.

SAT is the first problem known to be '''NP-complete''' (the Cook-Levin theorem). MAXSAT is also '''NP-complete'''. We then see that there always exists a roughly good truth assignment which satisfies half the clauses.

{{Theorem
|Theorem|
:For any set of <math>m</math> clauses, there is a truth assignment that satisfies at least <math>\frac{m}{2}</math> clauses.
}}
{{Proof| For each variable, independently assign a random value in <math>\{\mathrm{true},\mathrm{false}\}</math> with equal probability. For the <math>i</math>th clause, let <math>X_i</math> be the random variable which indicates whether the <math>i</math>th clause is satisfied. Suppose that there are <math>k</math> literals in the clause. The probability that the clause is satisfied is
:<math>\Pr[X_k=1]\ge(1-2^{-k})\ge\frac{1}{2}</math>.

Let <math>X=\sum_{i=1}^m X_i</math> be the number of satisfied clauses. By the linearity of expectation,
:<math>
\mathbf{E}[X]=\sum_{i=1}^{m}\mathbf{E}[X_i]\ge \frac{m}{2}.
</math>
Therefore, there exists an assignment such that at least <math>\frac{m}{2}</math> clauses are satisfied.
}}

=== Alterations ===
;Independent sets
An independent set of a graph is a set of vertices with no edges between them. The following theorem gives a lower bound on the size of the largest independent set.
{{Theorem
|Theorem|
:Let <math>G(V,E)</math> be a graph on <math>n</math> vertices with <math>m</math> edges. Then <math>G</math> has an independent set with at least <math>\frac{n^2}{4m}</math> vertices.
}}
{{Proof| Let <math>S</math> be a set of vertices constructed as follows:
:For each vertex <math>v\in V</math>:
:* <math>v</math> is included in <math>S</math> independently with probability <math>p</math>,
<math>p</math> to be determined.

Let <math>X=|S|</math>. It is obvious that <math>\mathbf{E}[X]=np</math>.

For each edge <math>e\in E</math>, let <math>Y_{e}</math> be the random variable which indicates whether both endpoints of <math></math> are in <math>S</math>.
:<math>
\mathbf{E}[Y_{uv}]=\Pr[u\in S\wedge v\in S]=p^2.
</math>
Let <math>Y</math> be the number of edges in the subgraph of <math>G</math> induced by <math>S</math>. It holds that <math>Y=\sum_{e\in E}Y_e</math>. By linearity of expectation,
:<math>\mathbf{E}[Y]=\sum_{e\in E}\mathbf{E}[Y_e]=mp^2</math>.

Note that although <math>S</math> is not necessary an independent set, it can be modified to one if for each edge <math>e</math> of the induced subgraph <math>G(S)</math>, we delete one of the endpoint of <math>e</math> from <math>S</math>. Let <math>S^*</math> be the resulting set. It is obvious that <math>S^*</math> is an independent set since there is no edge left in the induced subgraph <math>G(S^*)</math>.

Since there are <math>Y</math> edges in <math>G(S)</math>, there are at most <math>Y</math> vertices in <math>S</math> are deleted to make it become <math>S^*</math>. Therefore, <math>|S^*|\ge X-Y</math>. By linearity of expectation,
:<math>
\mathbf{E}[|S^*|]\ge\mathbf{E}[X-Y]=\mathbf{E}[X]-\mathbf{E}[Y]=np-mp^2.
</math>
The expectation is maximized when <math>p=\frac{n}{2m}</math>, thus
:<math>
\mathbf{E}[|S^*|]\ge n\cdot\frac{n}{2m}-m\left(\frac{n}{2m}\right)^2=\frac{n^2}{4m}.
</math>
There exists an independent set which contains at least <math>\frac{n^2}{4m}</math> vertices.
}}

The proof actually propose a randomized algorithm for constructing large independent set:

{{Theorem
|Algorithm|
Given a graph on <math>n</math> vertices with <math>m</math> edges, let <math>d=\frac{2m}{n}</math> be the average degree.
#For each vertex <math>v\in V</math>, <math>v</math> is included in <math>S</math> independently with probability <math>\frac{1}{d}</math>.
#For each remaining edge in the induced subgraph <math>G(S)</math>, remove one of the endpoints from <math>S</math>.
}}

Let <math>S^*</math> be the resulting set. We have shown that <math>S^*</math> is an independent set and <math>\mathbf{E}[|S^*|]\ge\frac{n^2}{4m}</math>.

== The Lovász Local Lemma ==

Consider a set of "bad" events <math>A_1,A_2,\ldots,A_n</math>. Suppose that <math>\Pr[A_i]\le p</math> for all <math>1\le i\le n</math>. We want to show that there is a situation that none of the bad events occurs. Due to the probabilistic method, we need to prove that
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0.
</math>
;Case 1<nowiki>: mutually independent events.</nowiki>
If all the bad events <math>A_1,A_2,\ldots,A_n</math> are mutually independent, then
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge(1-p)^n>0,
</math>
for any <math>p<1</math>.

;Case 2<nowiki>: arbitrarily dependent events.</nowiki>
On the other hand, if we put no assumption on the dependencies between the events, then by the union bound (which holds unconditionally),
:<math>
\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=1-\Pr\left[\bigvee_{i=1}^n A_i\right]\ge 1-np,
</math>
which is not an interesting bound for <math>p\ge\frac{1}{n}</math>. If we make no further assumption on the dependencies between the events, this bound is tight.

;Example
:Consider that a ball is uniformly thrown into one of the <math>(n+1)</math> bins. Let the "bad" events <math>A_1,A_2,\ldots,A_n</math> be defined as that <math>A_i</math> represents that the ball falls into the <math>i</math>th bin. The only good event is that the ball falls into the <math>(n+1)</math>th bin. Clearly, <math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=1-n\cdot\frac{1}{n+1}</math>. Thus the above union bound is achieved.

This example shows that dependencies between the events could cause troubles.

We would like to know what is going on between the two extreme cases: mutually independent events, and arbitrarily dependent events. The Lovász local lemma provides such a tool.

=== The local lemma ===
The local lemma is powerful tool for showing the possibility of rare event under limited dependencies. The structure of dependencies between a set of events is described by a '''dependency graph'''.

{{Theorem
|Definition|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set 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>.
}}

;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>.

This construction gives a general framework for the probability spaces with limited dependencies and is central to the constructive proof of the Lovász local lemma. In this example, each event is a predicate of variables, and the events are dependent if they depend on some common events.

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
|Theorem (The local lemma)|
:Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold:
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
:#the maximum degree of the dependency graph for the events <math>A_1,A_2,\ldots,A_n</math> is <math>d</math>, and
:::<math>ep(d+1)\le 1</math>.
:Then
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
}}

Randomized Algorithms (Spring 2010)/Approximate counting, linear programming

2010-05-24T08:49:25Z

172.16.65.36: /* Approximate Counting */

== Counting Problems ==

=== Complexity model ===

=== FPRAS ===

== Approximate Counting ==
Let us consider the following abstract problem.

Let <math>U</math> be a finite set of known size, and let <math>G\subseteq U</math>. We want to compute the size of <math>G</math>, namely <math>|G|</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 algorithm:
*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
::<math>Z=\frac{|U|}{N}\sum_{i=1}^N Y_i.</math>

It is easy to see that <math>\mathbf{E}[Z]=|G|</math> and we might hope that with high probability the value of <math>Z</math> is close to <math>|G|</math>. 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>

The following theorem states that the probabilistic accuracy of the estimation depends on the number of samples and the ratio between <math>|G|</math> and <math>|U|</math>

{|border="1"
|'''Theorem (estimator theorem)'''
:Let <math>\alpha=\frac{|G|}{|U|}</math>. Then the Monte Carlo method yields an <math>\epsilon</math>-approximation to <math>|G|</math> with probability at least <math>1-\delta</math> provided
::<math>N\ge\frac{4}{\epsilon \alpha}\ln\frac{2}{\delta}</math>.
|}
'''Proof''': Use the Chernoff bound.

<math>\square</math>

A counting algorithm for the set <math>G</math> has to deal with the following three complications:
* Implement the membership oracle <math>\mathcal{O}</math>. This is usually straightforward, or assumed by the model.
* Implement the uniform sampler <math>\mathcal{U}</math>. As we have seen, this is usually approximated by random walks. How to design the random walk and bound its mixing rate is usually technical challenging, if possible at all.
* Deal with exponentially small <math>\alpha=\frac{|G|}{|U|}</math>. This requires us to cleverly choose the universe <math>U</math>. Sometimes this needs some nontrivial ideas.

=== 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 '''#P-complete'''.

Naively applying the Monte Carlo method will not give a good answer. 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.

;The union of sets problem
We reformulate the DNF counting problem in a more abstract framework, called the '''union of sets''' problem.

Let <math>V</math> be a finite universe. We are given <math>m</math> subsets <math>H_1,H_2,\ldots,H_m\subseteq V</math>. The following assumptions hold:
*For all <math>i</math>, <math>|H_i|</math> is computable in poly-time.
*It is possible to sample uniformly from each individual <math>H_i</math>.
*For any <math>x\in V</math>, it can be determined in poly-time whether <math>x\in H_i</math>.

The goal is to compute the size of <math>H=\bigcup_{i=1}^m H_i</math>.

DNF counting can be interpreted in this general framework as follows. Suppose that the DNF formula <math>\phi</math> is defined on <math>n</math> variables, and <math>\phi</math> contains <math>m</math> clauses <math>C_1,C_2,\ldots,C_m</math>, where clause <math>C_i</math> has <math>k_i</math> literals. Without loss of generality, we assume that in each clause, each variable appears at most once.
* <math>V</math> is the set of all assignments.
*Each <math>H_i</math> is the set of satisfying assignments for the <math>i</math>-th clause <math>C_i</math> of the DNF formular <math>\phi</math>. Then the union of sets <math>H=\bigcup_i H_i</math> gives the set of satisfying assignments for <math>\phi</math>.
* Each clause <math>C_i</math> is a conjunction (AND) of literals. It is not hard to see that <math>|H_i|=2^{n-k_i}</math>, which is efficiently computable.
* Sampling from an <math>H_i</math> is simple: we just fix the assignments of the <math>k_i</math> literals of that clause, 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 can choose a unique representative among the multiple instances <math>(x,i)\in U</math> for the same <math>x\in H</math>, by choosing the <math>(x,i)</math> with the minimum <math>i</math>, and form a set <math>G</math>.

Formally, <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>.

It is obvious that <math>G\subseteq U</math> and
:<math>|G|=|H|</math>.

Therefore, estimation of <math>|H|</math> is reduced to estimation of <math>|G|</math> with <math>G\subseteq U</math>. Then <math>|G|</math> can have an <math>\epsilon</math>-approximation with probability <math>(1-\delta)</math> in poly-time, if we can uniformly sample from <math>U</math> and <math>|G|/|U|</math> is suitably small.

An uniform sample from <math>U</math> can be implemented as follows:
* 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>. The above sampling procedure is poly-time because each <math>|H_i|</math> can be computed in poly-time, and sampling uniformly from each <math>H_i</math> is poly-time.

We now only need to lower bound the ratio
:<math>\alpha=\frac{|G|}{|U|}</math>.

We claim that
:<math>\alpha\ge\frac{1}{m}</math>.
It is easy to see this, because each <math>x\in H</math> has at most <math>m</math> instances of <math>(x,i)</math> in <math>U</math>, and we already know that <math>|G|=|H|</math>.

Due to the estimator theorem, this needs <math>\frac{4m}{\epsilon}\ln\frac{2}{\delta}</math> uniform random samples from <math>U</math>.

This gives the coverage algorithm for the abstract problem of the union of sets. The DNF counting is a special case of it.

=== Permanents and perfect matchings ===

Let <math>U=\{u_1,u_2,\ldots,u_n\}</math> and <math>V=\{v_1,v_2,\ldots,v_n\}</math>. Consider a bipartite graph <math>G(U,V,E)</math>. An <math>M\subseteq E</math> is a '''perfect matching''' of <math>G</math> if every vertex of <math>G</math> has exactly one edge in <math>M</math> adjacent to it.

Given a bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math>, we want to count the number of perfect matchings of <math>G</math>. This problem can be reduced to computing the '''permanent''' of a square matrix.

{|border="1"
|'''Definition (permanent)'''
:Let <math>Q</math> be an <math>n\times n</math> matrix. The '''permanent''' of the matrix is defined as
::<math>\mathrm{per}(Q)=\sum_{\pi\in\mathbb{S}_n}\prod_{i=1}^n Q_{i,\pi(i)}</math>,
:where <math>\mathbb{S}_n</math> is the symmetric group of permutation of size <math>n</math>.
|}

If we multiply each term of the sum the sign of the permutation, then it gives us the determinant of the matrix,
:<math>\det(Q)=\sum_{\pi\in\mathbb{S}_n}\sgn(\pi)\prod_{i=1}^n Q_{i,\pi(i)}</math>,
where <math>\sgn(\pi)</math>, the sign of a permutation, is either <math>-1</math> or <math>+1</math>, according to whether the minimum number of pair-wise interchanges to achieve <math>\pi</math> from <math>(1,2,\ldots,n)</math> is odd or even.

Unlike the determinants, which are computable in poly-time, permanents are hard to compute, as permanents can be used to count the number of perfect matchings in a bipartite graph, which is '''#P-complete'''.

A bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math> can be represented by an <math>n\times n</math> matrix <math>Q</math> with 0-1 entries as follows:
* Each row of <math>Q</math> corresponds to a vertex in <math>U</math> and each column of <math>Q</math> corresponds to a vertex in <math>V</math>.
::<math>Q_{ij}=\begin{cases}
1 & \mbox{if }i\sim j,\\
0 & \mbox{otherwise}.
\end{cases}</math>
Note the subtle difference between the definition of <math>Q</math> and the adjacency matrix.

Each perfect matching corresponds to a permutation <math>\pi</math> of <math>U</math> with <math>(u,\pi(u))\in E</math> for every <math>u\in U</math>, which corresponds to a permutation <math>\pi\in\mathbb{S}_n</math> with <math>\prod_{i=1}^n Q_{i,\pi(i)}=1</math>. It is than easy to see that <math>\mathrm{per}(Q)</math> gives the number of perfect matchings in the bipartite graph <math>G</math>.

It is known that counting the number of perfect matchings in a bipartite graph is '''#P-hard'''. Since this problem can be reduced to computing the permanent, thus the problem of computing the permanents is also '''#P-hard'''.

Now we show that with randomization, we can approximate the number of perfect matchings in a bipartite graph. In particular, we will give an FPRAS for counting the perfect matchings in a dense bipartite graph.

==== The Jerrum-Sinclair algorithm ====
Fix a bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math>. Let <math>\mathcal{M}_k</math> be the set of matchings of size <math>k</math> in <math>G</math>, and let <math>m_k=|\mathcal{M}_k|</math>. Thus, <math>\mathcal{M}_k</math> is the set of perfect matchings in <math>G</math>, and our goal is to compute <math>m_n</math>.

Let <math>r_k=\frac{m_k}{m_{k-1}}</math> for <math>1<k\le n</math>. Then
:<math>m_k=m_{k-1}r_k</math>,
which gives us a recursion to compute the <math>m_n</math>, as
:<math>m_n=m_{1}\frac{m_2}{m_1}\cdot\frac{m_3}{m_2}\cdots\frac{m_n}{m_{n-1}}=m_1\prod_{k=2}^n r_k</math>,
where <math>m_1=|\mathcal{M}_1|</math> is the number of matchings of size 1 in the bipartite graph <math>G</math>, which is just the number of edges in <math>G</math>. Therefore, <math>m_n</math> can be computed once we know <math>r_k</math> for <math>1<k\le n</math>.

Each <math>r_k</math> can be estimated by sampling uniformly from the set <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>. The algorithm for estimating <math>m_n</math> is outlined as:
# For each <math>1<k\le n</math>, have an FPRAS for computing the <math>r_k</math> by uniform sampling sufficiently many members from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math> as
::*uniformly sample <math>N</math> matching from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>, for some polynomially large <math>N</math>;
::* assuming that there are <math>X</math> sampled matchings of size <math>k</math>, return <math>r_k</math> as <math>r_k=\frac{X}{N-X}</math>.
:2. Compute <math>m_n</math> as <math>m_n=m_1\prod_{k=2}^n r_k</math>, where <math>m_1=|E|</math>.

There are several issues that we have to deal with in order to have a fully functional FPRAS for counting perfect matchings.
* By taking the product of <math>r_k</math>'s, the errors for individual <math>r_k</math>'s add up.
* In order to accurately estimate <math>r_k</math> by sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>, the ratio <math>r_k</math> should be within the range <math>\left[\frac{1}{\alpha},\alpha\right]</math> for some <math>\alpha</math> within polynomial of <math>n</math>.
* Implement the uniform sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>.

;Estimator for each <math>r_k</math>

; Accumulation of errors

; Near-uniform sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>
In the last lecture, we have shown that by random walk, we can sample a near-uniform member of <math>\mathcal{M}_n\cup\mathcal{M}_{n-1}</math> in poly-time.

=== Volume estimation ===
We consider the problem of computing the volume of a given [http://en.wikipedia.org/wiki/Convex_body convex body] <math>K</math> in <math>n</math> dimensions.

We use <math>\Upsilon(K)\,</math> to denote the volume of the convex body <math>K</math>. Abstractly, the problem is that given as input a convex body <math>K</math> in <math>n</math> dimensions, return the <math>\Upsilon(K)\,</math>.

We should be more specific about the input model. Since we allow an arbitrary convex body as input, it is not even clear how to describe the body. We assume that <math>K</math> is described by means of a '''membership oracle''' <math>\mathcal{O}</math>, such that for a '''query''' of an <math>n</math>-dimensional point <math>x</math>, <math>\mathcal{O}(x)</math> indicates whether <math>x\in K</math>.

For example, the <math>n</math>-dimensional convex body defined by the intersection of <math>m</math> half-spaces, which is the set of feasible solutions to a system of <math>m</math> linear constraints, can be described as
:<math>A x\le \boldsymbol{b}</math>,
for some <math>m\times n</math> matrix <math>A</math>, and <math>m</math>-dimensional vector <math>b</math>. For a query of an <math>x</math>, the membership oracle <math>\mathcal{O}</math> just check whether <math>Ax\le b</math>.

For deterministic algorithms, there are negative news for this problem.

{|border="1"
|'''Theorem (Bárány-Füredi 1987)'''
:Suppose that a deterministic poly-time algorithm uses the membership oracle for a convex body <math>K</math> in <math>n</math> dimensions, and generates an upper bound <math>\Upsilon_u\,</math> and a lower bound <math>\Upsilon_\ell\,</math> on the volume <math>\Upsilon(K)\,</math> of <math>K</math>. Then, there is a convex body <math>K</math> and a constant <math>c</math> such that
::<math>\frac{\Upsilon_u}{\Upsilon_\ell}\ge c\left(\frac{n}{\log n}\right)^n</math>.
|}
That is said, with deterministic algorithms, we cannot even approximate the volume within a wildly loose range.

Dyer-Frieze-Kannan come up with an idea of estimating the volume of <math>K</math> by sampling near-uniformly from convex sets. They reduce the problem of computing approximately the volume of convex bodies to this sampling problem and thus give the first FPRAS for the volume of convex bodies.

For any convex body <math>K</math>, it encloses some <math>n</math>-dimensional ball and is also enclosed by another ball with larger radius. We assume that the convex body <math>K</math> encloses the unit ball around the origin, and is enclosed by a larger ball round the origin with polynomially large radius. Formally, we assume that
:<math>B(0,1)\subseteq K\subseteq B(0,n^c)</math> for some constant <math>c</math>,
where <math>B(p,r)</math> denotes a ball of radius <math>r</math> with <math>p</math> as center, i.e. <math>B(p,r)=\{x\mid \|x-p\|\le r \}</math>. We can make this assumption because it is known that for any convex body <math>K</math>, there exists a linear transformation <math>\tau</math> which can be found within poly-time such that <math>\tau K</math> transforms the <math>K</math> to a convex body that satisfies the assumption, and preserves the ratio of the volumes of the balls to the convex body.

The volumes of the balls are easy to compute. If only the ratio between the convex body and the ball which encloses it, is sufficiently large, then we can apply the Monte Carlo method to estimate <math>\Upsilon(K)\,</math> by uniformly sampling from the ball.

However, in high-dimension, the ratio between the volume of a convex body and the volume of ball which encloses it, can be exponentially small. This is caused by the so called the "[http://en.wikipedia.org/wiki/Curse_of_dimensionality curse of dimensionality]".

Instead of having an outer ball and an inner ball, we define a sequence of balls:
:<math>B_0=B(0,\lambda^0), B_1=B(0,\lambda^1), B_2=B(0,\lambda^2),\ldots, B_m=B(0,\lambda^m)</math>,
where <math>\lambda=(1+\frac{1}{n})</math> and <math>m</math> is the smallest positive integer such that <math>\lambda^m\ge n^c</math>. Therefore, the inner ball <math>B(0,1)=B_0</math>, the outer ball <math>B(0,n^c)\subseteq B_m</math>, and <math>m</math> is within polynomial of <math>n</math>. In fact, <math>m\approx cn\ln n</math>.

This sequence of balls naturally defines a sequence of convex bodies by intersections as <math>K_i=B_i\cap K</math>. It is obvious that
:<math>B(0,1)=K_0\subseteq K_1\subseteq K_2\subseteq\cdots\subseteq K_m=K</math>.
Balls are convex, and since the intersection of convex bodies is still convex, the sequence of <math>K_i</math> is a sequence of convex bodies.

We have the telescopic product:
:<math>
\frac{\Upsilon(K_0)}{\Upsilon(K_1)}\cdot\frac{\Upsilon(K_1)}{\Upsilon(K_2)}\cdots\frac{\Upsilon(K_{m-1})}{\Upsilon(K_m)}=\frac{\Upsilon(K_0)}{\Upsilon(K_m)}=\frac{\Upsilon(B(0,1))}{\Upsilon(K)}.
</math>
Therefore, the volume <math>\Upsilon(K)\,</math> can be computed as
:<math>\Upsilon(K)=\Upsilon(B(0,1))\cdot\prod_{i=1}^{m}\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math>.

The volume of unite ball <math>\Upsilon(B(0,1))\,</math> can be precisely computed in poly-time. Each <math>\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math> is computed by near-uniform sampling from <math>K_{i}</math>, which encloses <math>K_{i-1}</math>.

Another observation is that the ratio <math>\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math> is well-bounded. Recall that <math>K_i=B(0,\lambda^i)\cap K</math> where <math>\lambda=(1+\frac{1}{n})</math>. It can be proved that in <math>n</math> dimensions, the volume of <math>K_i</math> is at most <math>\lambda^n</math> times the <math>K_{i-1}</math>, thus the ratio <math>\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math> is at most <math>\lambda^n=O(1)</math>. By the estimator theorem, we can have an FPRAS for the ratio <math>\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math> if we can uniformly sample from <math>K_i</math>.

Uniformly sampling from an arbitrary convex body is replaced by near-uniform sampling achieved by random walks. In the original walk of Dyer-Frieze-Kannan, they consider the random walk over <math>n</math>-dimensional discrete grid points enclosed by <math>K</math>, and prove that the walk is rapid mixing. This gives us the first FPRAS for volume estimation which runs in <math>\tilde{O}(n^{23})</math>, where <math>\tilde{O}(\cdot)</math> ignores the polylogarithmic factors.

The time bound was later improved by a series of works, each introducing some new ideas.

{|border="1"
| || complexity || new ingredient(s)
|-
| Dyer-Frieze-Kannan 1991 || align="center" | <math>n^{23}</math> || everything
|-
| Lovász-Simonovits 1990 || align="center" | <math>n^{16}</math> || localization lemma
|-
| Applegate-Kannan 1990 || align="center" | <math>n^{10}</math> || logconcave sampling
|-
| Lovász 1990 || align="center" | <math>n^{10}</math> || ball walk
|-
| Dyer-Frieze 1991 || align="center" | <math>n^8</math> || better error analysis
|-
| Lovász-Simonovits 1993 || align="center" | <math>n^7</math> || many improvements
|-
| Kannan-Lovász-Simonovits 1997 || align="center" | <math>n^5</math> || isotropy, speedy walk
|-
| Lovász-Vempala 2003 || align="center" | <math>n^4</math> || simulated annealing, hit-and-run
|-
|}
(cited from "Geometric Random Walks: A Survey" by Santosh Vempala.)

The current best upper bound is <math>\tilde{O}(n^4)</math> due to Lovász and Vempala in 2003. It is conjectured that the optimal bound is <math>\Theta(n^3)</math>.

== Linear Programming ==

=== LP and convex polytopes ===

=== The simplex algorithms ===

=== An LP solver via random walks ===

Randomized Algorithms (Spring 2010)/Approximate counting, linear programming

2010-05-24T08:49:07Z

172.16.65.36: /* Approximate Counting */

== Counting Problems ==

=== Complexity model ===

=== FPRAS ===

== Approximate Counting ==
Let us consider the following abstract problem.

Let <math>U</math> be a finite set of known size, and let <math>G\subseteq U</math>. We want to compute the size of <math>G</math>, <math>|G|</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 algorithm:
*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
::<math>Z=\frac{|U|}{N}\sum_{i=1}^N Y_i.</math>

It is easy to see that <math>\mathbf{E}[Z]=|G|</math> and we might hope that with high probability the value of <math>Z</math> is close to <math>|G|</math>. 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>

The following theorem states that the probabilistic accuracy of the estimation depends on the number of samples and the ratio between <math>|G|</math> and <math>|U|</math>

{|border="1"
|'''Theorem (estimator theorem)'''
:Let <math>\alpha=\frac{|G|}{|U|}</math>. Then the Monte Carlo method yields an <math>\epsilon</math>-approximation to <math>|G|</math> with probability at least <math>1-\delta</math> provided
::<math>N\ge\frac{4}{\epsilon \alpha}\ln\frac{2}{\delta}</math>.
|}
'''Proof''': Use the Chernoff bound.

<math>\square</math>

A counting algorithm for the set <math>G</math> has to deal with the following three complications:
* Implement the membership oracle <math>\mathcal{O}</math>. This is usually straightforward, or assumed by the model.
* Implement the uniform sampler <math>\mathcal{U}</math>. As we have seen, this is usually approximated by random walks. How to design the random walk and bound its mixing rate is usually technical challenging, if possible at all.
* Deal with exponentially small <math>\alpha=\frac{|G|}{|U|}</math>. This requires us to cleverly choose the universe <math>U</math>. Sometimes this needs some nontrivial ideas.

=== 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 '''#P-complete'''.

Naively applying the Monte Carlo method will not give a good answer. 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.

;The union of sets problem
We reformulate the DNF counting problem in a more abstract framework, called the '''union of sets''' problem.

Let <math>V</math> be a finite universe. We are given <math>m</math> subsets <math>H_1,H_2,\ldots,H_m\subseteq V</math>. The following assumptions hold:
*For all <math>i</math>, <math>|H_i|</math> is computable in poly-time.
*It is possible to sample uniformly from each individual <math>H_i</math>.
*For any <math>x\in V</math>, it can be determined in poly-time whether <math>x\in H_i</math>.

The goal is to compute the size of <math>H=\bigcup_{i=1}^m H_i</math>.

DNF counting can be interpreted in this general framework as follows. Suppose that the DNF formula <math>\phi</math> is defined on <math>n</math> variables, and <math>\phi</math> contains <math>m</math> clauses <math>C_1,C_2,\ldots,C_m</math>, where clause <math>C_i</math> has <math>k_i</math> literals. Without loss of generality, we assume that in each clause, each variable appears at most once.
* <math>V</math> is the set of all assignments.
*Each <math>H_i</math> is the set of satisfying assignments for the <math>i</math>-th clause <math>C_i</math> of the DNF formular <math>\phi</math>. Then the union of sets <math>H=\bigcup_i H_i</math> gives the set of satisfying assignments for <math>\phi</math>.
* Each clause <math>C_i</math> is a conjunction (AND) of literals. It is not hard to see that <math>|H_i|=2^{n-k_i}</math>, which is efficiently computable.
* Sampling from an <math>H_i</math> is simple: we just fix the assignments of the <math>k_i</math> literals of that clause, 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 can choose a unique representative among the multiple instances <math>(x,i)\in U</math> for the same <math>x\in H</math>, by choosing the <math>(x,i)</math> with the minimum <math>i</math>, and form a set <math>G</math>.

Formally, <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>.

It is obvious that <math>G\subseteq U</math> and
:<math>|G|=|H|</math>.

Therefore, estimation of <math>|H|</math> is reduced to estimation of <math>|G|</math> with <math>G\subseteq U</math>. Then <math>|G|</math> can have an <math>\epsilon</math>-approximation with probability <math>(1-\delta)</math> in poly-time, if we can uniformly sample from <math>U</math> and <math>|G|/|U|</math> is suitably small.

An uniform sample from <math>U</math> can be implemented as follows:
* 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>. The above sampling procedure is poly-time because each <math>|H_i|</math> can be computed in poly-time, and sampling uniformly from each <math>H_i</math> is poly-time.

We now only need to lower bound the ratio
:<math>\alpha=\frac{|G|}{|U|}</math>.

We claim that
:<math>\alpha\ge\frac{1}{m}</math>.
It is easy to see this, because each <math>x\in H</math> has at most <math>m</math> instances of <math>(x,i)</math> in <math>U</math>, and we already know that <math>|G|=|H|</math>.

Due to the estimator theorem, this needs <math>\frac{4m}{\epsilon}\ln\frac{2}{\delta}</math> uniform random samples from <math>U</math>.

This gives the coverage algorithm for the abstract problem of the union of sets. The DNF counting is a special case of it.

=== Permanents and perfect matchings ===

Let <math>U=\{u_1,u_2,\ldots,u_n\}</math> and <math>V=\{v_1,v_2,\ldots,v_n\}</math>. Consider a bipartite graph <math>G(U,V,E)</math>. An <math>M\subseteq E</math> is a '''perfect matching''' of <math>G</math> if every vertex of <math>G</math> has exactly one edge in <math>M</math> adjacent to it.

Given a bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math>, we want to count the number of perfect matchings of <math>G</math>. This problem can be reduced to computing the '''permanent''' of a square matrix.

{|border="1"
|'''Definition (permanent)'''
:Let <math>Q</math> be an <math>n\times n</math> matrix. The '''permanent''' of the matrix is defined as
::<math>\mathrm{per}(Q)=\sum_{\pi\in\mathbb{S}_n}\prod_{i=1}^n Q_{i,\pi(i)}</math>,
:where <math>\mathbb{S}_n</math> is the symmetric group of permutation of size <math>n</math>.
|}

If we multiply each term of the sum the sign of the permutation, then it gives us the determinant of the matrix,
:<math>\det(Q)=\sum_{\pi\in\mathbb{S}_n}\sgn(\pi)\prod_{i=1}^n Q_{i,\pi(i)}</math>,
where <math>\sgn(\pi)</math>, the sign of a permutation, is either <math>-1</math> or <math>+1</math>, according to whether the minimum number of pair-wise interchanges to achieve <math>\pi</math> from <math>(1,2,\ldots,n)</math> is odd or even.

Unlike the determinants, which are computable in poly-time, permanents are hard to compute, as permanents can be used to count the number of perfect matchings in a bipartite graph, which is '''#P-complete'''.

A bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math> can be represented by an <math>n\times n</math> matrix <math>Q</math> with 0-1 entries as follows:
* Each row of <math>Q</math> corresponds to a vertex in <math>U</math> and each column of <math>Q</math> corresponds to a vertex in <math>V</math>.
::<math>Q_{ij}=\begin{cases}
1 & \mbox{if }i\sim j,\\
0 & \mbox{otherwise}.
\end{cases}</math>
Note the subtle difference between the definition of <math>Q</math> and the adjacency matrix.

Each perfect matching corresponds to a permutation <math>\pi</math> of <math>U</math> with <math>(u,\pi(u))\in E</math> for every <math>u\in U</math>, which corresponds to a permutation <math>\pi\in\mathbb{S}_n</math> with <math>\prod_{i=1}^n Q_{i,\pi(i)}=1</math>. It is than easy to see that <math>\mathrm{per}(Q)</math> gives the number of perfect matchings in the bipartite graph <math>G</math>.

It is known that counting the number of perfect matchings in a bipartite graph is '''#P-hard'''. Since this problem can be reduced to computing the permanent, thus the problem of computing the permanents is also '''#P-hard'''.

Now we show that with randomization, we can approximate the number of perfect matchings in a bipartite graph. In particular, we will give an FPRAS for counting the perfect matchings in a dense bipartite graph.

==== The Jerrum-Sinclair algorithm ====
Fix a bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math>. Let <math>\mathcal{M}_k</math> be the set of matchings of size <math>k</math> in <math>G</math>, and let <math>m_k=|\mathcal{M}_k|</math>. Thus, <math>\mathcal{M}_k</math> is the set of perfect matchings in <math>G</math>, and our goal is to compute <math>m_n</math>.

Let <math>r_k=\frac{m_k}{m_{k-1}}</math> for <math>1<k\le n</math>. Then
:<math>m_k=m_{k-1}r_k</math>,
which gives us a recursion to compute the <math>m_n</math>, as
:<math>m_n=m_{1}\frac{m_2}{m_1}\cdot\frac{m_3}{m_2}\cdots\frac{m_n}{m_{n-1}}=m_1\prod_{k=2}^n r_k</math>,
where <math>m_1=|\mathcal{M}_1|</math> is the number of matchings of size 1 in the bipartite graph <math>G</math>, which is just the number of edges in <math>G</math>. Therefore, <math>m_n</math> can be computed once we know <math>r_k</math> for <math>1<k\le n</math>.

Each <math>r_k</math> can be estimated by sampling uniformly from the set <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>. The algorithm for estimating <math>m_n</math> is outlined as:
# For each <math>1<k\le n</math>, have an FPRAS for computing the <math>r_k</math> by uniform sampling sufficiently many members from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math> as
::*uniformly sample <math>N</math> matching from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>, for some polynomially large <math>N</math>;
::* assuming that there are <math>X</math> sampled matchings of size <math>k</math>, return <math>r_k</math> as <math>r_k=\frac{X}{N-X}</math>.
:2. Compute <math>m_n</math> as <math>m_n=m_1\prod_{k=2}^n r_k</math>, where <math>m_1=|E|</math>.

There are several issues that we have to deal with in order to have a fully functional FPRAS for counting perfect matchings.
* By taking the product of <math>r_k</math>'s, the errors for individual <math>r_k</math>'s add up.
* In order to accurately estimate <math>r_k</math> by sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>, the ratio <math>r_k</math> should be within the range <math>\left[\frac{1}{\alpha},\alpha\right]</math> for some <math>\alpha</math> within polynomial of <math>n</math>.
* Implement the uniform sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>.

;Estimator for each <math>r_k</math>

; Accumulation of errors

; Near-uniform sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>
In the last lecture, we have shown that by random walk, we can sample a near-uniform member of <math>\mathcal{M}_n\cup\mathcal{M}_{n-1}</math> in poly-time.

=== Volume estimation ===
We consider the problem of computing the volume of a given [http://en.wikipedia.org/wiki/Convex_body convex body] <math>K</math> in <math>n</math> dimensions.

We use <math>\Upsilon(K)\,</math> to denote the volume of the convex body <math>K</math>. Abstractly, the problem is that given as input a convex body <math>K</math> in <math>n</math> dimensions, return the <math>\Upsilon(K)\,</math>.

We should be more specific about the input model. Since we allow an arbitrary convex body as input, it is not even clear how to describe the body. We assume that <math>K</math> is described by means of a '''membership oracle''' <math>\mathcal{O}</math>, such that for a '''query''' of an <math>n</math>-dimensional point <math>x</math>, <math>\mathcal{O}(x)</math> indicates whether <math>x\in K</math>.

For example, the <math>n</math>-dimensional convex body defined by the intersection of <math>m</math> half-spaces, which is the set of feasible solutions to a system of <math>m</math> linear constraints, can be described as
:<math>A x\le \boldsymbol{b}</math>,
for some <math>m\times n</math> matrix <math>A</math>, and <math>m</math>-dimensional vector <math>b</math>. For a query of an <math>x</math>, the membership oracle <math>\mathcal{O}</math> just check whether <math>Ax\le b</math>.

For deterministic algorithms, there are negative news for this problem.

{|border="1"
|'''Theorem (Bárány-Füredi 1987)'''
:Suppose that a deterministic poly-time algorithm uses the membership oracle for a convex body <math>K</math> in <math>n</math> dimensions, and generates an upper bound <math>\Upsilon_u\,</math> and a lower bound <math>\Upsilon_\ell\,</math> on the volume <math>\Upsilon(K)\,</math> of <math>K</math>. Then, there is a convex body <math>K</math> and a constant <math>c</math> such that
::<math>\frac{\Upsilon_u}{\Upsilon_\ell}\ge c\left(\frac{n}{\log n}\right)^n</math>.
|}
That is said, with deterministic algorithms, we cannot even approximate the volume within a wildly loose range.

Dyer-Frieze-Kannan come up with an idea of estimating the volume of <math>K</math> by sampling near-uniformly from convex sets. They reduce the problem of computing approximately the volume of convex bodies to this sampling problem and thus give the first FPRAS for the volume of convex bodies.

For any convex body <math>K</math>, it encloses some <math>n</math>-dimensional ball and is also enclosed by another ball with larger radius. We assume that the convex body <math>K</math> encloses the unit ball around the origin, and is enclosed by a larger ball round the origin with polynomially large radius. Formally, we assume that
:<math>B(0,1)\subseteq K\subseteq B(0,n^c)</math> for some constant <math>c</math>,
where <math>B(p,r)</math> denotes a ball of radius <math>r</math> with <math>p</math> as center, i.e. <math>B(p,r)=\{x\mid \|x-p\|\le r \}</math>. We can make this assumption because it is known that for any convex body <math>K</math>, there exists a linear transformation <math>\tau</math> which can be found within poly-time such that <math>\tau K</math> transforms the <math>K</math> to a convex body that satisfies the assumption, and preserves the ratio of the volumes of the balls to the convex body.

The volumes of the balls are easy to compute. If only the ratio between the convex body and the ball which encloses it, is sufficiently large, then we can apply the Monte Carlo method to estimate <math>\Upsilon(K)\,</math> by uniformly sampling from the ball.

However, in high-dimension, the ratio between the volume of a convex body and the volume of ball which encloses it, can be exponentially small. This is caused by the so called the "[http://en.wikipedia.org/wiki/Curse_of_dimensionality curse of dimensionality]".

Instead of having an outer ball and an inner ball, we define a sequence of balls:
:<math>B_0=B(0,\lambda^0), B_1=B(0,\lambda^1), B_2=B(0,\lambda^2),\ldots, B_m=B(0,\lambda^m)</math>,
where <math>\lambda=(1+\frac{1}{n})</math> and <math>m</math> is the smallest positive integer such that <math>\lambda^m\ge n^c</math>. Therefore, the inner ball <math>B(0,1)=B_0</math>, the outer ball <math>B(0,n^c)\subseteq B_m</math>, and <math>m</math> is within polynomial of <math>n</math>. In fact, <math>m\approx cn\ln n</math>.

This sequence of balls naturally defines a sequence of convex bodies by intersections as <math>K_i=B_i\cap K</math>. It is obvious that
:<math>B(0,1)=K_0\subseteq K_1\subseteq K_2\subseteq\cdots\subseteq K_m=K</math>.
Balls are convex, and since the intersection of convex bodies is still convex, the sequence of <math>K_i</math> is a sequence of convex bodies.

We have the telescopic product:
:<math>
\frac{\Upsilon(K_0)}{\Upsilon(K_1)}\cdot\frac{\Upsilon(K_1)}{\Upsilon(K_2)}\cdots\frac{\Upsilon(K_{m-1})}{\Upsilon(K_m)}=\frac{\Upsilon(K_0)}{\Upsilon(K_m)}=\frac{\Upsilon(B(0,1))}{\Upsilon(K)}.
</math>
Therefore, the volume <math>\Upsilon(K)\,</math> can be computed as
:<math>\Upsilon(K)=\Upsilon(B(0,1))\cdot\prod_{i=1}^{m}\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math>.

The volume of unite ball <math>\Upsilon(B(0,1))\,</math> can be precisely computed in poly-time. Each <math>\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math> is computed by near-uniform sampling from <math>K_{i}</math>, which encloses <math>K_{i-1}</math>.

Another observation is that the ratio <math>\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math> is well-bounded. Recall that <math>K_i=B(0,\lambda^i)\cap K</math> where <math>\lambda=(1+\frac{1}{n})</math>. It can be proved that in <math>n</math> dimensions, the volume of <math>K_i</math> is at most <math>\lambda^n</math> times the <math>K_{i-1}</math>, thus the ratio <math>\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math> is at most <math>\lambda^n=O(1)</math>. By the estimator theorem, we can have an FPRAS for the ratio <math>\frac{\Upsilon(K_{i})}{\Upsilon(K_{i-1})}</math> if we can uniformly sample from <math>K_i</math>.

Uniformly sampling from an arbitrary convex body is replaced by near-uniform sampling achieved by random walks. In the original walk of Dyer-Frieze-Kannan, they consider the random walk over <math>n</math>-dimensional discrete grid points enclosed by <math>K</math>, and prove that the walk is rapid mixing. This gives us the first FPRAS for volume estimation which runs in <math>\tilde{O}(n^{23})</math>, where <math>\tilde{O}(\cdot)</math> ignores the polylogarithmic factors.

The time bound was later improved by a series of works, each introducing some new ideas.

{|border="1"
| || complexity || new ingredient(s)
|-
| Dyer-Frieze-Kannan 1991 || align="center" | <math>n^{23}</math> || everything
|-
| Lovász-Simonovits 1990 || align="center" | <math>n^{16}</math> || localization lemma
|-
| Applegate-Kannan 1990 || align="center" | <math>n^{10}</math> || logconcave sampling
|-
| Lovász 1990 || align="center" | <math>n^{10}</math> || ball walk
|-
| Dyer-Frieze 1991 || align="center" | <math>n^8</math> || better error analysis
|-
| Lovász-Simonovits 1993 || align="center" | <math>n^7</math> || many improvements
|-
| Kannan-Lovász-Simonovits 1997 || align="center" | <math>n^5</math> || isotropy, speedy walk
|-
| Lovász-Vempala 2003 || align="center" | <math>n^4</math> || simulated annealing, hit-and-run
|-
|}
(cited from "Geometric Random Walks: A Survey" by Santosh Vempala.)

The current best upper bound is <math>\tilde{O}(n^4)</math> due to Lovász and Vempala in 2003. It is conjectured that the optimal bound is <math>\Theta(n^3)</math>.

== Linear Programming ==

=== LP and convex polytopes ===

=== The simplex algorithms ===

=== An LP solver via random walks ===

Randomized Algorithms (Spring 2010)/Approximate counting, linear programming

2010-05-23T14:48:40Z

172.16.65.36: /* The Jerrum-Sinclair algorithm */

== Counting Problems ==

=== Complexity model ===

=== FPRAS ===

== Approximate Counting ==
Let us consider the following formal problem.

Let <math>U</math> be a finite set of known size, and let <math>G\subseteq U</math>. We want to compute the size of <math>G</math>, <math>|G|</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 algorithm:
*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
::<math>Z=\frac{|U|}{N}\sum_{i=1}^N Y_i.</math>

It is easy to see that <math>\mathbf{E}[Z]=|G|</math> and we might hope that with high probability the value of <math>Z</math> is close to <math>|G|</math>. 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>

The following theorem states that the probabilistic accuracy of the estimation depends on the number of samples and the ratio between <math>|G|</math> and <math>|U|</math>

{|border="1"
|'''Theorem (estimator theorem)'''
:Let <math>\alpha=\frac{|G|}{|U|}</math>. Then the Monte Carlo method yields an <math>\epsilon</math>-approximation to <math>|G|</math> with probability at least <math>1-\delta</math> provided
::<math>N\ge\frac{4}{\epsilon \alpha}\ln\frac{2}{\delta}</math>.
|}
'''Proof''': Use the Chernoff bound.

<math>\square</math>

A counting algorithm for the set <math>G</math> has to deal with the following three complications:
* Implement the membership oracle <math>\mathcal{O}</math>. This is usually straightforward, or assumed by the model.
* Implement the uniform sampler <math>\mathcal{U}</math>. As we have seen, this is usually approximated by random walks. How to design the random walk and bound its mixing rate is usually technical challenging, if possible at all.
* Deal with exponentially small <math>\alpha=\frac{|G|}{|U|}</math>. This requires us to cleverly choose the universe <math>U</math>. Sometimes this needs some nontrivial ideas.

=== 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 '''#P-complete'''.

Naively applying the Monte Carlo method will not give a good answer. 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.

;The union of sets problem
We reformulate the DNF counting problem in a more abstract framework, called the '''union of sets''' problem.

Let <math>V</math> be a finite universe. We are given <math>m</math> subsets <math>H_1,H_2,\ldots,H_m\subseteq V</math>. The following assumptions hold:
*For all <math>i</math>, <math>|H_i|</math> is computable in poly-time.
*It is possible to sample uniformly from each individual <math>H_i</math>.
*For any <math>x\in V</math>, it can be determined in poly-time whether <math>x\in H_i</math>.

The goal is to compute the size of <math>H=\bigcup_{i=1}^m H_i</math>.

DNF counting can be interpreted in this general framework as follows. Suppose that the DNF formula <math>\phi</math> is defined on <math>n</math> variables, and <math>\phi</math> contains <math>m</math> clauses <math>C_1,C_2,\ldots,C_m</math>, where clause <math>C_i</math> has <math>k_i</math> literals. Without loss of generality, we assume that in each clause, each variable appears at most once.
* <math>V</math> is the set of all assignments.
*Each <math>H_i</math> is the set of satisfying assignments for the <math>i</math>-th clause <math>C_i</math> of the DNF formular <math>\phi</math>. Then the union of sets <math>H=\bigcup_i H_i</math> gives the set of satisfying assignments for <math>\phi</math>.
* Each clause <math>C_i</math> is a conjunction (AND) of literals. It is not hard to see that <math>|H_i|=2^{n-k_i}</math>, which is efficiently computable.
* Sampling from an <math>H_i</math> is simple: we just fix the assignments of the <math>k_i</math> literals of that clause, 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 can choose a unique representative among the multiple instances <math>(x,i)\in U</math> for the same <math>x\in H</math>, by choosing the <math>(x,i)</math> with the minimum <math>i</math>, and form a set <math>G</math>.

Formally, <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>.

It is obvious that <math>G\subseteq U</math> and
:<math>|G|=|H|</math>.

Therefore, estimation of <math>|H|</math> is reduced to estimation of <math>|G|</math> with <math>G\subseteq U</math>. Then <math>|G|</math> can have an <math>\epsilon</math>-approximation with probability <math>(1-\delta)</math> in poly-time, if we can uniformly sample from <math>U</math> and <math>|G|/|U|</math> is suitably small.

An uniform sample from <math>U</math> can be implemented as follows:
* 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>. The above sampling procedure is poly-time because each <math>|H_i|</math> can be computed in poly-time, and sampling uniformly from each <math>H_i</math> is poly-time.

We now only need to lower bound the ratio
:<math>\alpha=\frac{|G|}{|U|}</math>.

We claim that
:<math>\alpha\ge\frac{1}{m}</math>.
It is easy to see this, because each <math>x\in H</math> has at most <math>m</math> instances of <math>(x,i)</math> in <math>U</math>, and we already know that <math>|G|=|H|</math>.

Due to the estimator theorem, this needs <math>\frac{4m}{\epsilon}\ln\frac{2}{\delta}</math> uniform random samples from <math>U</math>.

This gives the coverage algorithm for the abstract problem of the union of sets. The DNF counting is a special case of it.

=== Permanents and perfect matchings ===

Let <math>U=\{u_1,u_2,\ldots,u_n\}</math> and <math>V=\{v_1,v_2,\ldots,v_n\}</math>. Consider a bipartite graph <math>G(U,V,E)</math>. An <math>M\subseteq E</math> is a '''perfect matching''' of <math>G</math> if every vertex of <math>G</math> has exactly one edge in <math>M</math> adjacent to it.

Given a bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math>, we want to count the number of perfect matchings of <math>G</math>. This problem can be reduced to computing the '''permanent''' of a square matrix.

{|border="1"
|'''Definition (permanent)'''
:Let <math>Q</math> be an <math>n\times n</math> matrix. The '''permanent''' of the matrix is defined as
::<math>\mathrm{per}(Q)=\sum_{\pi\in\mathbb{S}_n}\prod_{i=1}^n Q_{i,\pi(i)}</math>,
:where <math>\mathbb{S}_n</math> is the symmetric group of permutation of size <math>n</math>.
|}

If we multiply each term of the sum the sign of the permutation, then it gives us the determinant of the matrix,
:<math>\det(Q)=\sum_{\pi\in\mathbb{S}_n}\sgn(\pi)\prod_{i=1}^n Q_{i,\pi(i)}</math>,
where <math>\sgn(\pi)</math>, the sign of a permutation, is either <math>-1</math> or <math>+1</math>, according to whether the minimum number of pair-wise interchanges to achieve <math>\pi</math> from <math>(1,2,\ldots,n)</math> is odd or even.

A bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math> can be represented by an <math>n\times n</math> matrix <math>Q</math> with 0-1 entries as follows:
* Each row of <math>Q</math> corresponds to a vertex in <math>U</math> and each column of <math>Q</math> corresponds to a vertex in <math>V</math>.
::<math>Q_{ij}=\begin{cases}
1 & \mbox{if }i\sim j,\\
0 & \mbox{otherwise}.
\end{cases}</math>
Note the subtle difference between the definition of <math>Q</math> and the adjacency matrix.

Each perfect matching corresponds to a permutation <math>\pi</math> of <math>U</math> with <math>(u,\pi(u))\in E</math> for every <math>u\in U</math>, which corresponds to a permutation <math>\pi\in\mathbb{S}_n</math> with <math>\prod_{i=1}^n Q_{i,\pi(i)}=1</math>. It is than easy to see that <math>\mathrm{per}(Q)</math> gives the number of perfect matchings in the bipartite graph <math>G</math>.

It is known that counting the number of perfect matchings in a bipartite graph is '''#P-hard'''. Since this problem can be reduced to computing the permanent, thus the problem of computing the permanents is also '''#P-hard'''. This is quite different from the case of determinants, since the determinants can be computed in poly-time.

Now we show that with randomization, we can approximate the number of perfect matchings in a bipartite graph. In particular, we will give an FPRAS for counting the perfect matchings in a bipartite graph.

==== The Jerrum-Sinclair algorithm ====
Fix a bipartite graph <math>G(U,V,E)</math> with <math>|U|=|V|=n</math>. Let <math>\mathcal{M}_k</math> be the set of matchings of size <math>k</math> in <math>G</math>, and let <math>m_k=|\mathcal{M}_k|</math>. Thus, <math>\mathcal{M}_k</math> is the set of perfect matchings in <math>G</math>, and our goal is to compute <math>m_n</math>.

Let <math>r_k=\frac{m_k}{m_{k-1}}</math> for <math>1<k\le n</math>. Then
:<math>m_k=m_{k-1}r_k</math>,
which gives us a recursion to compute the <math>m_n</math>, as
:<math>m_n=m_{1}\frac{m_2}{m_1}\cdot\frac{m_3}{m_2}\cdots\frac{m_n}{m_{n-1}}=m_1\prod_{k=2}^n r_k</math>,
where <math>m_1=|\mathcal{M}_1|</math> is the number of matchings of size 1 in the bipartite graph <math>G</math>, which is just the number of edges in <math>G</math>. Therefore, <math>m_n</math> can be computed once we know <math>r_k</math> for <math>1<k\le n</math>.

Each <math>r_k</math> can be estimated by sampling uniformly from the set <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>. The algorithm for estimating <math>m_n</math> is outlined as:
# For each <math>1<k\le n</math>, have an FPRAS for computing the <math>r_k</math> by uniform sampling sufficiently many members from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math> as
::*uniformly sample <math>N</math> matching from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>, for some polynomially large <math>N</math>;
::* assuming that there are <math>X</math> sampled matchings of size <math>k</math>, return <math>r_k</math> as <math>r_k=\frac{X}{N-X}</math>.
:2. Compute <math>m_n</math> as <math>m_n=m_1\prod_{k=2}^n r_k</math>, where <math>m_1=|E|</math>.

There are several issues that we have to deal with in order to have a fully functional FPRAS for counting perfect matchings.
* By taking the product of <math>r_k</math>'s, the errors for individual <math>r_k</math>'s add up.
* In order to accurately estimate <math>r_k</math> by sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>, the ratio <math>r_k</math> should be within the range <math>\left[\frac{1}{\alpha},\alpha\right]</math> for some <math>\alpha</math> within polynomial of <math>n</math>.
* Implement the uniform sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>.

;Estimator for each <math>r_k</math>

; Accumulation of errors

; Near-uniform sampling from <math>\mathcal{M}_k\cup\mathcal{M}_{k-1}</math>
In the last lecture, we have shown that by random walk, we can sample a near-uniform member of <math>\mathcal{M}_n\cup\mathcal{M}_{n-1}</math> in poly-time.

=== Volume estimation ===

== Linear Programming ==

=== LP and convex polytopes ===

=== The simplex algorithms ===

=== An LP solver via random walks ===