随机算法 (Fall 2011)/The Probabilistic Method: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
imported>WikiSysop
No edit summary
imported>WikiSysop
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
= Counting =
= Probabilistic Method =
 
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.
===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.
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>.


{{Theorem
Although the idea of  the probabilistic method is simple, it provides us a powerful tool for existential proof.
|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| There are <math>2^{2^n}</math> boolean functions <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>.


Fix an integer <math>t</math>, we then 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>.
Uniformly choose a boolean function <math>f</math> at random. Note that each circuit can compute one boolean function (the converse is not true). The probability that <math>f</math> can be computed by a circuit with <math>t</math> gates is at most
:<math>
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}.
</math>
If <math>t=2^n/3n</math>, then
:<math>
\frac{2^t(t+2n+1)^{2t}}{2^{2^n}}=o(1)<1.
</math>
Therefore, there exists 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.
= Probabilistic Method =
===Ramsey number===
===Ramsey number===


Line 82: Line 58:
</math>
</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>.
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>.
===Tournament===
A '''[http://en.wikipedia.org/wiki/Tournament_(graph_theory) tournament]''' (竞赛图) on a set <math>V</math> of <math>n</math> players is an '''orientation''' of the edges of the complete graph on the set of vertices <math>V</math>. Thus for every two distinct vertices <math>u,v</math> in <math>V</math>, either <math>(u,v)\in E</math> or <math>(v,u)\in E</math>, but not both.
We can think of the set <math>V</math> as a set of <math>n</math> players in which each pair participates in a single match, where <math>(u,v)</math> is in the tournament iff player <math>u</math> beats player <math>v</math>.
{{Theorem|Definition|
:We say that a tournament has '''<math>k</math>-paradoxical''' if for every set of <math>k</math> players there is a player who beats them all.
}}
Is it true for every finite <math>k</math>, there is a <math>k</math>-paradoxical tournament (on more than <math>k</math> vertices, of course)? This problem was first raised by Schütte, and as shown by Erdős, can be solved almost trivially by the probabilistic method.
{{Theorem|Theorem (Erdős 1963)|
:If <math>{n\choose k}\left(1-2^{-k}\right)^{n-k}<1</math> then there is a tournament on <math>n</math> vertices that is <math>k</math>-paradoxical.
}}
{{Proof|
Consider a uniformly random tournament <math>T</math> on the set <math>V=[n]</math>. For every fixed subset <math>S\in{V\choose k}</math> of <math>k</math> vertices, let <math>A_S</math> be the event defined as follows
:<math>A_S:\,</math> there is no vertex in <math>V\setminus S</math> that beats all vertices in <math>S</math>.
In a uniform random tournament, the orientations of edges are independent. For any <math>u\in V\setminus S</math>,
:<math>\Pr[u\mbox{ beats all }v\in S]=2^{-k}</math>.
Therefore, <math>\Pr[u\mbox{ does not beats all }v\in S]=1-2^{-k}</math> and
:<math>\Pr[A_S]=\prod_{u\in V\setminus S}\Pr[u\mbox{ does not beats all }v\in S]=(1-2^{-k})^{n-k}</math>.
It follows that
:<math>\Pr\left[\bigvee_{S\in{V\choose k}}A_S\right]\le \sum_{S\in{V\choose k}}\Pr[A_S]={n\choose k}(1-2^{-k})^{n-k}<1.</math>
Therefore,
:<math>\Pr[\,T\mbox{ is }k\mbox{-paradoxical }]=\Pr\left[\bigwedge_{S\in{V\choose k}}\overline{A_S}\right]=1-\Pr\left[\bigvee_{S\in{V\choose k}}A_S\right]>0.</math>
There is a <math>k</math>-paradoxical tournament.
}}


= Averaging Principle =
= Averaging Principle =
===Hamiltonian paths===
The following result of Szele in 1943 is often considered the first use of the probabilistic method.
{{Theorem|Theorem (Szele 1943)|
:There is a tournament on <math>n</math> players with at least <math>n!2^{-(n-1)}</math> Hamiltonian paths.
}}
{{Proof|
Consider the uniform random tournament <math>T</math> on <math>[n]</math>. For any permutation <math>\pi</math> of <math>[n]</math>, let <math>X_{\pi}</math> be the indicator random variable defined as
:<math>X_{\pi}=\begin{cases}
1 & \forall i\in[n-1], (\pi_i,\pi_{i+1})\in T,\\
0 & \mbox{otherwise}.
\end{cases}</math>
In other words, <math>X_{\pi}</math> indicates whether <math>\pi_0\rightarrow\pi_1\rightarrow\pi_2\rightarrow\cdots\rightarrow\pi_{n-1}</math> gives a Hamiltonian path.
It holds that
:<math>\mathrm{E}[X_\pi]=1\cdot\Pr[X_\pi=1]+0\cdot\Pr[X_\pi=0]=\Pr[\forall i\in[n-1], (\pi_i,\pi_{i+1})\in T]=2^{-(n-1)}.</math>
Let <math>X=\sum_{\pi:\text{permutation of }[n]}X_\pi\,</math>. Clearly <math>X</math> is the number of Hamiltonian paths in the tournament <math>T</math>.
Due to the linearity of expectation,
:<math>\mathrm{E}[X]=\mathrm{E}\left[\sum_{\pi:\text{permutation of }[n]}X_\pi\right]=\sum_{\pi:\text{permutation of }[n]}\mathrm{E}[X_\pi]=n!2^{-(n-1)}.</math>
This is the average number of Hamiltonian paths in a tournament, where the average is taken over all tournaments.
Thus some tournament has at least <math>n!2^{-(n-1)}</math> Hamiltonian paths.
}}


===Maximum cut===
===Maximum cut===
Line 202: Line 124:
There exists an independent set which contains at least <math>\frac{n^2}{4m}</math> vertices.
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>.

Latest revision as of 03:58, 24 July 2011

Probabilistic Method

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]\displaystyle{ \ell }[/math], then we know there is a students whose height is at least [math]\displaystyle{ \ell }[/math], and there is a student whose height is at most [math]\displaystyle{ \ell }[/math].

