imported>Etone |
imported>Macdonald-ross |
| Line 1: |
Line 1: |
| <font color=red size=3> This part of the lecture note is still under editting. This notice will be removed once the lecture note has been fully updated.</font> | | {{otheruse|biological fitness}} |
| | '''Fitness''' in [[biology]] is the relative ability of an organism to survive and pass on its [[gene]]s to the next generation.<ref>King R.C. Stansfield W.D. & Mulligan P.K. 2006. ''A dictionary of genetics'', 7th ed. Oxford.</ref><sup>p160</sup> It is a central idea in [[evolution|evolutionary theory]]. Fitness is usually equal to the proportion of the individual's [[gene]]s in all the genes of the next generation. |
|
| |
|
| = Conditional Probability =
| | Like all terms in evolutionary biology, fitness is defined in terms of an interbreeding [[Population genetics|population]], which might or might not be a whole [[species]]. If differences in individual genotypes affect fitness, then the frequencies of the genotypes will change over generations; the genotypes with higher fitness become more common. This is the process called [[natural selection]]. |
| In probability theory, the word "condition" is a verb. "Conditioning on the event ..." means that it is assumed that the event occurs.
| |
|
| |
|
| {{Theorem
| | An individual's fitness is caused by its [[phenotype]], and passed on by its [[genotype]]. The fitnesses of different individuals with the same genotype are not necessarily equal. It depends on the [[environment]] in which the individuals live, and on accidental [[event]]s. However, since the fitness of the genotype is an [[average]]d quantity, it reflects the reproductive outcomes of ''all'' individuals with that genotype. |
| |Definition (conditional probability)|
| |
| :The '''conditional probability''' that event <math>\mathcal{E}_1</math> occurs given that event <math>\mathcal{E}_2</math> occurs is
| |
| ::<math>
| |
| \Pr[\mathcal{E}_1\mid \mathcal{E}_2]=\frac{\Pr[\mathcal{E}_1\wedge \mathcal{E}_2]}{\Pr[\mathcal{E}_2]}.
| |
| </math>
| |
| }}
| |
|
| |
|
| The conditional probability is well-defined only if <math>\Pr[\mathcal{E}_2]\neq0</math>.
| | == Relatedness == |
| | Fitness measures the number of the ''copies'' of the genes of an individual in the next generation. It doesn't really matter how the genes arrive in the next generation. For an individual, it is equally "beneficial" to reproduce itself, or to help relatives with similar genes to reproduce, ''as long as similar number of copies of individual's genes get passed on to the next generation''. Selection which promotes this kind of helper behaviour is called [[kin selection]]. |
|
| |
|
| For independent events <math>\mathcal{E}_1</math> and <math>\mathcal{E}_2</math>, it holds that
| | Our closest relatives (parents, siblings, and our own children) share on average 50% (half) of our genes. One step further removed are grandparents. With each of them we share on average 25% (a quarter) of our genes. That is a measure of our relatedness to them. Next come first cousins (children of our parents' siblings). We share 12.5% (1/8) of their genes.<ref name=JMS>Maynard Smith, John. 1999. ''Evolutionary genetics''. 2nd ed, Cambridge University Press.</ref><sup>p100</sup> |
| :<math>
| |
| \Pr[\mathcal{E}_1\mid \mathcal{E}_2]=\frac{\Pr[\mathcal{E}_1\wedge \mathcal{E}_2]}{\Pr[\mathcal{E}_2]}
| |
| =\frac{\Pr[\mathcal{E}_1]\cdot\Pr[\mathcal{E}_2]}{\Pr[\mathcal{E}_2]}
| |
| =\Pr[\mathcal{E}_1].
| |
| </math> | |
| It supports our intuition that for two independent events, whether one of them occurs will not affect the chance of the other.
| |
|
| |
|
| == Law of total probability == | | === Hamilton's rule === |
| The following fact is known as the law of total probability. It computes the probability by averaging over all possible cases.
| | [[W.D. Hamilton|William Hamilton]] added various ideas to the notion of fitness. His rule suggests that a costly action should be performed if: |
| {{Theorem
| | :<math>C < R \times B </math> where: |
| |Theorem (law of total probability)| | | * <math>c \ </math> is the reproductive cost to the altruist, |
| :Let <math>\mathcal{E}_1,\mathcal{E}_2,\ldots,\mathcal{E}_n</math> be mutually disjoint events, and <math>\bigvee_{i=1}^n\mathcal{E}_i=\Omega</math> is the sample space. | | * <math>b \ </math> is the reproductive benefit to the recipient of the altruistic behavior, and |
| :Then for any event <math>\mathcal{E}</math>,
| | * <math>r \ </math> is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness". |
| ::<math>
| | Fitness costs and benefits are measured in [[fecundity]].<ref>Hamilton W.D. 1964. The genetical evolution of social behavior. ''Journal of Theoretical Biology'' '''7''' (1): 1–52. doi:10.1016/0022-5193(64)90038-4.</ref> |
| \Pr[\mathcal{E}]=\sum_{i=1}^n\Pr[\mathcal{E}\mid\mathcal{E}_i]\cdot\Pr[\mathcal{E}_i].
| |
| </math> | |
| }}
| |
| {{Proof| Since <math>\mathcal{E}_1,\mathcal{E}_2,\ldots,\mathcal{E}_n</math> are mutually disjoint and <math>\bigvee_{i=1}^n\mathcal{E}_i=\Omega</math>, events <math>\mathcal{E}\wedge\mathcal{E}_1,\mathcal{E}\wedge\mathcal{E}_2,\ldots,\mathcal{E}\wedge\mathcal{E}_n</math> are also mutually disjoint, and <math>\mathcal{E}=\bigvee_{i=1}^n\left(\mathcal{E}\wedge\mathcal{E}_i\right)</math>. Then
| |
| :<math>
| |
| \Pr[\mathcal{E}]=\sum_{i=1}^n\Pr[\mathcal{E}\wedge\mathcal{E}_i],
| |
| </math> | |
| which according to the definition of conditional probability, is <math>\sum_{i=1}^n\Pr[\mathcal{E}\mid\mathcal{E}_i]\cdot\Pr[\mathcal{E}_i]</math>.
| |
| }}
| |
|
| |
|
| The law of total probability provides us a standard tool for breaking a probability into sub-cases. Sometimes, it helps the analysis.
| | === Inclusive fitness === |
| | Inclusive fitness is a term which is essentially the same as fitness, but emphasises the group of genes rather than individuals. |
|
| |
|
| == A Chain of Conditioning ==
| | Biological fitness says how well an organism can reproduce, and spread its genes to its offspring. The theory of inclusive fitness says that the fitness of an organism is also increased to the extent that its close relatives also reproduce. This is because relatives share genes in proportion to their relationship. |
| By the definition of conditional probability, <math>\Pr[A\mid B]=\frac{\Pr[A\wedge B]}{\Pr[B]}</math>. Thus, <math>\Pr[A\wedge B] =\Pr[B]\cdot\Pr[A\mid B]</math>. This hints us that we can compute the probability of the AND of events by conditional probabilities. Formally, we have the following theorem:
| |
| {{Theorem|Theorem|
| |
| :Let <math>\mathcal{E}_1, \mathcal{E}_2, \ldots, \mathcal{E}_n</math> be any <math>n</math> events. Then
| |
| ::<math>\begin{align}
| |
| \Pr\left[\bigwedge_{i=1}^n\mathcal{E}_i\right]
| |
| &=
| |
| \prod_{k=1}^n\Pr\left[\mathcal{E}_k \mid \bigwedge_{i<k}\mathcal{E}_i\right].
| |
| \end{align}</math>
| |
| }}
| |
| {{Proof|It holds that <math>\Pr[A\wedge B] =\Pr[B]\cdot\Pr[A\mid B]</math>. Thus, let <math>A=\mathcal{E}_n</math> and <math>B=\mathcal{E}_1\wedge\mathcal{E}_2\wedge\cdots\wedge\mathcal{E}_{n-1}</math>, then
| |
| :<math>\begin{align}
| |
| \Pr[\mathcal{E}_1\wedge\mathcal{E}_2\wedge\cdots\wedge\mathcal{E}_n]
| |
| &=
| |
| \Pr[\mathcal{E}_1\wedge\mathcal{E}_2\wedge\cdots\wedge\mathcal{E}_{n-1}]\cdot\Pr\left[\mathcal{E}_n\mid \bigwedge_{i<n}\mathcal{E}_i\right].
| |
| \end{align}
| |
| </math>
| |
| Recursively applying this equation to <math>\Pr[\mathcal{E}_1\wedge\mathcal{E}_2\wedge\cdots\wedge\mathcal{E}_{n-1}]</math> until there is only <math>\mathcal{E}_1</math> left, the theorem is proved.
| |
| }}
| |
|
| |
|
| =Polynomial Identity Testing (PIT)=
| | Another way of saying it: ''the inclusive fitness of an organism is not a property of itself, but a property of its set of [[genes]]''. It is calculated from from the reproductive success of the individual, plus the reproductive success of its relatives, each one weighed by an appropriate coefficient of relatedness.<ref>Adapted from Dawkins R. 1982. ''The extended phenotype''. Oxford: Oxford University Press, p186. ISBN 0-19-288051-9</ref> |
| Consider the following problem of '''Polynomial Identity Testing (PIT)''':
| |
| * '''Input:''' two <math>n</math>-variate polynomials <math>f, g\in\mathbb{F}[x_1,x_2,\ldots,x_n]</math> of degree <math>d</math>.
| |
| * '''Output:''' "yes" if <math>f\equiv g</math>, and "no" if otherwise.
| |
| The <math>\mathbb{F}[x_1,x_2,\ldots,x_n]</math> is the [http://en.wikipedia.org/wiki/Polynomial_ring#The_polynomial_ring_in_several_variables of multi-variate polynomials] over field <math>\mathbb{F}</math>. The most natural way to represent an <math>n</math>-variate polynomial of degree <math>d</math> is to write it as a sum of monomials:
| |
| :<math>f(x_1,x_2,\ldots,x_n)=\sum_{i_1,i_2,\ldots,i_n\ge 0\atop i_1+i_2+\cdots+i_n\le d}a_{i_1,i_2,\ldots,i_n}x_{1}^{i_1}x_2^{i_2}\cdots x_{n}^{i_n}</math>.
| |
| The '''degree''' or '''total degree''' of a monomial <math>a_{i_1,i_2,\ldots,i_n}x_{1}^{i_1}x_2^{i_2}\cdots x_{n}^{i_n}</math> is given by <math>i_1+i_2+\cdots+i_n</math> and the degree of a polynomial <math>f</math> is the maximum degree of monomials of nonzero coefficients.
| |
|
| |
|
| Alternatively, we can consider the following equivalent problem:
| | == History == |
| * '''Input:''' a polynomial <math>f\in\mathbb{F}[x_1,x_2,\ldots,x_n]</math> of degree <math>d</math>.
| | The [[British]] [[Sociology|social]] [[philosopher]] [[Herbert Spencer]] coined the phrase ''[[survival of the fittest]]'' in his 1864 work ''Principles of biology'' to mean what [[Charles Darwin]] called [[natural selection]].<ref> Herbert Spencer 1864. ''Principles of Biology'' London, vol 1, 444, wrote “This survival of the fittest, which I have here sought to express in mechanical terms, is that which Mr. Darwin has called ‘natural selection’, or the preservation of favoured races in the struggle for life. </ref> The original phrase was "survival of the best fitted". |
| * '''Output:''' "yes" if <math>f\equiv 0</math>, and "no" if otherwise.
| |
|
| |
|
| If <math>f</math> is written explicitly as a sum of monomials, then the problem is trivial. Again we allow <math>f</math> to be represented in product form.
| | == References == |
| | {{Reflist}} |
| | |
|
| |
|
| {{Theorem|Example|
| | [[Category:Classical genetics]] |
| The [http://en.wikipedia.org/wiki/Vandermonde_matrix Vandermonde matrix] <math>M=M(x_1,x_2,\ldots,x_n)</math> is defined as that <math>M_{ij}=x_i^{j-1}</math>, that is
| | [[Category:Evolutionary biology]] |
| :<math>M=\begin{bmatrix}
| |
| 1 & x_1 & x_1^2 & \dots & x_1^{n-1}\\
| |
| 1 & x_2 & x_2^2 & \dots & x_2^{n-1}\\
| |
| 1 & x_3 & x_3^2 & \dots & x_3^{n-1}\\
| |
| \vdots & \vdots & \vdots & \ddots &\vdots \\
| |
| 1 & x_n & x_n^2 & \dots & x_n^{n-1}
| |
| \end{bmatrix}</math>.
| |
| Let <math>f</math> be the polynomial defined as
| |
| :<math>
| |
| f(x_1,\ldots,x_n)=\det(M)=\prod_{j<i}(x_i-x_j).
| |
| </math>
| |
| It is pretty easy to evaluate <math>f(x_1,x_2,\ldots,x_n)</math> on any particular <math>x_1,x_2,\ldots,x_n</math>, however it is prohibitively expensive to symbolically expand <math>f(x_1,\ldots,x_n)</math> to its sum-of-monomial form.
| |
| }}
| |
| | |
| == Schwartz-Zippel Theorem==
| |
| Here is a very simple randomized algorithm, due to Schwartz and Zippel.
| |
| {{Theorem|Randomized algorithm for multi-variate PIT|
| |
| * fix an arbitrary set <math>S\subseteq \mathbb{F}</math> whose size to be fixed;
| |
| * pick <math>r_1,r_2,\ldots,r_n\in S</math> uniformly and independently at random;
| |
| * if <math>f(\vec{r})=f(r_1,r_2,\ldots,r_n) = 0</math> then return “yes” else return “no”;
| |
| }}
| |
| | |
| This algorithm requires only the evaluation of <math>f</math> at a single point <math>\vec{r}</math>. And if <math>f\equiv 0</math> it is always correct.
| |
| | |
| In the Theorem below, we’ll see that if <math>f\not\equiv 0</math> then the algorithm is incorrect with probability at most <math>\frac{d}{|S|}</math>, where <math>d</math> is the degree of the polynomial <math>f</math>.
| |
| | |
| {{Theorem|Theorem (Schwartz-Zippel)|
| |
| : Let <math>f\in\mathbb{F}[x_1,x_2,\ldots,x_n]</math> be a multivariate polynomial of degree <math>d</math> over a field <math>\mathbb{F}</math> such that <math>f\not\equiv 0</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,r_2\ldots,r_n</math> be chosen uniformly and independently at random from <math>S</math>. Then
| |
| ::<math>\Pr[f(r_1,f_2,\ldots,r_n)=0]\le\frac{d}{|S|}.</math>
| |
| }}
| |
| {{Proof|
| |
| We prove by induction on <math>n</math> the number of variables.
| |
| | |
| For <math>n=1</math>, assuming that <math>f\not\equiv 0</math>, due to the fundamental theorem of algebra, the degree-<math>d</math> polynomial <math>f(x)</math> has at most <math>d</math> roots, thus
| |
| :<math>\Pr[f(r)=0]\le\frac{d}{|S|}.
| |
| </math>
| |
| | |
| Assume the induction hypothesis for a multi-variate polynomial up to <math>n-1</math> variable.
| |
| | |
| An <math>n</math>-variate polynomial <math>f(x_1,x_2,\ldots,x_n)</math> can be represented as
| |
| :<math>f(x_1,x_2,\ldots,x_n)=\sum_{i=0}^kx_n^{i}f_i(x_1,x_2,\ldots,x_{n-1})</math>,
| |
| where <math>k</math> is the largest power of <math>x_n</math>, which means that the degree of <math>f_k</math> is at most <math>d-k</math> and <math>f_k\not\equiv 0</math>.
| |
| | |
| In particular, we write <math>f</math> as a sum of two parts:
| |
| :<math>f(x_1,x_2,\ldots,x_n)=x_n^k f_k(x_1,x_2,\ldots,x_{n-1})+\bar{f}(x_1,x_2,\ldots,x_n)</math>,
| |
| where both <math>f_k</math> and <math>\bar{f}</math> are polynomials, such that
| |
| * as argued above, the degree of <math>f_k</math> is at most <math>d-k</math> and <math>f_k\not\equiv 0</math>;
| |
| * <math>\bar{f}(x_1,x_2,\ldots,x_n)=\sum_{i=0}^{k-1}x_n^i f_i(x_1,x_2,\ldots,x_{n-1})</math>, thus <math>\bar{f}(x_1,x_2,\ldots,x_n)</math> has no <math>x_n^{k}</math> factor in any term.
| |
| | |
| By the law of total probability, it holds that
| |
| :<math> | |
| \begin{align}
| |
| &\Pr[f(r_1,r_2,\ldots,r_n)=0]\\
| |
| =
| |
| &\Pr[f(\vec{r})=0\mid f_k(r_1,r_2,\ldots,r_{n-1})=0]\cdot\Pr[f_k(r_1,r_2,\ldots,r_{n-1})=0]\\
| |
| &+\Pr[f(\vec{r})=0\mid f_k(r_1,r_2,\ldots,r_{n-1})\neq0]\cdot\Pr[f_k(r_1,r_2,\ldots,r_{n-1})\neq0].
| |
| \end{align}
| |
| </math>
| |
| Note that <math>f_k(r_1,r_2,\ldots,r_{n-1})</math> is a polynomial on <math>n-1</math> variables of degree <math>d-k</math> such that <math>f_k\not\equiv 0</math>.
| |
| By the induction hypothesis, we have
| |
| :<math>
| |
| \begin{align}
| |
| (*)
| |
| &\qquad
| |
| &\Pr[f_k(r_1,r_2,\ldots,r_{n-1})=0]\le\frac{d-k}{|S|}.
| |
| \end{align}
| |
| </math>
| |
| | |
| For the second case, recall that <math>\bar{f}(x_1,\ldots,x_n)</math> has no <math>x_n^k</math> factor in any term, thus the condition <math>f_k(r_1,r_2,\ldots,r_{n-1})\neq0</math> guarantees that
| |
| :<math>f(r_1,\ldots,r_{n-1},x_n)=x_n^k f_k(r_1,r_2,\ldots,r_{n-1})+\bar{f}(r_1,r_2,\ldots,r_n)=g_{r_1,\ldots,r_{n-1}}(x_n)</math>
| |
| is a single-variate polynomial such that the degree of <math>g_{r_1,\ldots,r_{n-1}}(x_n)</math> is <math>k</math> and <math>g_{r_1,\ldots,r_{n-1}}\not\equiv 0</math>, for which we already known that the probability <math>g_{r_1,\ldots,r_{n-1}}(r_n)=0</math> is at most <math>\frac{k}{|S|}</math>.
| |
| Therefore,
| |
| :<math> | |
| \begin{align}
| |
| (**)
| |
| &\qquad
| |
| &\Pr[f(\vec{r})=0\mid f_k(r_1,r_2,\ldots,r_{n-1})\neq0]=\Pr[g_{r_1,\ldots,r_{n-1}}(r_n)=0\mid f_k(r_1,r_2,\ldots,r_{n-1})\neq0]\le\frac{k}{|S|}
| |
| \end{align}
| |
| </math>.
| |
| Substituting both <math>(*)</math> and <math>(**)</math> back in the total probability, we have
| |
| <math>
| |
| \Pr[f(r_1,r_2,\ldots,r_n)=0]
| |
| \le\frac{d-k}{|S|}+\frac{k}{|S|}=\frac{d}{|S|}.
| |
| </math>
| |
| }}
| |
| | |
| == Bipartite Perfect Matching==
| |
| | |
| = Min-Cut in a Graph =
| |
| Let <math>G(V, E)</math> be a graph. Suppose that we want to partition the vertex set <math>V</math> into two parts <math>S</math> and <math>T</math> such that the number of ''crossing edges'', edges with one endpoint in each part, is as small as possible. This can be described as the following problem: the min-cut problem.
| |
| | |
| For a connected graph <math>G(V, E)</math>, a '''cut''' is a set <math>C\subseteq E</math> of edges, removal of which causes <math>G</math> becomes disconnected. The min-cut problem is to find the cut with minimum cardinality. A canonical deterministic algorithm for this problem is through the [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem max-flow min-cut theorem]. A global minimum cut is the minimum <math>s</math>-<math>t</math> min-cut, which is equal to the minimum <math>s</math>-<math>t</math> max-flow.
| |
| | |
| Do we have to rely on the "advanced" tools like flows? The answer is "no", with a little help of randomness.
| |
| | |
| == Karger's Min-Cut Algorithm ==
| |
| We will introduce an extremely simple algorithm discovered by [http://people.csail.mit.edu/karger/ David Karger]. The algorithm works on multigraphs, graphs allowing multiple edges between vertices.
| |
| | |
| We define an operation on multigraphs called ''contraction'':
| |
| For a multigraph <math>G(V, E)</math>, for any edge <math>uv\in E</math>, let <math>contract(G,uv)</math> be a new multigraph constructed as follows: <math>u</math> and <math>v</math> in <math>V</math> are replaced by a singe new vertex whose neighbors are all the old neighbors of <math>u</math> and <math>v</math>. In other words, <math>u</math> and <math>v</math> are merged into one vertex. The old edges between <math>u</math> and <math>v</math> are deleted.
| |
| | |
| Karger's min-cut algorithm is described as follows:
| |
| | |
| '''MinCut(multigraph <math>G(V, E)</math>)'''
| |
| * while <math>|V|>2</math> do
| |
| ** choose an edge <math>uv\in E</math> uniformly at random;
| |
| ** <math>G=contract(G,uv)</math>;
| |
| *return the edges between the only two vertices in <math>V</math>;
| |
| | |
| ----
| |
| A better way to understand Karger's min-cut algorithm is to describe it as randomly merging sets of vertices. Initially, each vertex <math>v\in V</math> corresponds to a singleton set <math>\{v\}</math>. At each step, (1) a crossing edge (edge whose endpoints are in different sets) is chosen uniformly at random from all crossing edges; and (2) the two sets connected by the chosen crossing-edge are merged to one set. Repeat this process until there are only two sets. The crossing edges between the two sets are returned.
| |
| ----
| |
| | |
| == Analysis ==
| |
| For a multigraph <math>G(V, E)</math>, fixed a minimum cut <math>C</math> (there might be more than one minimum cuts), we analyze the probability that <math>C</math> is returned by the MinCut algorithm. <math>C</math> is returned by MinCut if and only if no edge in <math>C</math> is contracted during the execution of MinCut. We will bound this probability
| |
| <math>\Pr[\mbox{no edge in }C\mbox{ is contracted}]</math>.
| |
| | |
| {{Theorem
| |
| |Lemma 1|
| |
| :Let <math>G(V, E)</math> be a multigraph with <math>n</math> vertices, if the size of the minimum cut of <math>G</math> is <math>k</math>, then <math>|E|\ge nk/2</math>.
| |
| }}
| |
| {{Proof|
| |
| :It holds that every vertex has at least <math>k</math> neighbors, because if there exists <math>v</math> with <math><k</math> neighbors, then the <math><k</math> edges adjacent to <math>v</math> disconnect <math>v</math> from the rest of <math>G</math>, forming a cut of size smaller than <math>k</math>. Therefore <math>|E|\ge kn/2</math>.
| |
| }}
| |
| | |
| {{Theorem
| |
| |Lemma 2|
| |
| :Let <math>G(V, E)</math> be a multigraph with <math>n</math> vertices, and <math>C</math> a minimum cut of <math>G</math>. If <math>e\not\in C</math>, then <math>C</math> is still a minimum cut of <math>contract(G, e)</math>.
| |
| }}
| |
| {{Proof|
| |
| :We first show that no edge in <math>C</math> is lost during the contraction. Due to the definition of contraction, the only edges removed from <math>G</math> in a contraction <math>contract(G, e)</math> are the parallel-edges sharing both endpoints with <math>e</math>. Since <math>e\not\in C</math>, none of these edges can be in <math>C</math>, or otherwise <math>C</math> cannot be a minimum cut of <math>G</math>. Thus every edge in <math>C</math> remains in <math>G</math>.
| |
| | |
| :It is then obvious to see that <math>C</math> is a cut of <math>contract(G, e)</math>. All paths in a contracted graph can be revived in the original multigraph by inserting the contracted edges into the path, thus a connected <math>contract(G, e)-C</math> would imply a connected <math>G-C</math>, which contradicts that <math>C</math> is a cut in <math>G</math>.
| |
| | |
| :Notice that a cut in a contracted graph must be a cut in the original graph. This can be easily verified by seeing contraction as taking the union of two sets of vertices. Therefore a contraction can never reduce the size of minimum cuts of a multigraph. A minimum cut <math>C</math> must still be a minimum cut in the contracted graph as long as it is still a cut.
| |
| | |
| :Concluding the above arguments, we have that <math>C</math> is a minimum cut of <math>contract(G, e)</math> for any <math>e\not\in C</math>.
| |
| }}
| |
| | |
| Let <math>G(V, E)</math> be a multigraph, and <math>C</math> a minimum cut of <math>G</math>.
| |
| | |
| Initially <math>|V|=n</math>.
| |
| After <math>(i-1)</math> contractions, denote the current multigraph as <math>G_i(V_i, E_i)</math>. Suppose that no edge in <math>C</math> has been chosen to be contracted yet. According to Lemma 2, <math>C</math> must be a minimum cut of the <math>G_i</math>. Then due to Lemma 1, the current edge number is <math>|E_i|\ge |V_i||C|/2</math>. Uniformly choosing an edge <math>e\in E_i</math> to contract, the probability that the <math>i</math>th contraction contracts an edge in <math>C</math> is given by:
| |
| | |
| :<math>\begin{align}\Pr_{e\in E_i}[e\in C] &= \frac{|C|}{|E_i|}
| |
| &\le |C|\cdot\frac{2}{|V_i||C|}
| |
| &= \frac{2}{|V_i|}.\end{align}</math>
| |
| | |
| Therefore, assuming that <math>C</math> is intact after <math>(i-1)</math> contractions, the probability that <math>C</math> survives the <math>i</math>th contraction is at least <math>1-2/|V_i|</math>. Note that <math>|V_i|=n-i+1</math>, because each contraction decrease the vertex number by 1.
| |
| | |
| The probability that no edge in the minimum cut <math>C</math> is ever contracted is:
| |
| | |
| :<math>\begin{align}
| |
| &\quad\,\prod_{i=1}^{n-2}\Pr[\,C\mbox{ survives all }(n-2)\mbox{ contractions }]\\
| |
| &=
| |
| \prod_{i=1}^{n-2}\Pr[\,C\mbox{ survives the }i\mbox{-th contraction}\mid C\mbox{ survives the first }(i-1)\mbox{-th contractions}]\\
| |
| &=
| |
| \prod_{i=1}^{n-2}\left(1-\frac{2}{|V_i|}\right) \\
| |
| &=
| |
| \prod_{i=1}^{n-2}\left(1-\frac{2}{n-i+1}\right)\\
| |
| &=
| |
| \prod_{k=3}^{n}\frac{k-2}{k}\\
| |
| &= \frac{2}{n(n-1)}.
| |
| \end{align}</math>
| |
| | |
| Therefore, we prove the following theorem,
| |
| | |
| {{Theorem
| |
| |Theorem|
| |
| : For any multigraph with <math>n</math> vertices, the MinCut algorithm returns a minimum cut with probability at least <math>\frac{2}{n(n-1)}</math>.
| |
| }}
| |
| | |
| Run MinCut independently for <math>n(n-1)/2</math> times and return the smallest cut returned. The probability that this the minimum cut is found is:
| |
| | |
| :<math>\begin{align}
| |
| 1-\Pr[\mbox{failed every time}] &= 1-\Pr[\mbox{MinCut fails}]^{n(n-1)/2} \\
| |
| &\ge 1- \left(1-\frac{2}{n(n-1)}\right)^{n(n-1)/2} \\
| |
| &\ge 1-\frac{1}{e}.
| |
| \end{align}</math>
| |
| | |
| A constant probability!
| |