Why does Karger's algorithm work "with high probability"

Question

I'm reading Karger 1993's "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm" (link).

It states that a single round of contractions yields a min-cut with probability $\Omega(n^{-2})$ and concludes that $O(n^2 \log n)$ independent contractions are sufficient to find a min-cut with high probability.

It makes sense to me that $O(n^2)$ independent contractions yields a min-cut with a probability of approximately 1. Anything above this increases the probability, but why has $\log n$ being chosen?

Answer 1

Lets say that the algorithm succeeds if it produces a min cut. First, it is proved that a single run of the algorithm succeeds with probability $\Omega(n^{-2}),ドル i.e. with probability $\ge \frac{c}{n^2}$ for some $c>0$.

This is, of course, very bad. For large $n$ our success probability converges to zero. However, if we run it independently $k$ times, then our failure probability is now $\left(1-\frac{c}{n^2}\right)^k$ (we choose the minimal cut obtained from the $k$ runs, in order to fail finding the cut in this manner we must fail every time). Finally, we have:

$\Pr\left[\text{failure}\right]\le \left(1-\frac{c}{n^2}\right)^k\le e^{-\frac{kc}{n^2}},ドル taking $k=n^2\log n$ we get:

$\Pr\left[\text{failure}\right]\le e^{-c\log n} = \frac{1}{n^c},ドル which converges to zero, as apposed to our failure probability after a single run of the algorithm.

• Richard: So the a probability of failure which is $\le \frac{1}{n^c}$ is a high probability of success and an appropriate expression for $k$ is sought?
• Ariel: I'm not sure i understand your question. "High" means (in this context) that your success probability goes to 1 as your input's size increases. I added $k$ just to show how the error probability is bounded in terms of the number of independent runs.
• Gaslight Deceive Subvert: If anyone wonders why $(1 - c/n^2)^k \leq e^{-kc/n^2},ドル it follows from 1ドル - x \leq e^{-x}$ which is a fundamental inequality in calculus.

Answer 2

Approximately, if a chance NOT to find a cut in independent contraction is 1ドル-\frac{a}{n^2},ドル then a chance to find it in $n^2\log n$ contractions is $$ 1-\left(1-\frac{a}{n^2}\right)^{n^2\log n}=1-\left(\left(1-\frac{a}{n^2}\right)^{n^2}\right)^{\log n}\approx 1-\exp(-a\log n)=1-\frac{a}{n}. $$