Although the idea of the probabilistic method is simple, it provides us a powerful tool for existential proof.

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]\displaystyle{ K_6 }[/math] (the complete graph on six vertices), there must be a monochromatic [math]\displaystyle{ K_3 }[/math] (a triangle whose edges have the same color).

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

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

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

For any fixed set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ k }[/math] vertices, let [math]\displaystyle{ \mathcal{E}_S }[/math] be the event that the [math]\displaystyle{ K_k }[/math] subgraph induced by [math]\displaystyle{ S }[/math] is monochromatic. There are [math]\displaystyle{ {k\choose 2} }[/math] many edges in [math]\displaystyle{ K_k }[/math], therefore

[math]\displaystyle{ \Pr[\mathcal{E}_S]=2\cdot 2^{-{k\choose 2}}=2^{1-{k\choose 2}}. }[/math]

Since there are [math]\displaystyle{ {n\choose k} }[/math] possible choices of [math]\displaystyle{ S }[/math], by the union bound

[math]\displaystyle{ \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]\displaystyle{ {n\choose k}\cdot 2^{1-{k\choose 2}}\lt 1 }[/math], thus there exists a two coloring that none of [math]\displaystyle{ \mathcal{E}_S }[/math] occurs, which means there is no monochromatic [math]\displaystyle{ K_k }[/math] subgraph.

[math]\displaystyle{ \square }[/math]

For [math]\displaystyle{ k\ge 3 }[/math] and we take [math]\displaystyle{ n=\lfloor2^{k/2}\rfloor }[/math], then

[math]\displaystyle{ \begin{align} {n\choose k}\cdot 2^{1-{k\choose 2}} &\lt \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!}\\ &\lt 1. \end{align} }[/math]

By the above theorem, there exists a two-coloring of [math]\displaystyle{ K_n }[/math] that there is no monochromatic [math]\displaystyle{ K_k }[/math]. Therefore, the Ramsey number [math]\displaystyle{ R(k,k)\gt \lfloor2^{k/2}\rfloor }[/math] for all [math]\displaystyle{ k\ge 3 }[/math].

Note that for sufficiently large [math]\displaystyle{ k }[/math], if [math]\displaystyle{ n= \lfloor 2^{k/2}\rfloor }[/math], then the probability that there exists a monochromatic [math]\displaystyle{ K_k }[/math] is bounded by

[math]\displaystyle{ {n\choose k}\cdot 2^{1-{k\choose 2}} \lt \frac{2^{1+\frac{k}{2}}}{k!} \ll 1, }[/math]

which means that a random two-coloring of [math]\displaystyle{ K_n }[/math] is very likely not to contain a monochromatic [math]\displaystyle{ K_{2\log n} }[/math]. This gives us a very simple randomized algorithm for finding a two-coloring of [math]\displaystyle{ K_n }[/math] without monochromatic [math]\displaystyle{ K_{2\log n} }[/math].

Averaging Principle

Maximum cut

