Randomised Algorithms and the Probabilistic Method
An algorithm allowed to flip coins can be simpler and faster than any deterministic one known, at the price of a guarantee about expectation rather than about every run. The same idea proves objects exist by showing a random one works with positive probability.
What a learner can do afterwards
- Separate an algorithm that is always correct and sometimes slow from one that is fast and sometimes wrong
- Compute the expected running time of a randomised routine on a worst-case input
- Use a counting argument over a random object to show something with a wanted property exists
1 · Read
Some objects are proven, not built. Pick one at random, and show the chance it works beats zero. A positive chance means at least one good choice sits out there, even when nobody can point at it. Counting every possibility by hand would be hopeless; one random experiment replaces the search.
The same habit runs algorithms that flip coins. A Las Vegas routine is always correct and sometimes slow: randomized quicksort averages n log n on any input, and only unlucky coins slow it. A Monte Carlo routine is fast and sometimes wrong, with a small error chance you shrink by repeating it.
Count expected time over the coin flips on a worst-case input: the adversary picks the list, chance does the rest. For existence, bound the failure chance below one, and the bound turns chance into certainty. Random construction succeeding somewhere proves the object exists; random steps succeeding most of the time beat any careful deterministic plan.
Name which guarantee you surrender against a deterministic rival. Las Vegas surrenders fixed speed, Monte Carlo surrenders certainty, and both keep a precise statement about average or error instead. Never promise every run; promise the expectation or the bound.
Positive chance proves existence, coins buy speed or simplicity, and the guarantee moves from every run to average or error.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.