An algorithm that is right with probability p and, when it is wrong, is detectably no better, becomes an algorithm that is right with probability 1 − (1 − p)ᵗ after t independent runs. On the lab's bridge graph p = 13/35, so five runs reach 9/10 and ten reach 99/100. The panel finds the smallest t by multiplying rather than by taking a logarithm, so the answer is an exact integer and the probability beside it is an exact fraction.
Core ideas
The hard idea is the hypothesis: repetition only helps when you can tell a better answer from a worse one. The other two are the arithmetic and how the smallest t is found.
Run the algorithm t times with independent randomness and keep the smallest cut any run returned. The kept answer is wrong only if every run was wrong, and the runs are independent, so that has probability (1 − p)ᵗ. On the bridge graph p = 13/35, so 1 − p = 22/35 and ten runs fail with probability (22/35)¹⁰ ≈ 0.0096. The panel computes that as an exact fraction rather than as a decimal.
Karger's algorithm never returns a cut smaller than the minimum, because everything it returns is a genuine cut. So a run that returns 2 edges is definitely at least as good as a run that returns 3, and taking the best of t answers cannot be fooled. If an algorithm could err in both directions, the best of t answers would be the most extreme error rather than the best answer, and amplification would make things worse.
t ≥ ln(1/δ)/p is the familiar estimate, and it is an estimate: it involves logarithms of quantities that are not exact and it rounds. The panel instead multiplies 1 − p by itself until the product drops below 1 − target, counting the steps. The answer is the exact least t, and the routine refuses rather than looping if p is zero.
The material
The amplification identity, the graph where one run is worst, and the exact cost of each target.
The lab's hardest graph is two triangles joined by a single edge: 1-2, 1-3, 2-3, 4-5, 4-6, 5-6, 3-4. Seven edges, six vertices, and a unique minimum cut of one edge — the bridge 3-4. There is exactly one way to succeed and the single edge has to survive all four contractions, which it does with probability 13/35 ≈ 0.3714. Over seeds 1 to 120 the algorithm succeeded 41 times and missed 79, the first miss being seed 1, which returned a cut of two edges.
One run at 0.37 is not an algorithm anybody would use. The question this page answers is what it costs to turn it into one, and the answer is exact.
Let one run of a Monte Carlo algorithm return a correct answer with probability at least p, and suppose a wrong answer is never better than a correct one, so that keeping the best of several runs keeps a correct answer if any run produced one. Then t independent runs return a correct answer with probability at least 1 − (1 − p)ᵗ.
Let Aᵢ be the event that run i returns a correct answer, so P(Aᵢ) ≥ p. The kept answer is incorrect only if every run was incorrect, which is the intersection of the complements.
The runs use independent randomness, so those complements are independent and P(no run correct) = Π P(not Aᵢ) ≤ (1 − p)ᵗ. The kept answer is therefore correct with probability at least 1 − (1 − p)ᵗ.
The hypothesis about wrong answers is where the “keep the best” step is discharged: without it, knowing that some run was correct does not tell you that the answer you kept is.
□
On the bridge graph that gives 1 − (22/35)ᵗ. The panel prints it at several values of t as exact fractions with decimals beside them, and the growth is the one to internalise: each extra run multiplies the failure probability by 22/35, so failure decays geometrically while the work grows linearly.
Switch to the two triangles joined by two edges, where one run succeeds with probability 19/35. Now three runs reach 9/10, six reach 99/100 and nine reach 999/1000. Compare with the bridge graph's 5, 10 and 15. The success probability changed by less than a factor of two and the cost of a given target changed by about the same factor, which is what a geometric decay predicts: halving p roughly doubles the runs needed.
And on the four-cycle one run succeeds with probability 1, so the smallest t for every target is 1, and the panel prints 1 rather than a logarithm's rounded suggestion. That is the case where the general formula would still work and would be an odd thing to quote.
It does not make the algorithm always correct. 1 − (22/35)¹⁵ is about 0.9991, which is not 1, and no finite t reaches 1. The panel's target menu offers 9/10, 99/100 and 999/1000 rather than certainty for that reason. If you need certainty you need a different algorithm; what repetition buys is a failure probability you choose, at a cost you can compute.
It also does not help if the runs share randomness. Independence is a hypothesis of the theorem, and it is the hypothesis that a real implementation is most likely to break — by reusing a seed, by deriving all t seeds from one in a way that correlates them, or by drawing from a generator whose low bits are a short cycle. The generator behind every lab on this course is a prime-modulus stream with a mixed seed for exactly that reason.
And it does not turn a one-sided guarantee into a two-sided one. Everything above rested on being able to prefer one answer to another. The next lesson's algorithm has the same structure from a different direction: a primality test whose positive findings are proofs and whose negative findings are silence, so that repeating it accumulates evidence in one direction only.
Interactive
The success probability is a recursion over contraction states, exact; the measured rate over seeds is not it, and repetition is what makes either of them useful
Method
Establish one run's probability first; everything after it is one multiplication per run.
Can you tell a better answer from a worse one without knowing the truth? For a minimum cut, yes: fewer edges is better and nothing returned is ever below the minimum. If not, keeping the best of t runs is keeping the most extreme error.
The panel computes it by recursion over contraction states. Where you cannot compute it, use the proved bound — and then the t you derive is a bound on the runs needed rather than the exact number.
(1 − p) times itself, counting steps until it falls under 1 − target. This gives the least t exactly. The logarithmic formula is a fine estimate and it rounds in an unstated direction, which matters when t is small.
Ten runs on the bridge graph leave a failure probability of about 0.0096, not zero. Write that number down next to the answer; it is the part of the guarantee that is easiest to drop and the only part that is a risk.
1-2, 1-3, 2-3, 4-5, 4-6, 5-6, 3-4. A unique minimum cut of one edge, the bridge 3-4, which must survive four contractions. One run succeeds with probability 13/35.
The measured rate 41/120 ≈ 0.342 sits below the exact 13/35 ≈ 0.371. At the previous lesson's graph the measured rate sat above the exact one. Both are ordinary, and the pair of observations is the cheapest available demonstration that a measured rate is not an estimate of the truth in any sense you can act on at 120 samples.
Ten runs of an algorithm that is wrong 63 per cent of the time give an answer that is wrong less than one per cent of the time. Nothing about the algorithm improved; the failure probability was multiplied by 22/35 ten times. That is the whole trade, and it is why a Monte Carlo algorithm with a constant success probability is a useful object even when the constant is small.
For a faded rehearsal, set the target to 999/1000 and predict the smallest t on the two-triangles-joined-by-two-edges graph before switching to it. The supplied first move is this: there p = 19/35, so 1 − p = 16/35 ≈ 0.457, and each run multiplies the failure probability by that. Estimate how many runs take 0.457ᵗ below 0.001, then check the exact answer — and then say why the bridge graph needs 15 for the same target.
You should be able to derive 1 − (1 − p)ᵗ, name the one-sided-error hypothesis that licenses keeping the best run, find the smallest t for a target by multiplying, and state the residual failure probability you have bought rather than implying certainty.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.