Given an undirected graph [math]\displaystyle{ G(V,E) }[/math], a set [math]\displaystyle{ C }[/math] of edges of [math]\displaystyle{ G }[/math] is called a cut if [math]\displaystyle{ G }[/math] is disconnected after removing the edges in [math]\displaystyle{ C }[/math]. We can represent a cut by [math]\displaystyle{ c(S,T) }[/math] where [math]\displaystyle{ (S,T) }[/math] is a bipartition of the vertex set [math]\displaystyle{ V }[/math], and [math]\displaystyle{ c(S,T)=\{uv\in E\mid u\in S,v\in T\} }[/math] is the set of edges crossing between [math]\displaystyle{ S }[/math] and [math]\displaystyle{ 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 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
Given an undirected graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges, there is a cut of size at least [math]\displaystyle{ \frac{m}{2} }[/math].
Proof.
Enumerate the vertices in an arbitrary order. Partition the vertex set [math]\displaystyle{ V }[/math] into two disjoint sets [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] as follows.
For each vertex [math]\displaystyle{ v\in V }[/math],
  • independently choose one of [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] with equal probability, and let [math]\displaystyle{ v }[/math] join the chosen set.

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

[math]\displaystyle{ \Pr[Y_{uv}=1]=\Pr[X_u\neq X_v]=\frac{1}{2}. }[/math]

The size of [math]\displaystyle{ c(S,T) }[/math] is given by [math]\displaystyle{ Y=\sum_{uv\in E}Y_{uv} }[/math]. By the linearity of expectation,

[math]\displaystyle{ \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]\displaystyle{ (S,T) }[/math] of [math]\displaystyle{ V }[/math] such that [math]\displaystyle{ |c(S,T)|\ge\frac{m}{2} }[/math], i.e. there exists a cut of [math]\displaystyle{ G }[/math] which contains at least [math]\displaystyle{ \frac{m}{2} }[/math] edges.

[math]\displaystyle{ \square }[/math]

Alternations

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
Let [math]\displaystyle{ G(V,E) }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices with [math]\displaystyle{ m }[/math] edges. Then [math]\displaystyle{ G }[/math] has an independent set with at least [math]\displaystyle{ \frac{n^2}{4m} }[/math] vertices.
Proof.
Let [math]\displaystyle{ S }[/math] be a set of vertices constructed as follows:
For each vertex [math]\displaystyle{ v\in V }[/math]:
  • [math]\displaystyle{ v }[/math] is included in [math]\displaystyle{ S }[/math] independently with probability [math]\displaystyle{ p }[/math],

[math]\displaystyle{ p }[/math] to be determined.

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

For each edge [math]\displaystyle{ e\in E }[/math], let [math]\displaystyle{ Y_{e} }[/math] be the random variable which indicates whether both endpoints of [math]\displaystyle{ }[/math] are in [math]\displaystyle{ S }[/math].

[math]\displaystyle{ \mathbf{E}[Y_{uv}]=\Pr[u\in S\wedge v\in S]=p^2. }[/math]

Let [math]\displaystyle{ Y }[/math] be the number of edges in the subgraph of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ S }[/math]. It holds that [math]\displaystyle{ Y=\sum_{e\in E}Y_e }[/math]. By linearity of expectation,

[math]\displaystyle{ \mathbf{E}[Y]=\sum_{e\in E}\mathbf{E}[Y_e]=mp^2 }[/math].

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

Since there are [math]\displaystyle{ Y }[/math] edges in [math]\displaystyle{ G(S) }[/math], there are at most [math]\displaystyle{ Y }[/math] vertices in [math]\displaystyle{ S }[/math] are deleted to make it become [math]\displaystyle{ S^* }[/math]. Therefore, [math]\displaystyle{ |S^*|\ge X-Y }[/math]. By linearity of expectation,

[math]\displaystyle{ \mathbf{E}[|S^*|]\ge\mathbf{E}[X-Y]=\mathbf{E}[X]-\mathbf{E}[Y]=np-mp^2. }[/math]

The expectation is maximized when [math]\displaystyle{ p=\frac{n}{2m} }[/math], thus

[math]\displaystyle{ \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]\displaystyle{ \frac{n^2}{4m} }[/math] vertices.

[math]\displaystyle{ \square }[/math]

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

Algorithm

Given a graph on [math]\displaystyle{ n }[/math] vertices with [math]\displaystyle{ m }[/math] edges, let [math]\displaystyle{ d=\frac{2m}{n} }[/math] be the average degree.

  1. For each vertex [math]\displaystyle{ v\in V }[/math], [math]\displaystyle{ v }[/math] is included in [math]\displaystyle{ S }[/math] independently with probability [math]\displaystyle{ \frac{1}{d} }[/math].
  2. For each remaining edge in the induced subgraph [math]\displaystyle{ G(S) }[/math], remove one of the endpoints from [math]\displaystyle{ S }[/math].

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

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)/The_Probabilistic_Method&oldid=4691"