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.
More to read
Probabilistic Methods in Combinatorics
One way to prove that something exists is this: instead of building it, show that if you picked one at random, you would get lucky with some chance bigger than zero. If a random choice works with positive probability, then at least one good choice must be out there, even if nobody can point to it directly.
This trick is called the probabilistic method, and it is a central idea in combinatorics and computer science. Suppose you want to show there is a way to color a graph, or arrange a tournament, with some property you care about. Counting every possibility by hand is hopeless. But pick a coloring at random and compute the chance it fails. If that chance is less than one, success must happen somewhere.
The same habit of thought runs through randomised algorithms, where a program flips coins as it runs. You stop asking "will this always work?" and start asking "what happens on average, and how often does it fail?" A random construction that succeeds with positive probability proves existence; a random algorithm that succeeds most of the time can be simpler and faster than any careful deterministic plan. Two kinds matter. A Las Vegas algorithm is always correct and sometimes slow: randomised quicksort from earlier in this thread is one, since its expected running time is n log n on any input and only unlucky coins make it slower. A Monte Carlo algorithm is fast and sometimes wrong, with a small error chance you shrink by repeating it. Expected running time is counted over the coin flips for a worst case input, so the adversary picks the list and chance does the rest.
This graduate-level course teaches the method itself: how to set up the random experiment, how to bound the probability of failure, and how to turn a statement about chance into a statement about certainty. It focuses on the core techniques and on applying them to real combinatorial problems.
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.