Why does Karger's algorithm work "with high probability"
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&gt;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.