What is a randomized algorithm
With greedy, we picked the best option in front of us. Some methods, though, simply roll the dice: they decide at random what to choose. It sounds strange, but sometimes this is faster and simpler. How can leaving things to chance help?
Choosing with dice
Some methods decide what to do next by rolling a die. They don't think it through; they simply leave it to chance.
Each press of the button rolls the die once.
There's no knowing in advance which face will come up.
Press to roll the die. You can't know the next face in advance.
Why leave things to chance on purpose? If you always choose the same way, someone can exploit that habit and deliberately build a hard input.
Choosing at random sidesteps that kind of trick.
The real use shows up in the next step.
Using a random pivot
One kind of fast sort picks a single pivot and splits the rest, smaller values to the left and larger ones to the right.
But if you always use the last value as the pivot, an input that's already in order makes every split lopsided, and the sort becomes very slow.
Compare how many splitting steps it takes with the last value as pivot vs a random pivot. (lopsided = slow)
Choose the pivot at random, and whatever input comes in, splits almost never end up lopsided. Traps aimed at bad inputs don't work either.
So on average the splits come out even, and the sort gets faster.
Estimating by throwing many times
Randomness is also used for estimating. Inside a square, draw a quarter circle, one of four equal slices of a circle, and scatter points all over.
By seeing what share of all the points land inside the quarter circle, you can estimate how much of the area it covers.
Drop the points one at a time.
The more points you drop, the closer the ratio gets to the true value. (points in circle / all points)
With few points, the estimate jumps around. But the more points you drop, the more tightly the ratio hugs the true value.
You can't trust one or two lucky throws, but the average of countless throws is reliable.
This is how you estimate an answer by throwing many times.
Trading certainty for speed
Random methods aren't free. In exchange for being fast and simple, they can't promise the same answer every time, and with bad luck they're occasionally slow.
Press both sides to compare what you gain and what you give up.
Press what you gain and what you give up to compare. (fast · simple vs no guarantee of the same answer)
So randomness isn't always good; it has its proper place.
Use it when being fast and simple is worth more than a little uncertainty. You give up a bit of certainty to buy speed and simplicity.
Summary at a glance
Here are random methods at a glance: choose with dice, avoid traps with a random pivot, estimate an answer by throwing many times, and trade certainty for speed.
Press the key points in order to sum them up yourself.
Press the four key points in order to sum up. (dice · random pivot · estimating by many throws · the trade-off)
Leaving things to chance sounds sloppy, but used well, randomness is a fast and dependable tool.
The more enormous the data, the more this idea of estimating by throwing many times comes into play.
In the next lesson, we move on to a world of points connected by lines: graphs.